分类： 赛事资讯

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

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

5378 USA 4259 CHN 444 CAN 332 KOR 142 IND 125 ROU 88 MYS 77 SGP 72 TWN 64 VNM 61 HKG 55 GEO 50 GBR 47 IRN 46 DEU 40 POL 36 ARM 28 FRA 28 EGY 25 AUS 21 AZE 18 ISR 18 BLR 17 UKR 17 KAZ 15 GRC 14 HRV 14 BGD 13 SLV 13 NZL 12 TUR 12 TUN 12 THA 12 CHE 12 BRA 10 KGZ 10 JPN 10 IDN 8 RUS 8 NLD 7 ZAF 7 SWE 7 SRB 7 MNG 7 ESP 7 BGR 6 SYR 6 PHL 5 MEX 5 LTU 5 COL 5 ARE 4 TKM 4 PER 4 NPL 4 EST 3 SVK 3 NGA 2 PRK 2 MDA 2 MAR 2 LUX 2 KHM 2 ITA 2 IRL 2 CYP 2 CUB 1 VEN 1 UZB 1 TJK 1 SHN 1 PRT 1 PAK 1 MLT 1 MAC 1 LVA 1 IRQ 1 HUN 1 GUM 1 FIN 1 DOM 1 CZE 1 CHL 1 BOL 1 BEL 1 AUT 1 ARG 1 AFG

总共有 26969 份评分提交，按语言细分如下：
12396 C++17
6423 C++11
4386 Java
3561 Python 3.6.9
178 C
25 Python 2.7.17

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

USACO 2022 年 12 月学术活动，白金

白金组共有412人参加，其中247人为预科生。我们在本次比赛中看到了相当多的满分，其中有4个来自美国。最佳得分手的结果在这里。祝贺所有优秀选手取得的优异成绩！

1 Breakdown
查看问题 | 测试数据 | 解决方案
2 Making Friends
查看问题 | 测试数据 | 解决方案
3 Palindromes
查看问题 | 测试数据 | 解决方案

USACO 2022 年 12 月学术活动，金牌

黄金组共有1035人参加，其中预科生721人。所有在本次比赛中获得 700 分或更高分的参赛者将自动晋升为白金组别。所有晋升者的详细结果都在这里。

1 Bribing Friends
查看问题 | 测试数据 | 解决方案
2 Mountains
查看问题 | 测试数据 | 解决方案
3 Strongest Friendship Group
查看问题 | 测试数据 | 解决方案

USACO 2022 年 12 月学术活动，银奖

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

1 Barn Tree
查看问题 | 测试数据 | 解决方案
2 Circular Barn
查看问题 | 测试数据 | 解决方案
3 Range Reconstruction
查看问题 | 测试数据 | 解决方案

USACO 2022 年 12 月学术活动，铜奖

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

1 Cow College
查看问题 | 测试数据 | 解决方案
2 Feeding the Cows
查看问题 | 测试数据 | 解决方案
3 Reverse Engineering
查看问题 | 测试数据 | 解决方案

最后的评论

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

关于学术诚信在我们比赛中的重要性的简短说明：数百名参赛者因在本次比赛中作弊而被取消资格。作弊会被终身取消 USACO 晋级资格，教师、校长和大学招生人员通常不喜欢被告知在我们的比赛中作弊的学生（过去曾有学生因作弊而被学校开除）在 USACO 比赛中）。请尊重我们比赛的完整性。处理作弊是导致比赛结果发布时间过长的主要原因之一。

许多人为 USACO 比赛的质量和成功做出了贡献。为本次比赛提供帮助的人包括 Benjamin Qi、Freddie Tang、Mythreya Dharani、Timothy Feng、Nathan Wang、Sam Zhang、Joe Li、Larry Xing、Aryansh Shrivastava、Chongtian Ma、Jesse Choe、Yuval Vaknin、Danny Mittal、Nick Wu、Spencer Compton、Riya Arora、Jonathan Paulson、Claire Zhang、Andi Qu、Richard Qi、David Hu、Mark Chen、Daniel Zhang 和 Timothy Qian。还要感谢我们的翻译人员和克莱姆森 CCIT 为我们提供比赛基础设施。最后，我们感谢 USACO 赞助商的慷慨支持：Citadel、Ansatz、X-Camp、TwoSigma、EasyFunCoding 和 Jump Trading。

