分类： 赛事资讯

For the New Year celebration, Bessie and her friends have constructed a giant tree with many glowing ornaments. Bessie has the ability to turn the ornaments on and off through remote control. Before the sun rises, she wants to toggle some of the ornaments in some order (possibly toggling an ornament more than once) such that the tree starts and ends with no ornaments on. Bessie thinks the tree looks cool if the set of activated ornaments is exactly a subtree rooted at some vertex. She wants the order of ornaments she toggles to satisfy the property that, for every subtree, at some point in time it was exactly the set of all turned on ornaments. Additionally, it takes energy to switch on and off ornaments, and Bessie does not want to waste energy, so she wants to find the minimum number of toggles she can perform.

Formally, you have a tree with vertices labeled 1…N (2≤N≤2⋅105) rooted at 1. Each vertex is initially inactive. In one operation, you can toggle the state of a single vertex from inactive to active or vice versa. Output the minimum possible length of a sequence of operations satisfying both of the following conditions:

Define the subtree rooted at a vertex r to consist of all vertices v such that r lies on the path from 1 to v inclusive. For every one of the N subtrees of the tree, there is a moment in time when the set of active vertices is precisely those in that subtree.
Every vertex is inactive after the entire sequence of operations.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The second line contains p2…pN (1≤pi<i), where pi denotes the parent of vertex i in the tree.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the minimum possible length.

SAMPLE INPUT:

3
1 1

SAMPLE OUTPUT:

6
There are three subtrees, corresponding to {1,2,3}, {2}, and {3}. Here is one sequence of operations of the minimum possible length:

activate 2
(activated vertices form the subtree rooted at 2)
activate 1
activate 3
(activated vertices form the subtree rooted at 1)
deactivate 1
deactivate 2
(activated vertices form the subtree rooted at 3)
deactivate 3
SCORING:
Inputs 2-3: N≤8
Inputs 4-9: N≤40
Inputs 10-15: N≤5000
Inputs 16-21: No additional constraints.
Problem credits: Benjamin Qi

Note: The time limit for this problem is 5s, 2.5 times the default. The memory limit for this problem is 512MB, twice the default.

Bessie has recently taken an interest in magic and needs to collect mana for a very important spell. Bessie has N (1≤N≤18) mana pools, the ith of which accumulates mi mana per second (1≤mi≤108). The pools are linked by a collection of M (0≤M≤N(N−1)) directed edges (ai,bi,ti), meaning that she can travel from ai to bi in ti seconds (1≤ai,bi≤N, ai≠bi, 1≤ti≤109). Whenever Bessie is present at a pool, she can collect all the mana stored at that location, emptying it. At time 0, all mana pools are empty, and Bessie can select any pool to start at.

Answer Q (1≤Q≤2⋅105) queries, each specified by two integers s and e (1≤s≤109, 1≤e≤N). For each query, determine the maximum amount of mana Bessie can collect in s seconds if she must be at mana pool e at the end of the sth second.

INPUT FORMAT (input arrives from the terminal / stdin):

First line contains N and M.
Next line contains m1,m2,…,mN.

Next M lines contain ai,bi,ti. No ordered pair (ai,bi) appears more than once in the input.

Next line contains Q.

Next Q lines contain two integers s and e.

OUTPUT FORMAT (print output to the terminal / stdout):

Q lines, one for each query.

SAMPLE INPUT:

2 1
1 10
1 2 10
4
5 1
5 2
100 1
100 2

SAMPLE OUTPUT:

5
50
100
1090
First query: Bessie takes 5 mana from pool 1 after 5 seconds.

Second query: Bessie takes 50 mana from pool 2 after 5 seconds.

Third query: Bessie takes 100 mana from pool 1 after 100 seconds.

Fourth query: Bessie takes 90 mana from pool 1 after 90 seconds and 1000 mana from pool 2 after 100 seconds.

SAMPLE INPUT:

4 8
50000000 100000000 20000000 70000000
1 2 20
2 1 50
2 3 90
1 3 40
3 1 10
4 1 25
1 4 5
4 3 70
3
8 3
1000000000 1
500000 4

