分类： 赛事资讯

There are NN (1≤N≤20001≤N≤2000) evenly spaced mountains in a row on the edge of Farmer John's farm. These can be expressed as an array of heights h1,h2,…,hNh1,h2,…,hN. For a mountain ii, you can see another mountain jj if there are no mountains strictly higher than the line of sight connecting the tops of mountain jj and ii. Formally, for two mountains i<ji<j, they can see each other if there is no kk such that i<k<ji<k<j and (k,hk)(k,hk) is above the line segment connecting (i,hi)(i,hi) and (j,hj)(j,hj). There are QQ (1≤Q≤20001≤Q≤2000) updates where the height of one mountain increases. Find the total number of unordered pairs of mountains that see each other after each update.

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

Line 11 contains NN.Line 22 contains NN heights h1,h2,…,hNh1,h2,…,hN (for each ii, 0≤hi≤1090≤hi≤109).

Line 33 contains QQ.

Lines 44 to 3+Q3+Q contain xx, yy (1≤x≤N1≤x≤N, 1≤y1≤y) where xx is the index of the mountain and yy is the amount the height increases by. It is guaranteed that the new height of the mountain is at most 109109.

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

QQ lines, with the total number of unordered pairs of mountains that see each other after each update.

SAMPLE INPUT:

5
2 4 3 1 5
3
4 3
1 3
3 2

SAMPLE OUTPUT:

7
10
7

Initially, the following pairs of mountains can see each other: (1,2)(1,2), (2,3)(2,3), (2,5)(2,5), (3,4)(3,4), (3,5)(3,5), (4,5)(4,5), a total of 66.

After the first update, mountain 44 has a height of 44, which doesn't block any visibility but does make it so that 44 can now see 22, making the new answer 77.

After the second update, mountain 11 has a height of 55, which doesn't block any visibility but does make it so that 11 can now see 33, 44, and 55, making the new answer 1010.

After the third update, mountain 33 has a height of 55, which blocks mountain 11 from seeing mountain 44, blocks mountain 22 from seeing mountains 44 and 55, and doesn't allow itself to see any more mountains since it can already see all of them, making the new answer 77.

SCORING:

Tests 2-5 satisfy N,Q≤100N,Q≤100.

Tests 6-11 satisfy Q≤10Q≤10.

Tests 12-21 have no additional constraints.

Problem credits: Joe Li and Larry Xing

Bessie wants to watch Bovine Genomics: The Documentary, but she doesn’t want to go alone. Unfortunately, her friends aren’t enthusiastic enough to go with her! Therefore, Bessie needs to bribe her friends to accompany her to the movie theater. She has two tools in her bribery arsenal: mooney and ice cream cones.

Bessie has NN (1≤N≤20001≤N≤2000) friends. However, not all friends are created equal! Friend ii has a popularity score of PiPi (1≤Pi≤20001≤Pi≤2000), and Bessie wants to maximize the sum of the popularity scores of the friends accompanying her. Friend ii is only willing to accompany Bessie if she gives them CiCi (1≤Ci≤20001≤Ci≤2000) moonies. They will also offer her a discount of 11 mooney if she gives them XiXi (1≤Xi≤20001≤Xi≤2000) ice cream cones. Bessie can get as many whole-number discounts as she wants from a friend, as long as the discounts don’t cause the friend to give her mooney.

Bessie has AA moonies and BB ice cream cones at her disposal (0≤A,B≤20000≤A,B≤2000). Help her determine the maximum sum of the popularity scores she can achieve if she spends her mooney and ice cream cones optimally!

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

Line 11 contains three numbers NN, AA, and BB, representing the number of friends, the amount of mooney, and the number of ice cream cones Bessie has respectively.

Each of the next NN lines contains three numbers, PiPi, CiCi, and XiXi, representing popularity (PiPi), mooney needed to bribe friend ii to accompany Bessie (CiCi), and ice cream cones needed to receive a discount of 11 mooney from friend ii (XiXi).

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

Output the maximum sum of the popularity scores of the friends accompanying Bessie, assuming she spends her moonie and ice cream cones optimally.

SAMPLE INPUT:

3 10 8
5 5 4
6 7 3
10 6 3

SAMPLE OUTPUT:

15

Bessie can give 44 moonies and 44 ice cream cones to cow 11, and 66 moonies and 33 ice cream cones to cow 33, in order to get cows 11 and 33 to accompany her for a total popularity of 5+10=155+10=15.

SCORING:

Test cases 2-4 satisfy N≤5N≤5 and Ci=1Ci=1

Test cases 5-7 satisfy B=0B=0

Test cases 8-10 satisfy N,A,B,Pi,Ci,Xi≤50N,A,B,Pi,Ci,Xi≤50