我们期待在 2023 年 1 月的比赛中再次见到大家。

编码愉快！

Elsie has a program that takes as input an array of N (1≤N≤100) variables b[0],…,b[N−1], each equal to zero or one, and returns the result of applying a sequence of if / else if / else statements on the input. Each statement examines the value of at most one input variable, and returns either zero or one. An example of such a program might be:

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
For example, if the input to the program above is "10" (that is, b[0]=1 and b[1]=0), then the output should be 1.

Elsie has told Bessie the correct output for M (1≤M≤100) different inputs. Bessie is now trying to reverse engineer Elsie's program. Unfortunately, Elsie might have lied; it may be the case that no program of the form above is consistent with what Elsie said.

For each of T (1≤T≤10) test cases, determine whether Elsie must be lying or not.

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

The first line contains T, the number of test cases.
Each test case starts with two integers N and M, followed by M lines, each containing a string of N zeros and ones representing an input (that is, the values of b[0]…b[N−1]) and an additional character (zero or one) representing the output. Consecutive test cases are separated by newlines.

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

For each test case, output "OK" or "LIE" on a separate line.

SAMPLE INPUT:

4

1 3
0 0
0 0
1 1

2 4
00 0
01 1
10 1
11 1

1 2
0 1
0 0

2 4
00 0
01 1
10 1
11 0

SAMPLE OUTPUT:

OK
OK
LIE
LIE
Here's a valid program for the first test case:

if (b[0] == 0) return 0;
else return 1;
Another valid program for the first test case:

if (b[0] == 1) return 1;
else return 0;
A valid program for the second test case:

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;
Clearly, there is no valid program corresponding to the third test case, because Elsie's program must always produce the same output for the same input.

It may be shown that there is no valid program corresponding to the last test case.

SCORING:

Inputs 2 and 3 have N=2.
Inputs 4 and 5 have M=2.
Inputs 6 through 12 have no additional constraints.

Problem credits: Benjamin Qi

Farmer John has N (1≤N≤105) cows, the breed of each being either a Guernsey or a Holstein. They have lined up horizontally with the cows occupying positions labeled from 1…N.

Since all the cows are hungry, FJ decides to plant grassy patches on some of the positions 1…N. Guernseys and Holsteins prefer different types of grass, so if Farmer John decides to plant grass at some location, he must choose to planting either Guernsey-preferred grass or Holstein-preferred grass --- he cannot plant both at the same location. Each patch of grass planted can feed an unlimited number of cows of the appropriate breed.

Each cow is willing to move a maximum of K (0≤K≤N−1) positions to reach a patch. Find the minimum number of patches needed to feed all the cows. Also, print a configuration of patches that uses the minimum amount of patches needed to feed the cows. Any configuration that satisfies the above conditions will be considered correct.

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

Each input contains T test cases, each describing an arrangement of cows. The first line of input contains T (1≤T≤10). Each of the T test cases follow.
Each test case starts with a line containing N and K. The next line will contain a string of length N, where each character denotes the breed of the ith cow (G meaning Guernsey and H meaning Holstein).

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

For each of the T test cases, please write two lines of output. For the first line, print the minimum number of patches needed to feed the cows. For the second line, print a string of length N that describes a configuration that feeds all the cows with the minimum number of patches. The ith character, describing the ith position, should be a '.' if there is no patch, a 'G' if there is a patch that feeds Guernseys, and a 'H' if it feeds Holsteins. Any valid configuration will be accepted.

SAMPLE INPUT:

6
5 0
GHHGG
5 1
GHHGG
5 2
GHHGG
5 3
GHHGG
5 4
GHHGG
2 1
GH

SAMPLE OUTPUT:

5
GHHGG
3
.GH.G
2
..GH.
2
...GH
2
...HG
2
HG

Note that for some test cases, there are multiple acceptable configurations that manage to feed all cows while using the minimum number of patches. For example, in the fourth test case, another acceptable answer would be:

.GH..

This corresponds to placing a patch feeding Guernseys on the 2nd position and a patch feeding Holsteins on the third position. This uses the optimal number of patches and ensures that all cows are within 3 positions of a patch they prefer.