SAMPLE OUTPUT:

160000000
239999988050000000
119992550000000
An example where Bessie is able to collect much larger amounts of mana.

SCORING:

Inputs 3-4: N≤10,Q≤100
Inputs 5-9: N≤10
Inputs 10-14: Q≤100
Inputs 15-17: N=16
Inputs 18-20: N=17
Inputs 21-24: No additional constraints.
Problem credits: Benjamin Qi

Note: The time limit for this problem is 4s, twice the default. The memory limit for this problem is 512MB, twice the default.

Farmer John has N (2≤N≤2⋅105) tractors, where the ith tractor can only be used within the inclusive interval [ℓi,ri]. The tractor intervals have left endpoints ℓ1<ℓ2<⋯<ℓN and right endpoints r1<r2<⋯<rN. Some of the tractors are special.

Two tractors i and j are said to be adjacent if [ℓi,ri] and [ℓj,rj] intersect. Farmer John can transfer from one tractor to any adjacent tractor. A path between two tractors a and b consists of a sequence of transfers such that the first tractor in the sequence is a, the last tractor in the sequence is b, and every two consecutive tractors in the sequence are adjacent. It is guaranteed that there is a path between tractor 1 and tractor N. The length of a path is the number of transfers (or equivalently, the number of tractors within it minus one).

You are given Q (1≤Q≤2⋅105) queries, each specifying a pair of tractors a and b (1≤a<b≤N). For each query, output two integers:

The length of any shortest path between tractor a to tractor b.
The number of special tractors such that there exists at least one shortest path from tractor a to tractor b containing it.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and Q.
The next line contains a string of length 2N consisting of Ls and Rs, representing the left and right endpoints in sorted order. It is guaranteed that for each proper prefix of this string, the number of Ls exceeds the number of Rs.

The next line contains a bit string of length N, representing for each tractor whether it is special or not.

The next Q lines each contain two integers a and b, specifying a query.

OUTPUT FORMAT (print output to the terminal / stdout):

For each query, the two quantities separated by spaces.

SAMPLE INPUT:

8 10
LLLLRLLLLRRRRRRR
11011010
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5

SAMPLE OUTPUT:

1 2
1 1
1 2
2 4
2 3
2 4
2 3
1 1
1 2
1 2
The 8 tractor intervals, in order, are [1,5],[2,10],[3,11],[4,12],[6,13],[7,14],[8,15],[9,16].
For the 4th query, there are three shortest paths between the 1st and 5th tractor: 1 to 2 to 5, 1 to 3 to 5, and 1 to 4 to 5. These shortest paths all have length 2.

Additionally, every tractor 1,2,3,4,5 is part of one of the three shortest paths mentioned earlier, and since 1,2,4,5 are special, there are 4 special tractors such that there exists at least one shortest path from tractor 1 to 5 containing it.

SCORING:

Inputs 2-3: N,Q≤5000
Inputs 4-7: There are at most 10 special tractors.
Inputs 8-16: No additional constraints.
Problem credits: Benjamin Qi

2023 年 2 月的比赛以算法编程问题为特色，涵盖了广泛的技术和难度级别。

在为期 4 天的比赛中，共有 10441 名不同的用户登录。共有 8672 名参与者提交了至少一个解决方案，来自 88 个不同的国家：