Test cases 11-15 satisfy N,A,B,Pi,Ci,Xi≤200N,A,B,Pi,Ci,Xi≤200

Test cases 16-20 satisfy no further constraints

Problem credits: Timothy Feng, Nathan Wang, and Sam Zhang

The United Cows of Farmer John (UCFJ) are at the annual hoofball championships! UCFJ's team of NN(1≤N≤7500)(1≤N≤7500) cows won a gold medal in hoofball, narrowly beating out Farmer Nhoj's team.

The cows have already lined up for the awards ceremony. They want FJ to take N(N+1)2N(N+1)2 group photos, one for each contiguous subsequence of the lineup.

However, FJ, as the coach of the team, is very particular about how the cows should be lined up. Specifically, he refuses to take a picture of a subsequence unless it forms a *palindrome,* meaning that the breed of the iith cow from the left end of the subsequence must be the same as the breed of the iith cow from the right end of the subsequence for all positive integers iiless than or equal to the length of the subsequence. Each cow's breed is either Guernsey or Holstein.

For each of the N(N+1)2N(N+1)2 contiguous subsequences of the lineup, count the minimum number of transpositions necessary to rearrange that subsequence into a palindrome (or −1−1if it is impossible to do so). A single transposition consists of taking two adjacent cows in the subsequence and swapping them. Output the sum of all these counts.

Note that the number of transpositions needed is calculated independently for each contiguous subsequence (the cows return to their initial positions between photos).

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

The lineup, represented by a string of Gs and Hs of length NN.

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

The sum of the aforementioned quantity over all N(N+1)2N(N+1)2contiguous subsequences of the lineup.

SAMPLE INPUT:

GHHGGHHGH

SAMPLE OUTPUT:

The first four contiguous subsequences are G, GH, GHH, and GHHG. Both G and GHHG are already palindromes, so they contribute 00 to the sum. GHH can be rearranged into a palindrome using a single transposition, so it contributes 11 to the sum. GH cannot be rearranged into a palindrome using any number of transpositions, so it contributes −1−1 to the sum.

Another contiguous subsequence that contributes to the sum is HHGG. This can be rearranged into a palindrome using two transpositions.

SCORING:

There are fifteen test cases aside from the sample, one for each of N∈[100,200,500,1000,2000,5000,5000,5000,5000,5000,7500,7500,7500,7500,7500]N∈[100,200,500,1000,2000,5000,5000,5000,5000,5000,7500,7500,7500,7500,7500].

Problem credits: Mythreya Dharani and Benjamin Qi

Note: the time limit for this problem is 3s, 50% larger than the default. The memory limit is twice the default.

There are initially MM (1≤M≤2⋅1051≤M≤2⋅105) pairs of friends among FJ's NN (2≤N≤2⋅1052≤N≤2⋅105) cows labeled 1…N1…N. The cows are leaving the farm for vacation one by one. On day ii, the ii-th cow leaves the farm, and all pairs of the ii-th cow's friends still present on the farm become friends. How many new friendships are formed in total?

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

The first line contains NN and MM.The next MM lines contain two integers uiui and vivi denoting that cows uiui and vivi are friends (1≤ui,vi≤N1≤ui,vi≤N, ui≠viui≠vi). No unordered pair of cows appears more than once.

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

One line containing the total number of new friendships formed. Do not include pairs of cows that were already friends at the beginning.

SAMPLE INPUT:

7 6
1 3
1 4
7 1
2 3
2 4
3 5

SAMPLE OUTPUT:

5

On day 11, three new friendships are formed: (3,4)(3,4), (3,7)(3,7), and (4,7)(4,7).

On day 33, two new friendships are formed: (4,5)(4,5) and (5,7)(5,7).

SCORING:

Test cases 2-3 satisfy N≤500N≤500.

Test cases 4-7 satisfy N≤104N≤104.

Test cases 8-17 satisfy no additional constraints.
Problem credits: Benjamin Qi

Note: the time limit for this problem is 3s, 50% larger than the default.

Farmer John's farm can be represented as a directed weighted graph, with roads (edges) connecting different nodes, and the weight of each edge being the time required to travel along the road. Every day, Bessie likes to travel from the barn (located at node 11) to the fields (located at node NN) traveling along exactly KK roads, and wants to reach the fields as quickly as possible under this constraint. However, at some point, the roads stop being maintained, and one by one, they start breaking down, becoming impassable. Help Bessie find the shortest path from the barn to the fields at all moments in time!