SCORING:

Inputs 2 through 4 have N≤10.
Inputs 5 through 8 have N≤40.
Inputs 9 through 12 have N≤105.

Problem credits: Mythreya Dharani

Farmer John is planning to open a new university for cows!

There are N (1≤N≤105) cows who could potentially attend this university. Each cow is willing to pay a maximum tuition of ci (1≤ci≤106). Farmer John can set the tuition that all cows must pay to enroll. If this tuition is greater than the maximum a cow is willing to pay, then the cow will not attend the university. Farmer John wants to make the most possible money so he can pay his instructors a fair wage. Please determine how much money he can make, and how much tuition he should charge.

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

The first line contains N. The second line contains N integers c1,c2,…,cN, where ci is the maximum tuition cow i is willing to pay.

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

Please output the maximum amount of money Farmer John can make and the optimal tuition he should charge. If there are multiple solutions, output the solution with the smallest optimal tuition.
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" in Java, a "long long" in C/C++).

SAMPLE INPUT:

4
1 6 4 6

SAMPLE OUTPUT:

12 4
If Farmer John charges 4, then 3 cows will attend, allowing him to make 3⋅4=12.

SCORING:

Test cases 2 through 4 have ci≤1,000.
Test cases 5 through 8 have N≤5,000.
Test cases 9 through 12 have no additional constraints.
Problem credits: Freddie Tang

Bessie has an array a1,…,aN, where 1≤N≤300 and 0≤ai≤109 for all i. She won't tell you a itself, but she will tell you the range of each subarray of a. That is, for each pair of indices i≤j, Bessie tells you ri,j=maxa[i…j]−mina[i…j]. Given these values of r, please construct an array that could have been Bessie's original array. The values in your array should be in the range [−109,109].

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

The first line contains N.
Another N lines follow. The ith of these lines contains the integers ri,i,ri,i+1,…,ri,N.

It is guaranteed that there is some array a with values in the range [0,109] such that for all i≤j, ri,j=maxa[i…j]−mina[i…j].

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

Output one line containing N integers b1,b2,…,bN in the range [−109,109] representing your array. They must satisfy ri,j=maxb[i…j]−minb[i…j] for all i≤j.

SAMPLE INPUT:

3
0 2 2
0 1
0

SAMPLE OUTPUT:

1 3 2
For example, r1,3=maxa[1…3]−mina[1…3]=3−1=2.

SAMPLE INPUT:

3
0 1 1
0 0
0

SAMPLE OUTPUT:

0 1 1
This example satisfies the constraints for subtask 1.

SAMPLE INPUT:

4
0 1 2 2
0 1 1
0 1
0

SAMPLE OUTPUT:

1 2 3 2
This example satisfies the constraints for subtask 2.

SAMPLE INPUT:

4
0 1 1 2
0 0 2
0 2
0

SAMPLE OUTPUT:

1 2 2 0

SCORING:

Test 5 satisfies r1,N≤1.
Tests 6-8 satisfy ri,i+1=1 for all 1≤i<N.
Tests 9-14 satisfy no additional constraints.
Problem credits: Danny Mittal

Farmer John and his archnemesis Farmer Nhoj are playing a game in a circular barn. There are N (1≤N≤105) rooms in the barn, and the ith room initially contains ai cows (1≤ai≤5⋅106). The game is played as follows:
Both farmers will always be in the same room. After entering a room, each farmer takes exactly one turn, with Farmer John going first. Both farmers initially enter room 1.
If there are zero cows in the current room, then the farmer to go loses. Otherwise, the farmer to go chooses an integer P, where P must either be 1 or a prime number at most the number of cows in the current room, and removes P cows from the current room.
After both farmers have taken turns, both farmers move to the next room in the circular barn. That is, if the farmers are in room i, then they move to room i+1, unless they are in room N, in which case they move to room 1.
Determine the farmer that wins the game if both farmers play optimally.

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

The input contains T test cases. The first line contains T (1≤T≤1000). Each of the T test cases follow.
Each test case starts with a line containing N, followed by a line containing a1,…,aN.

It is guaranteed that the sum of all N is at most 2⋅105.

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