4328 美国 2828 CHN 263 KOR 257 CAN 95 IND 91 ROU 69 MYS
57 SGP 55 TWN 52 DEU 36 HKG 32 GBR 31 SYR 30 EGY
26 ISR 24 AUS 19 ARM 18 IRN 17 KAZ 16 JPN 15 NZL
14 VNM 14 UKR 14 TUR 14 POL 14 MNG 14 GEO 14 BRA
12 SLV 11 AZE 10 UZB 10 FRA 9 MEX 9 GRC 9 CHE
9 BGD 8 THA 7 TUN 7 ARE 6 VEN 6 PHL 5 TKM
5 RUS 5 PER 5 ITA 5 EST 5 ESP 5 BLR 4 SAU
4 COL 3 ZAF 3 LTU 3 KGZ 3 BGR 2 SWE 2 SRB
2 NPL 2 NLD 2 NGA 2 MLT 2 MDA 2 MAC 2 LKA
2 IDN 2 HRV 2 CUB 2 AFG 1 TJK 1 SVN 1 SVK
1 QAT 1 PRK 1 NOR 1 LUX 1 KHM 1 ISL 1 IRL
1 GUM 1 FIN 1 ETH 1 CYP 1 CMR 1 CHL 1 CAF
1 BIH 1 BEL 1 BDI 1 ARG

总共有 20488 份评分提交，按语言细分如下：

以下是白金、黄金、白银和铜牌比赛的详细结果。您还将找到每个问题的解决方案和测试数据。

USACO 2023 年2月学术活动，白金

铂金组共有463人参加，其中322人为预科生。最佳得分手的结果在这里。祝贺所有优秀选手取得的优异成绩！

1 Hungry Cow
查看问题 | 测试数据 | 解决方案
2 Problem Setting
查看问题 | 测试数据 | 解决方案
3 Watching Cowflix
查看问题 | 测试数据 | 解决方案

USACO 2023 年2月学术活动，金奖

黄金组总人数1030人，其中预科生743人。所有在本次比赛中获得 750 分或更高分的参赛者将自动晋升为白金级别。所有晋升者的详细结果都在这里。

1 Equal Sum Subarrays
查看问题 | 测试数据 | 解决方案
2 Fertilizing Pastures
查看问题 | 测试数据 | 解决方案
3 Piling Papers
查看问题 | 测试数据 | 解决方案

USACO 2023 年2月学术活动，银奖

银牌组共有4010人参加，其中预科生3101人。所有在本次比赛中获得 700 分或更高分的参赛者将自动晋升为黄金组。

1 Bakery
查看问题 | 测试数据 | 解决方案
2 Cow-libi
查看问题 | 测试数据 | 解决方案
3 Moo Route II
查看问题 | 测试数据 | 解决方案

USACO 2023 年2月学术活动，铜奖

青铜组总参赛人数5694人，其中预科生4425人。所有在本次比赛中获得 750 分或更高分的参赛者将自动晋升为银牌组。

1 Hungry Cow
查看问题 | 测试数据 | 解决方案
2 Stamp Grid
查看问题 | 测试数据 | 解决方案
3 Watching Mooloo
查看问题 | 测试数据 | 解决方案

最后的评论

到目前为止，我很高兴看到整个 2022-2023 赛季的持续高参与度。2 月的比赛非常具有挑战性，尤其是在银牌组，但我们仍然看到晋级人数很多。

对于那些尚未晋升的人，请记住，您练习得越多，您的算法编码技能就会越好——请坚持下去！USACO 比赛旨在挑战最优秀的学生，要想在比赛中脱颖而出，需要付出大量的努力。为了帮助您修复代码中的任何错误，您现在可以重新提交您的解决方案并使用“分析模式”从评审服务器获得反馈。

许多人为 USACO 比赛的质量和成功做出了贡献。为本次比赛提供帮助的人包括 Brandon Wang、Claire Zhang、Benjamin Qi、Danny Mittal、Mark Gordon、Rohin Garg、Jesse Choe、Nathan Wang、David Hu、Mihir Singhal、Andi Qu、Spencer Compton 和 Richard Qi。还要感谢我们的翻译人员和克莱姆森 CCIT 为我们提供比赛基础设施。最后，我们感谢 USACO 赞助商的慷慨支持：Citadel、Ansatz、X-Camp、TwoSigma、VPlanet Coding、EasyFunCoding、Orijtech 和 Jump Trading。

我们期待在美国公开赛上再次见到大家，这是我们本赛季的最后一场比赛！

编码愉快！