Formally, we start with a complete weighted directed graph on NN vertices (1≤N≤3001≤N≤300) with N2N2 edges: one edge for every pair (i,j)(i,j) for 1≤i,j≤N1≤i,j≤N (note that there are NN self loops). After each removal, output the minimum weight of any path from 11 to NN that passes through exactly KK (not necessarily distinct) edges (2≤K≤82≤K≤8). Note that after the ii-th removal, the graph has N2−iN2−i edges left.

The weight of a path is defined as the sum of the weights of all of the edges on the path. Note that a path can contain multiple of the same edge and multiple of the same vertex, including vertices 11 and NN.

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

The first line contains NN and KK.The next NN lines contain NN integers each. The jj-th integer of ii-th line is wijwij (1≤wij≤1081≤wij≤108).

Then N2N2 additional lines follow, each containing two integers ii and jj (1≤i,j≤N1≤i,j≤N). Every pair of integers appears exactly once.

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

Exactly N2N2 lines, the minimum weight KK-path after each removal. If no KK-path exists then output −1−1.

SAMPLE INPUT:

3 4
10 4 4
9 5 3
2 1 6
3 1
2 3
2 1
3 2
2 2
1 3
3 3
1 1
1 2

SAMPLE OUTPUT:

11
18
22
22
22
-1
-1
-1
-1

After the first removal, the shortest 44-path is:
1 -> 2 -> 3 -> 2 -> 3
After the second removal, the shortest 44-path is:
1 -> 3 -> 2 -> 1 -> 3

After the third removal, the shortest 44-path is:
1 -> 3 -> 3 -> 3 -> 3

After six removals, there is no longer a 44-path.

SCORING:

For 2≤T≤142≤T≤14, test case TT satisfies K=⌊(T+3)/2⌋K=⌊(T+3)/2⌋.

Problem credits: Benjamin Qi

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

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

4773 美国 3312 CHN 321 KOR 321 CAN 140 IND 98 ROU 87 SGP
81 VNM 73 TWN 72 MYS 62 GEO 57 DEU 52 ISR 48 HKG
42 ARM 36 AUS 31 EGY 30 POL 30 GBR 30 BLR 24 JPN
23 FRA 23 AZE 18 NZL 17 IRN 15 TUR 14 MEX 14 COL
13 KAZ 13 ESP 12 SLV 12 MNG 11 SYR 10 TUN 10 RUS
10 IDN 10 GRC 10 CUB 9 BGD 8 NLD 8 EST 7 UZB
7 SRB 7 PHL 7 PAK 7 CHE 7 BGR 6 ZAF 6 LTU
6 KGZ 6 HRV 5 UKR 5 THA 5 ARE 4 SWE 4 PER
4 BRA 3 TJK 3 NPL 3 IRL 3 BEL 2 TKM 2 MLT
2 LKA 2 ITA 2 ISL 2 ETH 1 VEN 1 SVN 1 SVK
1 SAU 1 PRT 1 PRK 1 NOR 1 NGA 1 MDA 1 KIR
1 KHM 1 GUM 1 FIN 1 CZE 1 CYP 1 CHL 1 BMU
1 BLZ 1 BDI 1 AUT 1 ARG 1 AFG

总共有 27301 份评分提交，按语言细分如下：
12771 C++17
5867 C++11
4769 Java
3735 Python 3.6.9
131 C
28 Python 2.7.17

以下是白金、黄金、白银和铜牌比赛的详细结果。您还将找到每个问题的解决方案和测试数据，并且通过单击任何问题，您可以练习在“分析模式”下重新提交解决方案。 如果您已登录，您还将在下方看到您自己的具体结果以及您参加的比赛。

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

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

1 Tractor Paths
查看问题 | 测试数据 | 解决方案
2 Mana Collection
查看问题 | 测试数据 | 解决方案
3 Subtree Activation
查看问题 | 测试数据 | 解决方案

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

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

1 Find and Replace
查看问题 | 测试数据 | 解决方案
2 Lights Off
查看问题 | 测试数据 | 解决方案
3 Moo Route
查看问题 | 测试数据 | 解决方案

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

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

1 Find and Replace
查看问题 | 测试数据 | 解决方案
2 Following Directions
查看问题 | 测试数据 | 解决方案
3 Moo Route
查看问题 | 测试数据 | 解决方案

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

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

1 Leaders
查看问题 | 测试数据 | 解决方案
2 Air Cownditioning II
查看问题 | 测试数据 | 解决方案
3 Moo Operations
查看问题 | 测试数据 | 解决方案

最后的评论

那些寻求微不足道的问题的人需要看看这场比赛以外的其他地方。尽管如此，尽管每个部门都有一系列极具挑战性的任务，但我们仍然看到了令人印象深刻的高分。

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

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

期待本赛季第三场比赛与大家再次相见！

编码愉快！