For each test case, output the farmer that wins the game, either "Farmer John" or "Farmer Nhoj."

SAMPLE INPUT:

5
1
4
1
9
2
2 3
2
7 10
3
4 9 4

SAMPLE OUTPUT:

Farmer Nhoj
Farmer John
Farmer John
Farmer John
Farmer Nhoj

For the first test case, Farmer John can remove 1, 2, or 3 cows from the first room. Whichever number he removes, Nhoj can remove the remaining cow(s), forcing FJ to lose when they circle back to the first room.

For the second test case, FJ can remove 5 cows, forcing Nhoj to work with only 4 cows remaining. Now, Nhoj can either remove 1, 2, or 3 cows. This is now similar to the first test case.

For the third and fourth test cases, FJ can immediately remove all the cows from the first room, forcing Nhoj to lose.

For the fifth test case, FJ can remove 1, 2, or 3, cows from the first room, and Nhoj can remove the rest right after. When they circle back around to the first room, FJ will lose.

SCORING:

Inputs 2-4 satisfy N=1.
Inputs 1, 2, and 5-7 satisfy ai≤1000.
Inputs 8-20 satisfy no additional constraints.
Problem credits: Chongtian Ma, Jesse Choe, and Yuval Vaknin

Note: the time limit for this problem is 4s, two times the default. The memory limit is also twice the default.
Farmer John's farm has N barns (2≤N≤2⋅105) numbered 1…N. There are N−1 roads, where each road connects two barns and it is possible to get from any barn to any other barn via some sequence of roads. Currently, the jth barn has hj hay bales (1≤hj≤109).

To please his cows, Farmer John would like to move the hay such that each barn has an equal number of bales. He can select any pair of barns connected by a road and order his farmhands to move any positive integer number of bales less than or equal to the number of bales currently at the first barn from the first barn to the second.

Please determine a sequence of orders Farmer John can issue to complete the task in the minimum possible number of orders. It is guaranteed that a sequence of orders exists.

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

The first line of input contains the value of N.

The second line of input contains the space-separated values of hj for j=1…N.

The final N−1 lines of input each contain two space-separated barn numbers ui vi, indicating that there is a bidirectional road connecting ui and vi.

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

Output the minimum possible number of orders, followed a sequence of orders of that length, one per line.
Each order should be formatted as three space-separated positive integers: the source barn, the destination barn, and the third describes the number of hay bales to move from the source to the destination.

If there are multiple solutions, output any.

SAMPLE INPUT:

4
2 1 4 5
1 2
2 3
2 4

SAMPLE OUTPUT:

3
3 2 1
4 2 2
2 1 1

In this example, there are a total of twelve hay bales and four barns, meaning each barn must have three hay bales at the end. The sequence of orders in the sample output can be verbally translated as below:

From barn 3 to barn 2, move 1 bale.
From barn 4 to barn 2, move 2 bales.
From barn 2 to barn 1, move 1 bale.

SCORING:

Test cases 2-8 satisfy N≤5000
Test cases 7-10 satisfy vi=ui+1
Test cases 11-16 satisfy no additional constraints
Problem credits: Aryansh Shrivastava

Farmer John has N cows (2≤N≤105), conveniently labeled 1…N. There are M (1≤M≤2⋅105) pairs of friends among these cows.
A group of cows is called a "friendship group" if every cow in the group is reachable from every other cow in the group via a chain of friendships that lies solely within the group (friendships connecting to cows outside the group have no impact). The "strength" of a friendship group is the minimum number of friends of any cow in the group within the group times the number of cows in the group (again, note that friendships connecting to cows outside the group do not count for this definition).

Please find the maximum strength over all friendship groups.

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

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

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

One line containing the maximum strength over all friendship groups.

SAMPLE INPUT:

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

SAMPLE OUTPUT:

12
The maximum strength can be observed to be with the group of cows numbered 1,2,3,4. The minimum number of friends of any cow in this group within the group is 3, so the answer is 4⋅3=12.

SCORING:

For 1≤T≤3, test case T satisfies N≤16.
For 4≤T≤9, test case T satisfies N≤1000.
For 10≤T≤20, test case T satisfies no additional constraints.
Problem credits: Benjamin Qi