Bessie likes to watch shows on Mooloo. Because Bessie is a busy cow, she has planned a schedule for the next N (1≤N≤105) days that she will watch Mooloo. Because Mooloo is a paid subscription service, she now needs to decide how to minimize the amount of money she needs to pay.

Mooloo has an interesting subscription system: it costs d+K (1≤K≤109) moonies to subscribe to Mooloo for d consecutive days. You can start a subscription at any time, and you can start a new subscription as many times as you desire if your current subscription expires. Given this, figure out the minimum amount of moonies Bessie needs to pay to fulfill her schedule.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains integers N and K.

The second line contains N integers describing the days Bessie will watch Mooloo: 1≤d1<d2<⋯<dN≤1014.

OUTPUT FORMAT (print output to the terminal / stdout):
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:
2 4
7 9
SAMPLE OUTPUT:
7
Bessie buys a three-day subscription on day 7, spending d+K=3+4=7 moonies.

SAMPLE INPUT:
2 3
1 10
SAMPLE OUTPUT:
8
Bessie first buys a one-day subscription on day 1, spending d+K=1+3=4 moonies. Bessie also buys a one-day subscription on day 10, spending d+K=1+3=4 moonies. In total, Bessie spends 8 moonies.

SCORING:
Inputs 3-5: N≤10
Inputs 6-12: No additional constraints.
Problem credits: Danny Mittal

A stamp painting is a black and white painting on an N×N canvas, where certain cells are inked while others are blank. It can be described by an N×N array of characters (1≤N≤20). The ith entry of the jth column of the array is equal to * if the canvas contains ink at that square and . otherwise.

Bessie has a stamp painting that she would like to create, so Farmer John has lent her a single K×K (1≤K≤N) stamp to do this and an empty N×N canvas. Bessie can repeatedly rotate the stamp clockwise by 90∘ and stamp anywhere on the grid as long as the stamp is entirely inside the grid. Formally, to stamp, Bessie chooses integers i,j such that i∈[1,N−K+1] and j∈[1,N−K+1]; for each (i′,j′) such that 1≤i′,j′≤K, canvas cell (i+i′−1,j+j′−1) is painted black if the stamp has ink at (i′,j′). Bessie can rotate the stamp at any time between stampings. Once a canvas cell is painted black, it remains black.

Farmer John is wondering whether it's possible for Bessie to create her desired stamp painting with his stamp. For each of T (1≤T≤100) test cases, help Farmer John answer this question.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains T, the number of test cases.
Each test case starts with an integer N followed by N lines, each containing a string of *s and .s, representing Bessie's desired stamp painting. The next line contains K and is followed by K lines, each containing a string of *s and .s, representing Farmer John's stamp.

Consecutive test cases are separated by newlines.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output "YES" or "NO" on separate lines.

SAMPLE INPUT:

4

2
**
*.
1
*

3
.**
.**
***
2
.*
**

3
...
.*.
...
3
.*.
...
...

3
**.
.**
..*
2
.*
*.

SAMPLE OUTPUT:

YES
YES
NO
YES
In the first test case, Bessie can perform the following sequence of stampings:

Stamp at (1,1)
Stamp at (1,2)
Stamp at (2,1)
In the second test case, Bessie can perform the following sequence of stampings:

Stamp at (2,2)
Stamp at (2,1)
Rotate 90∘
Rotate 90∘
Stamp at (1,2)
In the third test case, it is impossible to paint the middle cell.

In the fourth test case, Bessie can perform the following sequence of stampings:

Rotate 90∘
Stamp at (1,1)
Stamp at (1,2)
Stamp at (2,2)
Problem credits: Benjamin Qi and Claire Zhang

Bessie is a hungry cow. Each day, for dinner, if there is a haybale in the barn, she will eat one haybale. Farmer John does not want Bessie to starve, so some days he sends a delivery of haybales, which arrive in the morning (before dinner). In particular, on day di, Farmer John sends a delivery of bi haybales (1≤di≤1014, 1≤bi≤109).