Bessie is using the latest and greatest innovation in text-editing software, miV! Its powerful find-and-replace feature allows her to find all occurrences of a lowercase English letter c and replace each with a nonempty string of lowercase letters s. For example, given the string "ball", if Bessie selects c to be 'l' and s to be "na", the given string transforms into "banana".

Bessie starts with the string "a" and transforms it using a number of these find-and-replace operations, resulting in a final string S. Since S could be massive, she wants to know, given l and r with 1≤l≤r≤min(|S|,1018), what Sl…r (the substring of S from the l-th to the r-th character inclusive) is.

It is guaranteed that the sum of |s| over all operations is at most 2⋅105, and that r−l+1≤2⋅105.

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

The first line contains l, r, and the number of operations.
Each subsequent line describes one operation and contains c and s for that operation. All characters are in the range 'a' through 'z'.

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

Output the string Sl…r on a single line.

SAMPLE INPUT:
3 8 4
a ab
a bc
c de
b bbb

SAMPLE OUTPUT:

bdebbb
The string is transformed as follows:

a→ab→bcb→bdeb→bbbdebbb

SCORING:

Inputs 2-7: ∑|s|,r−l+1≤2000
Inputs 8-15: No additional constraints.
Problem credits: Benjamin Qi

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

Bessie wants to go to sleep, but the farm's lights are keeping her awake. How can she turn them off?

Bessie has two bit strings of length N (2≤N≤20), representing a sequence of lights and a sequence of switches, respectively. Each light is either on (1) or off (0). Each switch is either active (1) or inactive (0).

A *move* consists of the following sequence of operations:

Toggle exactly one switch (set it to active if it is inactive, or vice versa).
For each active switch, toggle the state of the corresponding light (turn it off if it is on, or vice versa).
Cyclically rotate the switches to the right by one. Specifically, if the bit string corresponding to the switches is initially s0s1…sN−1 then it becomes sN−1s0s1…sN−2.
For T (1≤T≤2⋅105) instances of the problem above, count the minimum number of moves required to turn all the lights off.

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

First line contains T and N.
Next T lines each contain a pair of length-N bit strings.

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

For each pair, the minimum number of moves required to turn all the lights off.

SAMPLE INPUT:

4 3
000 101
101 100
110 000
111 000

SAMPLE OUTPUT:

0
1
3
2
First test case: the lights are already all off.
Second test case: We flip the third switch on the first move.
Third test case: we flip the first switch on the first move, the second switch on the second move, and the second switch again on the third move.
Fourth test case: we flip the first switch on the first move and the third switch on the second move.
It can be shown that in each case this is the minimal number of moves necessary.

SAMPLE INPUT:

1 10
1100010000 1000011000

SAMPLE OUTPUT:

2
It can be shown that 2 moves are required to turn all lights off.
We flip the seventh switch on the first move and then again on the second move.
SCORING:
Inputs 3-5: N≤8
Inputs 6-13: N≤18
Inputs 14-20: No additional constraints.
Problem credits: William Yue, Eric Yang, and Benjamin Qi

Farmer Nhoj dropped Bessie in the middle of nowhere! At time t=0, Bessie is located at x=0 on an infinite number line. She frantically searches for an exit by moving left or right by 1 unit each second. However, there actually is no exit and after T seconds, Bessie is back at x=0, tired and resigned.

Farmer Nhoj tries to track Bessie but only knows how many times Bessie crosses x=.5,1.5,2.5,…,(N−1).5, given by an array A0,A1,…,AN−1 (1≤N≤105, 1≤Ai≤106). Bessie never reaches x>N nor x<0.

In particular, Bessie's route can be represented by a string of T=∑N−1i=0Ai Ls and Rs where the ith character represents the direction Bessie moves in during the ith second. The number of direction changes is defined as the number of occurrences of LRs plus the number of occurrences of RLs.

Please help Farmer Nhoj count the number of routes Bessie could have taken that are consistent with A and minimize the number of direction changes. It is guaranteed that there is at least one valid route.

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

The first line contains N. The second line contains A0,A1,…,AN−1.
OUTPUT FORMAT (print output to the terminal / stdout):
The number of routes Bessie could have taken, modulo 109+7.

SAMPLE INPUT:

2
4 6

SAMPLE OUTPUT:

2
Bessie must change direction at least 5 times. There are two routes corresponding to Bessie changing direction exactly 5 times:

RRLRLLRRLL
RRLLRRLRLL

SCORING:

Inputs 2-4: N≤2 and max(Ai)≤103
Inputs 5-7: N≤2
Inputs 8-11: max(Ai)≤103
Inputs 12-21: No additional constraints.
Problem credits: Brandon Wang, Claire Zhang, and Benjamin Qi