Compute the total number of haybales Bessie will eat during the first T days.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains N and T (1≤N≤105, 1≤T≤1014).
The next N lines each contain di and bi. It is additionally guaranteed that 1≤d1<d2<⋯<dN≤T.

OUTPUT FORMAT (print output to the terminal / stdout):

Output the number of haybales that Bessie will eat during the first T days.
Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

1 5
1 2

SAMPLE OUTPUT:

2
Two haybales arrive on the morning of day 1. Bessie eats one haybale for dinner on day 1 and another haybale on day 2. On days 3…5, there are no more haybales for Bessie to eat. In total, Bessie eats 2 haybales during the first 5 days.

SAMPLE INPUT:

2 5
1 2
5 10

SAMPLE OUTPUT:

3
Two haybales arrive on the morning of day 1. Bessie eats one haybale on days 1 and 2. There are no haybales for Bessie to eat on days 3 and 4. On the morning of day 5, 10 haybales arrive. Bessie eats one haybale for dinner on day 5. In total, Bessie eats 3 haybales during the first 5 days.

SAMPLE INPUT:

2 5
1 10
5 10

SAMPLE OUTPUT:

5
10 haybales arrive on the morning of day 1. Bessie eats one haybale on days 1…4. On the morning of day 5, another 10 haybales arrive, meaning there are 16 haybales in the barn. For dinner on day 5, Bessie eats another haybale. In total, Bessie eats 5 haybales during the first 5 days.

SCORING:

Inputs 4-7: T≤105
Inputs 8-13: No additional constraints.
Problem credits: Brandon Wang

Note: The time limit for this problem is 4s, twice the default.

Bessie is on vacation! Due to some recent technological advances, Bessie will travel via technologically sophisticated flights, which can even time travel. Furthermore, there are no issues if two "parallel" versions of Bessie ever meet.

In the country there are N airports numbered 1,2,…,N and M time-traveling flights (1≤N,M≤200000). Flight j leaves airport cj at time rj, and arrives in airport dj at time sj (0≤rj,sj≤109, sj<rj is possible). In addition, she must leave ai time for a layover at airport i (1≤ai≤109). (That is to say, if Bessie takes a flight arriving in airport i at time s, she can then transfer to a flight leaving the airport at time r if r≥s+ai. The layovers do not affect when Bessie arrives at an airport.)

Bessie starts at city 1 at time 0. For each airport from 1 to N, what is the earliest time when Bessie can get to at it?

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input contains N and M.
The next M lines describe flights. The jth of these lines contains cj, rj, dj, sj in that order. (1≤cj,dj≤N, 0≤rj,sj≤109)

The next line describes airports. It contains N space separated integers, a1,…,aN.

OUTPUT FORMAT (print output to the terminal / stdout):

There are N lines of output. Line i contains the earliest time when Bessie can get to airport i, or -1 if it is not possible for Bessie to get to that airport.

SAMPLE INPUT:

3 3
1 0 2 10
2 11 2 0
2 1 3 20
10 1 10

SAMPLE OUTPUT:

0
0
20
Bessie can take the 3 flights in the listed order, which allows her to arrive at airports 1 and 2 at time 0, and airport 3 at time 20.

Note that this route passes through airport 2 twice, first from time 10-11 and then from time 0-1.

SAMPLE INPUT:

3 3
1 0 2 10
2 10 2 0
2 1 3 20
10 1 10

SAMPLE OUTPUT:

0
10
-1
In this case, Bessie can take flight 1, arriving at airport 2 at time 10. However, she does not arrive in time to also take flight 2, since the departure time is 10 and she cannot make a 1 time-unit layover.

SCORING:

Inputs 3-5: rj<sj for all j, i.e. all flights arrive after they depart.
Inputs 6-10: N,M≤5000
Inputs 11-20: No additional constraints.
Problem credits: Brandon Wang

Note: The time limit for this problem is 4s, two times the default.

Somebody has been grazing in Farmer John's (1≤G≤105) private gardens! Using his expert forensic knowledge, FJ has been able to determine the precise time each garden was grazed. He has also determined that there was a single cow that was responsible for every grazing incident.

In response to these crimes each of FJ's N (1≤N≤105) cows have provided an alibi that proves the cow was in a specific location at a specific time. Help FJ test whether each of these alibis demonstrates the cow's innocence.

A cow can be determined to be innocent if it is impossible for her to have travelled between all of the grazings and her alibi. Cows travel at a rate of 1 unit distance per unit time.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line of input will contain G and N separated by a space.
The next G lines contain the integers x, y, and t (−109≤x,y≤109;0≤t≤109) separated by a space describing the location and time of the grazing. It will always be possible for a single cow to travel between all grazings.

The next N lines contain x, y, and t (−109≤x,y≤109;0≤t≤109) separated by a space describing the location and time of each cow's alibi.

OUTPUT FORMAT (print output to the terminal / stdout):

Output a single integer: the number of cows with alibis that prove their innocence.

SAMPLE INPUT:

2 4
0 0 100
50 0 200
0 50 50
1000 1000 0
50 0 200
10 0 170

SAMPLE OUTPUT:

2
There were two grazings; the first at (0,0) at time 100 and the second at (50,0) at time 200.

The first cow's alibi does not prove her innocence. She has just enough time to arrive at the first grazing.

The second cow's alibi does prove her innocence. She is nowhere near any of the grazings.

Unfortunately for the third cow, being at the scene of the crime does not prove innocence.

Finally, the fourth cow is innocent because it's impossible to make it from her alibi to the final grazing in time.

SCORING:

Inputs 2-4: 1≤G,N≤103. Also, for both the fields and alibis, −106≤x,y≤106 and 0≤t≤106.
Inputs 5-11: No additional constraints.
Problem credits: Mark Gordon

Bessie has opened a bakery!

In her bakery, Bessie has an oven that can produce a cookie in tC units of time or a muffin in tM units of time (1≤tC,tM≤109). Due to space constraints, Bessie can only produce one pastry at a time, so to produce A cookies and B muffins, it takes A⋅tC+B⋅tM units of time.

Bessie's N (1≤N≤100) friends would each like to visit the bakery one by one. The ith friend will order ai (1≤ai≤109) cookies and bi (1≤bi≤109) muffins immediately upon entering. Bessie doesn't have space to store pastries, so she only starts making pastries upon receiving an order. Furthermore, Bessie's friends are very busy, so the ith friend is only willing to wait ci (ai+bi≤ci≤2⋅1018) units of time before getting sad and leaving.

Bessie really does not want her friends to be sad. With one mooney, she can upgrade her oven so that it takes one less unit of time to produce a cookie or one less unit of time to produce a muffin. She can't upgrade her oven a fractional amount of times, but she can choose to upgrade her oven as many times as she needs before her friends arrive, as long as the time needed to produce a cookie and to produce a muffin both remain strictly positive.

For each of T (1≤T≤100) test cases, please help Bessie find out the minimum amount of moonies that Bessie must spend so that her bakery can satisfy all of her friends.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains T, the number of test cases.
Each test case starts with one line containing N, tC, tM. Then, the next N lines each contain three integers ai,bi,ci.

Consecutive test cases are separated by newlines.

OUTPUT FORMAT (print output to the terminal / stdout):

The minimum amount of moonies that Bessie needs to spend for each test case, on separate lines.

SAMPLE INPUT:

2

3 7 9
4 3 18
2 4 19
1 1 6

5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22

SAMPLE OUTPUT:

11
6
In the first test case, Bessie can pay 11 moonies to decrease the time required to produce a cookie by 4 and a muffin by 7, so that her oven produces cookies in 3 units of time and muffins in 2 units of time. Then she can satisfy the first friend in 18 units of time, the second friend in 14 units of time, and the third friend in 5 units of time, so none of them will get sad and leave.

In the second test case, Bessie should decrease the time required to produce a cookie by 6 and a muffin by 0.

SCORING:

Inputs 2-4: N≤10,tC,tM≤1000
Inputs 5-11: No additional constraints.
Problem credits: Benjamin Qi