Google Code Jam Archive — Qualification Round 2021 problems
Overview
Code Jam finally turned 18 this year — it's now eligible for the World Finals! To celebrate, the Qualification Round jammed out for 3 hours longer than usual, for the first-ever 30-hour round.
For the second time, the Qualification Round had five problems, with the first one being tied to a follow-up problem. Reversort and Reversort Engineering both versed on investigating a quirky sorting algorithm and were inverses of each other in a sense. Reversort required careful coding only, but Reversort Engineering involved an insight and working out some math. Moons and Umbrellas featured an early appearance of Cody-Jamal with a problem that could be solved greedily. However, if you wanted to go for the extra credit, a completely different approach was needed. In case you haven't noticed, there was no way the extra credit could help you or prevent you from advancing, so it really was just extra.
The last two problems were significantly harder to tackle, as usual. Median Sort was an interactive problem that required adapting your knowledge of sorting algorithms and possibly putting information theory to work. Finally, Cheating Detection was an unusual problem, and not only because we don't do cheating detection for the Qualification Round. There were multiple ways to try to pinpoint the cheater, all based on finding the signal with the least noise.
The first hour and a half of the contest had a scoreboard blackout due to a configuration mistake that was hard to pinpoint. This did not deter our participants from submitting and scoring lots of points during that time. When the scoreboard appeared, there were already thousands of contestants on it. One of them was ksun48 who was the only competitor to achieve a perfect score within the first hour.
In the end, 37398 contestants submitted something, with 33853 getting points. When the final results were revealed, 25961 scored at least 30 points and advanced to Round 1. 644 contestants went beyond and managed to score a perfect 100 points, with 436 of them even getting to 101 due to the extra credit in Moons and Umbrellas.
Thank you for joining us for another year of Code Jam! If you got at least 30 points, congratulations, you have advanced! We will see you in any of the Round 1s, starting with Round 1A in two weeks. (You can keep participating in Round 1s until you advance to Round 2.) If you did not score enough points to get to Round 1 this time, we hope you'll join us in 2022! In the mean time, to improve your skills, you can practice with lots of old problems from our archive. In addition, Kick Start registration remains open and you can jump in at any round for some live-contest experience! If you want additional help, join our mailing list and ask questions!
Cast
Reversort: Written by the Code Jam team. Prepared by Pablo Heiber.
Moons and umbrellas: Written by Sherry Wu. Prepared by Timothy Buzzelli.
Reversort Engineering: Written by Pablo Heiber. Prepared by Swapnil Gupta.
Median Sort: Written and prepared by Pablo Heiber.
Cheating Detection: Written by Ian Tullis. Prepared by Ian Tullis and Timothy Buzzelli.
Solutions and other problem preparation and review by Andy Huang, Darcy Best, Ian Tullis, Jing Wang, Liang Bai, Max Ward, Md Mahbubul Hasan, Mohamed Yosri Ahmed, Nafis Sadique, Pablo Heiber, Sherry Wu, Swapnil Gupta, Timothy Buzzelli, and Yeabkal Wubshit.
Analysis authors:
- Reversort: Md Mahbubul Hasan.
- Moons and umbrellas: Pablo Heiber.
- Reversort Engineering: Swapnil Gupta.
- Median Sort: Pablo Heiber.
- Cheating Detection: Pablo Heiber.
A. Reversort
Problem
Note: The main parts of the statements of the problems "Reversort" and "Reversort Engineering" are identical, except for the last paragraph. The problems can otherwise be solved independently.
Reversort is an algorithm to sort a list of distinct integers in increasing order. The algorithm is based on the "Reverse" operation. Each application of this operation reverses the order of some contiguous part of the list.
The pseudocode of the algorithm is the following:
Reversort(L):
for i := 1 to length(L) - 1
j := position with the minimum value in L between i and length(L), inclusive
Reverse(L[i..j])
After $$$i-1$$$ iterations, the positions $$$1,\;2,\;\dots,\;i-1$$$ of the list contain the $$$i-1$$$ smallest elements of L, in increasing order. During the $$$i$$$-th iteration, the process reverses the sublist going from the $$$i$$$-th position to the current position of the $$$i$$$-th minimum element. That makes the $$$i$$$-th minimum element end up in the $$$i$$$-th position.
For example, for a list with $$$4$$$ elements, the algorithm would perform $$$3$$$ iterations. Here is how it would process $$$L = [4, 2, 1, 3]$$$:
- $$$i = 1,~ j = 3 \longrightarrow L = [1, 2, 4, 3]$$$
- $$$i = 2,~ j = 2 \longrightarrow L = [1, 2, 4, 3]$$$
- $$$i = 3,~ j = 4 \longrightarrow L = [1, 2, 3, 4]$$$
The most expensive part of executing the algorithm on our architecture is the Reverse operation. Therefore, our measure for the cost of each iteration is simply the length of the sublist passed to Reverse, that is, the value $$$j - i + 1$$$. The cost of the whole algorithm is the sum of the costs of each iteration.
In the example above, the iterations cost $$$3$$$, $$$1$$$, and $$$2$$$, in that order, for a total of $$$6$$$.
Given the initial list, compute the cost of executing Reversort on it.
Input
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow. Each test case consists of 2 lines. The first line contains a single integer $$$\mathbf{N}$$$, representing the number of elements in the input list. The second line contains $$$\mathbf{N}$$$ distinct integers $$$\mathbf{L_1}$$$, $$$\mathbf{L_2}$$$, ..., $$$\mathbf{L_N}$$$, representing the elements of the input list $$$L$$$, in order.
Output
For each test case, output one line containing Case #$$$x$$$: $$$y$$$, where $$$x$$$
is the test case number (starting from 1) and $$$y$$$ is the total cost of executing
Reversort on the list given as input.
Limits
Time limit: 10 seconds.
Memory limit: 1 GB.
Test Set 1 (Visible Verdict)
$$$1 \le \mathbf{T} \le 100$$$.
$$$2 \le \mathbf{N} \le 100$$$.
$$$1 \le \mathbf{L_i} \le N$$$, for all $$$i$$$.
$$$\mathbf{L_i} \ne \mathbf{L_j}$$$, for all $$$i \ne j$$$.
Sample
3 4 4 2 1 3 2 1 2 7 7 6 5 4 3 2 1
Case #1: 6 Case #2: 1 Case #3: 12
Sample Case #1 is described in the statement above.
In Sample Case #2, there is a single iteration, in which Reverse is applied to a sublist of size 1. Therefore, the total cost is 1.
In Sample Case #3, the first iteration reverses the full list, for a cost of 7. After that, the list is already sorted, but there are 5 more iterations, each of which contributes a cost of 1.
B. Moons and Umbrellas
Problem
Cody-Jamal is working on his latest piece of abstract art: a mural consisting of a row of waning moons and closed umbrellas. Unfortunately, greedy copyright trolls are claiming that waning moons look like an uppercase C and closed umbrellas look like a J, and they have a copyright on CJ and JC. Therefore, for each time CJ appears in the mural, Cody-Jamal must pay $$$\mathbf{X}$$$, and for each time JC appears in the mural, he must pay $$$\mathbf{Y}$$$.
Cody-Jamal is unwilling to let them compromise his art, so he will not change anything already painted. He decided, however, that the empty spaces he still has could be filled strategically, to minimize the copyright expenses.
For example, if CJ?CC? represents the current state of the mural,
with C representing a waning moon, J representing a closed umbrella,
and ? representing a space that still needs to be painted with either
a waning moon or a closed umbrella, he could finish the mural as
CJCCCC, CJCCCJ, CJJCCC, or CJJCCJ.
The first and third options would require paying $$$\mathbf{X} + \mathbf{Y}$$$ in copyrights,
while the second and fourth would require paying $$$2 \cdot \mathbf{X} + \mathbf{Y}$$$.
Given the costs $$$\mathbf{X}$$$ and $$$\mathbf{Y}$$$ and a string representing the current state of the mural, how much does Cody-Jamal need to pay in copyrights if he finishes his mural in a way that minimizes that cost?
Input
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ lines follow. Each line contains two integers $$$\mathbf{X}$$$ and $$$\mathbf{Y}$$$ and a string $$$\mathbf{S}$$$ representing the two costs and the current state of the mural, respectively.
Output
For each test case, output one line containing Case #$$$x$$$: $$$y$$$,
where $$$x$$$ is the test case number (starting from 1) and $$$y$$$ is the
minimum cost that Cody-Jamal needs to pay in copyrights for a finished mural.
Limits
Time limit: 10 seconds.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
Each character of $$$\mathbf{S}$$$ is either C, J, or ?.
Test Set 1 (Visible Verdict)
$$$1 \le$$$ the length of $$$\mathbf{S}$$$ $$$\le 10$$$.
$$$1 \le \mathbf{X} \le 100$$$.
$$$1 \le \mathbf{Y} \le 100$$$.
Test Set 2 (Visible Verdict)
$$$1 \le$$$ the length of $$$\mathbf{S}$$$ $$$\le 1000$$$.
$$$1 \le \mathbf{X} \le 100$$$.
$$$1 \le \mathbf{Y} \le 100$$$.
Extra credit!
What if some copyright holders could pay Cody-Jamal for the advertisement instead of being paid? Cody-Jamal getting paid is represented by a negative cost.
Test Set 3 (Hidden Verdict)
$$$1 \le$$$ the length of $$$\mathbf{S}$$$ $$$\le 1000$$$.
$$$-100 \le \mathbf{X} \le 100$$$.
$$$-100 \le \mathbf{Y} \le 100$$$.
Sample
Note: there are additional samples that are not run on submissions down below.4 2 3 CJ?CC? 4 2 CJCJ 1 3 C?J 2 5 ??J???
Case #1: 5 Case #2: 10 Case #3: 1 Case #4: 0
Sample Case #1 is the one explained in the problem statement. The minimum cost is $$$\mathbf{X} + \mathbf{Y} = 2 + 3 = 5$$$.
In Sample Case #2, Cody-Jamal is already finished, so he does not have a choice.
There are two CJs and one JC in his mural.
In Sample Case #3, substituting either C or J results
in one CJ either from the second and third characters or the first
and second characters, respectively.
In Sample Case #4, Cody-Jamal can finish his mural with all Js.
Since that contains no instance of CJ nor JC, it yields
no copyright cost.
Additional Sample - Test Set 3
The following additional sample fits the limits of Test Set 3. It will not be run against your submitted solutions.1 2 -5 ??JJ??
Case #1: -8
In Sample Case #1 for Test Set 3, Cody-Jamal can finish his mural optimally
as JCJJCC or JCJJJC. Either way, there is one
CJ and two JCs in his mural.
C. Reversort Engineering
Problem
Note: The main parts of the statements of the problems "Reversort" and "Reversort Engineering" are identical, except for the last paragraph. The problems can otherwise be solved independently.
Reversort is an algorithm to sort a list of distinct integers in increasing order. The algorithm is based on the "Reverse" operation. Each application of this operation reverses the order of some contiguous part of the list.
The pseudocode of the algorithm is the following:
Reversort(L):
for i := 1 to length(L) - 1
j := position with the minimum value in L between i and length(L), inclusive
Reverse(L[i..j])
After $$$i-1$$$ iterations, the positions $$$1,\;2,\;\dots,\;i-1$$$ of the list contain the $$$i-1$$$ smallest elements of L, in increasing order. During the $$$i$$$-th iteration, the process reverses the sublist going from the $$$i$$$-th position to the current position of the $$$i$$$-th minimum element. That makes the $$$i$$$-th minimum element end up in the $$$i$$$-th position.
For example, for a list with $$$4$$$ elements, the algorithm would perform $$$3$$$ iterations. Here is how it would process $$$L = [4, 2, 1, 3]$$$:
- $$$i = 1,~ j = 3 \longrightarrow L = [1, 2, 4, 3]$$$
- $$$i = 2,~ j = 2 \longrightarrow L = [1, 2, 4, 3]$$$
- $$$i = 3,~ j = 4 \longrightarrow L = [1, 2, 3, 4]$$$
The most expensive part of executing the algorithm on our architecture is the Reverse operation. Therefore, our measure for the cost of each iteration is simply the length of the sublist passed to Reverse, that is, the value $$$j - i + 1$$$. The cost of the whole algorithm is the sum of the costs of each iteration.
In the example above, the iterations cost $$$3$$$, $$$1$$$, and $$$2$$$, in that order, for a total of $$$6$$$.
You are given a size $$$\mathbf{N}$$$ and a cost $$$\mathbf{C}$$$. Find a list of $$$\mathbf{N}$$$ distinct integers between 1 and $$$\mathbf{N}$$$ such that the cost of applying Reversort to it is exactly $$$\mathbf{C}$$$, or say that there is no such list.
Input
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ lines follow. Each line describes a test case with two integers $$$\mathbf{N}$$$ and $$$\mathbf{C}$$$, the size of the wanted list and the desired cost, respectively.
Output
For each test case, if there
is no list of size $$$\mathbf{N}$$$ such that applying Reversort to it costs
exactly $$$\mathbf{C}$$$, output one line containing Case #$$$x$$$: IMPOSSIBLE, where $$$x$$$ is the
test case number (starting from 1).
Otherwise, output one line containing
Case #$$$x$$$: $$$y_1$$$ $$$y_2$$$ ... $$$y_\mathbf{N}$$$,
where $$$x$$$ is the
test case number (starting from 1) and each $$$y_i$$$ is a distinct integer between
$$$1$$$ and $$$\mathbf{N}$$$, representing the $$$i$$$-th element of one such possible list.
If there are multiple solutions, you may output any one of them. (See "What if a test case has multiple correct solutions?" in the Competing section of the FAQ.) This information about multiple solutions will not be explicitly stated in the remainder of the 2021 contest.
Limits
Time limit: 10 seconds.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$1 \le \mathbf{C} \le 1000$$$.
Test Set 1 (Visible Verdict)
$$$2 \le \mathbf{N} \le 7$$$.
Test Set 2 (Visible Verdict)
$$$2 \le \mathbf{N} \le 100$$$.
Sample
5 4 6 2 1 7 12 7 2 2 1000
Case #1: 4 2 1 3 Case #2: 1 2 Case #3: 7 6 5 4 3 2 1 Case #4: IMPOSSIBLE Case #5: IMPOSSIBLE
Sample Case #1 is described in the statement above.
In Sample Case #2, the algorithm runs for only one iteration on the proposed output. In that iteration, reverse is applied to a sublist of size 1, therefore, its cost is 1.
In Sample Case #3, the first iteration reverses the full list, for a cost of 7. After that,
the list is already sorted, but there are 5 more iterations, each of which contributes a cost
of 1. Another valid output would be 7 5 4 3 2 1 6. For that output, the first
iteration has a cost of 6, the last one has a cost of 2, and all others have a cost of 1.
In Sample Case #4, Reversort will necessarily perform 6 iterations, each of which will have a cost of at least 1, so there is no way the total cost can be as low as required.
D. Median Sort
Problem
You want to sort $$$\mathbf{N}$$$ distinct items, $$$x_1, x_2, \dots, x_\mathbf{N}$$$. Unfortunately, you do not have a way of comparing two of these items. You only have a way to, given three of them, find out which one is the median, that is, which one is neither the minimum nor the maximum among the three.
For example, suppose $$$\mathbf{N} = 5$$$ and you know that:
- $$$x_1$$$ is the median of $$$\{x_1, x_2, x_3\}$$$
- $$$x_2$$$ is the median of $$$\{x_2, x_3, x_4\}$$$
- $$$x_3$$$ is the median of $$$\{x_3, x_4, x_5\}$$$
Then, it is guaranteed that the sorted order of the elements is either $$$x_4, x_2, x_1, x_3, x_5$$$ or its reverse $$$x_5, x_3, x_1, x_2, x_4$$$. Notice that by knowing only medians, it is impossible to distinguish the order of any list from its reverse, since the median question has the same result for any three elements in both cases.
Your program will have to find the order of $$$\mathbf{T}$$$ lists of $$$\mathbf{N}$$$ elements using at most $$$\mathbf{Q}$$$ median questions in total (or $$$\mathbf{Q} / \mathbf{T}$$$ queries per list on average). In each case, finding either the right order or its reverse is considered correct. The order for each case is generated uniformly at random from all possible orders, and independently of any other information.
Input and output
This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.
Initially, the judge will send you a single line containing three integers $$$\mathbf{T}$$$, $$$\mathbf{N}$$$, and $$$\mathbf{Q}$$$: the number of test cases, the number of elements to sort within each test case, and the total number of questions you are allowed across all test cases, respectively. Then, you must process $$$\mathbf{T}$$$ test cases. Each test case consists of a series of question exchanges plus an additional exchange to provide the answer.
For a question exchange, your program must print a single line containing
three distinct integers $$$i, j, k$$$ all between $$$1$$$ and $$$\mathbf{N}$$$, inclusive,
which corresponds to asking the judge "which element is the median of the set
$$$\{x_i, x_j, x_k\}$$$?"
The judge will respond with a single line containing a single integer $$$\mathbf{L}$$$,
meaning that the median of that set is $$$x_\mathbf{L}$$$ ($$$\mathbf{L}$$$ is always equal to
one of $$$i$$$, $$$j$$$, or $$$k$$$).
If you try to perform a $$$(\mathbf{Q}+1)$$$-th question exchange, the judge will simply output
-1.
Once you are ready to state the result, print a line containing $$$\mathbf{N}$$$ integers
representing the indices of the elements in sorted or reverse sorted order.
The judge will respond with a single integer 1 if your answer
is correct or -1 if it is not. After receiving the judge's answer for the
$$$\mathbf{T}$$$-th case, your program must finish in time in order to not receive a Time Limit Exceeded
error. In addition, if you print additional information after receiving the result
for the $$$\mathbf{T}$$$-th case, you will get a Wrong Answer judgment.
If the judge receives an invalidly formatted line or invalid values from your
program at any moment, the judge will print a single number -1.
After the judge prints -1 for any of the reasons explained above,
it will not print any further output. If your program continues to wait for the judge after
receiving a -1, your program will time out, resulting in a Time Limit
Exceeded error. Notice that it is your responsibility to have your program
exit in time to receive a Wrong Answer judgment instead of a Time Limit
Exceeded error. As usual, if the memory limit is exceeded, or your program
gets a runtime error, you will receive the appropriate judgment.
Limits
Time limit: 40 seconds.
Memory limit: 1 GB.
$$$\mathbf{T} = 100$$$.
Test Set 1 (Visible Verdict)
$$$\mathbf{N} = 10$$$.
$$$\mathbf{Q} = 300 \cdot \mathbf{T}$$$.
Test Set 2 (Visible Verdict)
$$$\mathbf{N} = 50$$$.
$$$\mathbf{Q} = 300 \cdot \mathbf{T}$$$.
Test Set 3 (Hidden Verdict)
$$$\mathbf{N} = 50$$$.
$$$\mathbf{Q} = 170 \cdot \mathbf{T}$$$.
Testing Tool
You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.
Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.
2 5 600
1 2 3
2
4 2 3
3
5 4 3
4
5 4 3 2 1
1
1 2 3
3
2 3 4
4
3 4 5
5
1 3 5 4 2
1
E. Cheating Detection
Problem
100 players are competing in a 10000-question trivia tournament; the players are numbered from 1 to 100. Player $$$i$$$ has a skill level of $$$S_i$$$ and question $$$j$$$ has a difficulty level of $$$Q_j$$$. Each skill level and each question difficulty are chosen uniformly at random from the range $$$[-3.00, 3.00]$$$, and independently of all other choices. For example, a player can have a skill level of $$$2.47853$$$ and a question can have a difficulty level of $$$-1.4172$$$.
When player $$$i$$$ tries to answer question $$$j$$$, the probability that they answer it correctly is $$$f(S_i - Q_j)$$$, where $$$f$$$ is the sigmoid function: $$$$f(x) = \frac{1}{1 + e^{-x}}$$$$ where $$$e$$$ is Euler's number (approximately 2.718...), the mathematical constant. Notice that $$$0 \lt f(x) \lt 1$$$ for all $$$x$$$, so $$$f(S_i - Q_j)$$$ is always a valid probability. Each of these answer attempts is chosen at random independently of all other choices.
There is one exception: exactly one of the players is a cheater! The cheater is chosen uniformly at random from among all players, and independently of all other choices. The cheater behaves as follows: before answering each question, they flip a fair coin. If it comes up heads, they do not cheat and the rules work as normal. If it comes up tails, they secretly look up the answer on the Internet and answer the question correctly. Formally, they decide whether to cheat at random with $$$0.5$$$ probability for each question, independently of all other choices.
The results of a tournament consist of only the per-question results (correct or incorrect) for each player. Apart from the general description above, you do not know anything about the skill levels of the players or the difficulties of the questions.
You must correctly identify the cheater in at least $$$\mathbf{P}$$$ percent of the test cases. That is, you must succeed in at least $$$\mathbf{P} \cdot \mathbf{T} / 100$$$ out of $$$\mathbf{T}$$$ cases.
Input
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. The second line of the input
gives the percentage of test cases, $$$\mathbf{P}$$$, that you must answer correctly for your solution to be
considered correct. $$$\mathbf{T}$$$ test cases follow.
Each case consists of 100 lines of 10000 characters each. The j-th character on the i-th line is
1 if the i-th player answered the j-th question correctly, or 0 if they
answered it incorrectly.
Output
For each test case, output one line containing Case #$$$x$$$: $$$y$$$, where $$$x$$$ is
the test case number (starting from 1) and $$$y$$$ is the number of the cheater (with
player numbers starting from 1).
Limits
Time limit: 60 seconds.
Memory limit: 1 GB.
$$$\mathbf{T} = 50$$$.
Test Set 1 (Visible Verdict)
$$$\mathbf{P} = 10$$$.
Test Set 2 (Visible Verdict)
$$$\mathbf{P} = 86$$$.
Sample
1 0 0011101000101010000010000001000101010000000011000110101000100001100101010000011000010010001000011000010010000000000010010000000000000111000110001010000000011110010000011001111000101011001100010000010000000010000100100000000000001000011010000101010000000000010001001111000100010001000000010011010001001100110000100010001000010100000001001100010000010000011110010000000110000001001100100001000110000001000000100000001011000100010001101000000000000000000000001110010000001010010101101000011000000000000001000100001011000000110100100000000011100000010000000111100001000010000000000000110111101100110000111100100000100000011011010110000011000000001000100101000010000110010010010001000000110101001000001000100000010001010010001000100000000110110001000000110001000000000000000011010000100010000000110100010001001010110000000001000000010000000011100000001010101000000100000110000001000011001100010001111010100101010000000000100000100100000000011101000000000100101100001000000000101000110100000001010001111100001000000100001111000011100001000001100000000011011000001000100110110000000001111000100000001000011011010000000000001011100000000110000011001010000001010000011000100001000001010000010000000001100010000001100000000000001001000010010000000000010000110000000110000000100000100010000100000011010010001000010000001100011001001101110010010110000101111100000011000011011000000010000010101101100100010000001000000101100000010000101000001000100000000100000111010000000011001011011001100010001000000001111000100100001000000010000000100000101000000000000001100000111100100010001010000110000001010100010100011010010000010000100000100000010010010000110000111100100111110000001000100000000001000001000000000000110001100010000000110100001000010011001110010000001000000000000100000010000100000000101000110010001011000001000100111000010101001000011100000010011100000100100111100100000000000011001000110000000000000010110100010001000000000100000100010100001000010000010101000001111000110000010011100000000000000010100000000100000000011010100001100010001000000000111000001100000000010101010000000011001000001010000110110000111010001100000100000001110000000000000001001000000000010001000000000000001100010001100000010000000000000000101000000000000000100010110000010100110001000010010001011100110001000100100000010000001001101010000101000110000101000000010010000000100110000001000000100010000001101001001100010000000100110001100010000000100100001010010000010000001000000000000000001000000001110010010000101110001100010010100000111001000000000000110100110101010100000000101000000001100000000010111001000101010000000001010000000000101000000000010000000000010100101110010100000001101000010100100010000000101000001001100001010110000010000110001000100000000010010001000011011100000001001100100000000111001000100010000011100100000110100001010010001000110001001100100001000000110111010000000001000000000100010100000011010010000000100111000000000000000000010101100011000011101000000000001001000100100010111101000100110111010100010001000000000011011000010000001100000000010100000001001000110001011000100000000011010010000100111101110000011100000110100001000110000100101010100001100010010100000000010001000000001001110000010000000110000100010010000111100100000000000000101000010010001001000110010001001101000001001001000000000100000010001101000000010101010001010001110010100000000010101000011001001100000100101000010000101000001101111001000110000000000001011000011001000000100001000010000000000100000100011001001110010010000111100010000010001000001100010000001000101000010010010000011001101010110001000001001000101110010010100000000000001100010000001010000101000110000001001110010101000000100000000000000010001001000010010000010001001000000000011000110000001000001111000000000000001000101100001000000100010101001111011000100000100000100001110101001000100000000100010011010010000000000000100110000001001010101001110011110000000010001100000101000000000111100000000001100101001000000000000000000000000101000010110000110001000101100000000000000000000100000000001011000011001000000000000011001111001000000001000011000001100011100000000000111100000001000000010001100100000001000010000001010001100010000100001001011101000100100000000011010000100000011001000011101010000010010010100100011000100001000110001110000100100010100100010010110111010001100000100010000000001010111100011001010000000000000100001001011000000100010001111000010000010100001010100001010010101000010100000010001100010000010101000010010100011111110111000010010000010000000000000010100110001000100010000101100100100010001000001000100010000010000101010011000100110000011010000010110000011000000010100010010101100010010000010001101000000000000010001101000000000000000101001000000001011000000000000000101010110001000100000011000000100010000000001101011000000100100000001010000010010010000101000001100001100100110000000100010001010100000011000000001010000000000110010101011000010000000000000100011000000010101011000001011000011000000010000010001010000011100010100000001110000000000001100101000001100110000011000000101000101001000001011000100100000100010100000011100110101000000011010011001100011100011010100010100111100000000010111101000011000010000000001101010100000011000000000000101000000001001000000000100001100001101010001000010001000001000100000000010101000010010000111000010000000000001000000011110011000010010000000000101100000100010001101000000000010110100010100111001000000100000000001100010010000011010110000010100101001000001101000001100001101010000100010011101000000001100100000100010101000000000011000000000100000100010101010010000000010001010000100010000001010000101100001000000001000100000100101101000100111000000000000100110000101001000010000110101000010101000110000010100001000011101111000000110010000110110100000000010000001010001011000100000000000110100000110110010110000100101000000000000001001100010101000000010000000010000110001000000001010001000000101000010010010101101100000001001001001110010001111011000000100000100010000100010111001000000000100010000000110111001001100000000100011100100000000010010001000110010101101011000000100000101011001100000000101000000000010100101100000100110100001000011010010000000000000011101001000111000000000001010001001000000001000000010000000011000000100000110011000001100100010000000100000000010000100000000101010101000001001000011000001010111000000011101101011110000010000000000011000000000100010000110000000010001100011001100000110000000010000000001010011000011010011000010001100000000100011001000010000010010000110100010011000000000000100101000000010111000000000001000001001001010000001000000000000010010000001001001001100010101000000011010010001000100000000100001111000100110000100100000101000100001000001000010000010011000000000100100100010000110000000101001000010100000010000101010000000000101011000000010000000010000000010100001100000000000111000001011101001001000110000100000010000010000100000000010011101000110000010011000100110000100000000000000100100010111010010010010000000111000000001000101110010101000110100111000000001010000100010000000010001000001010000110000100001010011101010010100000000000010100000010000110000010001000001000011000010010000000011100111101011000100010000000000010000000000000100000000100010001110101101010111000000101101100000111001010000000011010110100000000010000000001100000000001000010100100010010000011100001100110100000010100010100000000000010100010001010000110001000000001000010100011000000100000011000100000000100000110000001000101000000011001001010000000101000000001000100010010000100011100001010000001100010000000100000100101100101000000000010001000000111100110000101100000110000000100010000010010010100000111000011001001100000110000100000001101011011010000100000100000100110000100101000010000010100000001001000000100011000000110011001100000010000001001010001000100001000000000100000100001000000001001001001011001010011100100001000101011001001101100110000000000000000000000010000000010001000100010000101101000010001001001111000000001000001110000000001000000000011000011000000000000011000000000000110000000001001101000000100000001000001100010010010000010000000010100010010000011001001010010000000000000000000001100111011000000001010111100000000000000101001010000100100000011000001111000010001000001100010001011000000100110000100000101000000001001000000000010111000100100000100010000000000000010100000100010000000001011010110010101000001000000000000001011011001100000001000000000000000000000101000001001110100000000001000000111101001100000000010011000100010001000001100100100001100100010001100001010101010001010001001000010100000000000000000000000000010100100101000110000001001000001001110110001000001001000000010000111001111001010001101010111000010010001101001000100101100000110000000010010010000100100000000011001001011000001000001110010011000000110000000001010000100001000010010001010111001000001010000001111000100100100000110010000101100000110100000000010000000100100010000010000101110001000000000000100101000000000110011001011100111000001100000001000111000011000000100101000001010010110000000000000110010001010001010110100000001101100111011111000000010000001100001001110001001101011000000000100000010001000000101001001000001000000000000111000100010000000010001000000001000000000000000101000000000000110010100010001001001000001100010000000101100000000000110010000100010000000000010111101110001011100000001011000101011010001100001100101000000000100000000000100000010000100000001000000010001000100100001110100010101100000100010001000010110000000000000101000000000001001000000111001000011011010101110010100000000011110000100000110010000000010011110001011010000000000100011001000000010000010011000000001011000000000000011010001000101000010111000001001001001011000000000000010011000000101000010100100000001011110000100001100010110000011001010001010100000010011101100010000000100100000000101101000100100001000000010001000000000000010100110000000100010110000000000000100001011010001111100000010000011000000110000000000100000100001000100000001001100100101010101010000101000100110 ------------------------------- 99 lines of input omitted. Use the download button above to view the full sample input. -------------------------------
Case #1: 59
Analysis — A. Reversort
The pseudocode of the solution is almost given in the statement. We just need to give it the formal shape in the programming language of our choice. There are two non-straightforward statements in the provided pseudocode. We assume we store L in an array, so we have quick access to any index within it.
The first one is to figure out the index of the minimum element in a contiguous subarray. There
may be some library functions to perform this task. For example, in
C++ we can use min_element, in Python we can use
index
and
min
to figure out the minimum element. We can also run another loop to find out
the minimum element in the subarray. Please note, the input numbers are all different
so the minimum in each iteration is unique.
The second one is to reverse a subarray. Again, there may be some library functions
to perform this task. For example, we can use the
reverse
STL library
function for C++,
reversed
or reverse or simply slicing in Python.
We can also run a loop to reverse the subarray.
The length of the subarray we are reversing in the second step above is the cost of the reversal. Accumulating these costs will give our final answer.
This solution has the time complexity of $$$O(\mathbf{N}^2)$$$. We are running an outer loop from 1 to $$$\mathbf{N}-1$$$. Inside the loop we are performing two steps that take linear time each: minimum finding and array reversal. Hence the time complexity is $$$O(\mathbf{N}^2)$$$.
One final note, there are solutions to this problem that run in $$$O(\mathbf{N}\log{\mathbf{N}})$$$ time, but they are a lot more complex. Do you want to try to find one?
Analysis — B. Moons and Umbrellas
Test Set 1
In Test Set 1, the size of the mural is small enough that we can test every possible final mural.
Let $$$\ell$$$ be the length of $$$\mathbf{S}$$$.
We can either check for each string of length $$$\ell$$$
consisting only on Cs and Js whether it agrees with
$$$\mathbf{S}$$$ in the non-? spots, or brute-force only the ?s directly. For
each valid way of finishing the mural, we can calculate the total cost to Cody-Jamal, and keep
a running minimum to output at the end. Since we check at most $$$2^\ell$$$ final murals, and for
each we need only an additional linear pass to check the score, this algorithm takes
$$$O(2^\ell \cdot \ell)$$$ time, which is fast enough for Test Set 1.
Test Set 2
In Test Set 2, $$$\ell$$$ can be up to $$$1000$$$, so an exponential algorithm will not do.
However, a simple observation can yield a much faster algorithm:
since $$$\mathbf{X}$$$ > 0 and $$$\mathbf{Y}$$$ > 0, we would like to avoid inserting CJ or JC
into the string. So if all letters
surround a consecutive substring of ?s are the same letter $$$a$$$, then making
all those ?s into $$$a$$$ adds no CJs or JCs.
If the substring is surrounded by $$$a$$$ on the left and $$$b$$$ on the right, with
$$$a \neq b$$$, on the other hand, at some point there will be a change from $$$a$$$ to $$$b$$$,
so we will be forced into an occurrence of $$$ab$$$. Making all the ?s into $$$a$$$s
(or $$$b$$$s) makes sure that we only add that one forced occurrence and nothing else. This yields
a greedy algorithm that can be implemented in multiple ways, some taking as little as
$$$O(\ell)$$$ time. Notice that the cost is the same on the resulting string than on the string
where ?s are removed instead of replaced, which leads to a 1-line implementation:
S.replace('?', '').count('CJ') * X + S.replace('?', '').count('JC') * Y
Extra credit: Test Set 3
In the solution for Test Set 2 we assume that minimizing the number of occurrences of
CJ and/or JC is best, which is true only when $$$\mathbf{X}$$$ and $$$\mathbf{Y}$$$ are
non-negative. This means that Test Set 3 needs a completely different solution. In this
case, a technique that would not normally show up in the second
problem in a Qualification Round:
dynamic programming.
We can take the function $$$f(s)$$$ that we need to compute and define it recursively as follows:
- $$$f(\mathtt{?}s) = \min(f(\mathtt{C}s), f(\mathtt{J}s))$$$
- $$$f(a\mathtt{?}s) = \min(f(a\mathtt{C}s), f(a\mathtt{J}s))$$$ for $$$a \in \{\mathtt{C}, \mathtt{J}\}$$$
- $$$f(aas) = f(as)$$$ for $$$a \in \{\mathtt{C}, \mathtt{J}\}$$$
- $$$f(\mathtt{CJ}s) = \mathbf{X} + f(\mathtt{J}s)$$$
- $$$f(\mathtt{JC}s) = \mathbf{Y} + f(\mathtt{C}s)$$$
- $$$f(s) = 0$$$ if the length of $$$s \le 1$$$
You can verify that the cases above form a partition and properly define the recursion. We have a constant number of cases, each of which can be computed in constant time not counting the recursion calls, so the time complexity of the solution is $$$O(D)$$$ where $$$D$$$ is the size of the domain of the function. You can check that every value of $$$f$$$ that is ever required to calculate $$$f(\mathbf{S})$$$ can be defined by a suffix of the input $$$\mathbf{S}$$$ and at most two extra characters at the beginning. This means $$$D$$$ is linear in the length of $$$\mathbf{S}$$$, and so is the time complexity of the algorithm. Notice that we need to represent each element in the domain in constant space for this to work out exactly as mentioned, for example representing suffixes of $$$\mathbf{S}$$$ by just their length or an index into $$$\mathbf{S}$$$. However, for the low limits of this problem, even a larger representation using copies of the full suffix is fast enough.
Analysis — C. Reversort Engineering
Test Set 1
The solution to the problem is a permutation of the numbers from 1 to $$$\mathbf{N}$$$.
The cost of each permutation can be calculated by simulating the Reversort algorithm as
described in the
analysis of the Reversort problem in $$$O(\mathbf{N}^{2})$$$ time complexity.
There are $$$\mathbf{N}!$$$ distinct
permutations of size $$$\mathbf{N}$$$, containing the numbers from 1 to $$$\mathbf{N}$$$ exactly once each.
The cost of
each permutation can be calculated and the answer is any permutation that
has a cost equal to $$$\mathbf{C}$$$. If there is no such permutation, output
IMPOSSIBLE. The time complexity of the
overall solution is $$$O( \mathbf{N}! \cdot \mathbf{N}^{2} )$$$.
Test set 2
As $$$\mathbf{N}$$$ is large for Test Set 2, we cannot generate every possible permutation. The major observation here is that the range of valid costs for a given $$$\mathbf{N}$$$ lies between $$$\mathbf{N} - 1$$$ (when the cost of each reverse operation is the minimum possible, which is $$$1$$$) and $$$\frac{\mathbf{N} \cdot (\mathbf{N} + 1)} {2} - 1$$$ (when the cost of each reverse operation is the maximum possible, which is $$$\mathbf{N}-i$$$. Cost = $$$\mathbf{N} - 1$$$ when the array is already sorted.
All costs in between those two limits are possible, as we shall see.
Hence, if $$$\mathbf{C}$$$ is not in the valid range for given $$$\mathbf{N}$$$,
output IMPOSSIBLE. Otherwise, we perform the following construction by recursion,
which also serves as proof that the costs in range are indeed possible.
The first iteration costs between 1 and $$$\mathbf{N}$$$, so we should choose a cost $$$x$$$ for it
such that $$$\mathbf{C} - x$$$, fits in the possible range for a permutation of size $$$\mathbf{N} - 1$$$.
You can check that this is always possible,
and even compute the full range of $$$x$$$ values that work by solving the system of
inequalities.
Now, recursively generate a permutation $$$P$$$ of size $$$\mathbf{N} - 1$$$ and cost $$$\mathbf{C} - x$$$. Then, add $$$1$$$ to all integers in $$$P$$$ and insert $$$1$$$ at its left end, getting a new permutation of integers between $$$1$$$ and $$$\mathbf{N}$$$. Then, reverse the prefix of $$$P$$$ of length $$$x$$$ as the cost of the initial iteration should be $$$x$$$. The non-recursive steps take $$$O(\mathbf{N})$$$ to adjust $$$P$$$. Since we perform those for each index, the overall complexity of the solution is $$$O(\mathbf{N}^{2})$$$.
Analysis — D. Median Sort
This problem is about information theory. There are $$$\mathbf{N}! / 2$$$ essentially different outputs, which means we need at least $$$\log_2(\mathbf{N}! / 2)$$$ bits of information. For $$$\mathbf{N}=50$$$ that is slightly over $$$213$$$. That means that for Test Set 2, extracting less than a bit per query (on average) can work, but for Test Set 3 it will not. In Test Set 1, on the other hand, this informational analysis is not necessary.
Test Set 1
In this test set we have 300 queries per case, which is more than the number of different triples $$${\mathbf{N} \choose 3} = 120$$$. This means that we can query every possible subset of $$$3$$$ elements and memoize the results. Freed from the limitations of the number of queries, any solution to sort based on medians works. One simple way is to notice that the only elements that are never the median are the first and last elements, so we can identify those, and arbitrarily choose which one is the first and which one is the last. Then, we can eliminate those two and find the candidates for second and next-to-last as the ones that are never median in queries with only remaining elements. To know which one to assign second, we can check an additional query between the element we chose to go first and the two newfound elements: the one who is the median of that subset should be second, and the other one should be next-to-last. We can iterate this to find and place pairs of elements moving inwards until we place them all.
See below for other sorting algorithms that work on medians. While the other test sets have the additional burden of having to make them work in an online way, we can use the pre-query tactic for this one to make our lives easier, even if we implement the same basic algorithm. It also allows for simpler implementations of some of the algorithms that use extra queries.
Test Set 2
Since just $$$1$$$ bit of information per query is enough for this test set, we can use one of our known comparison-based optimal sorting algorithms like Merge Sort or Heap Sort. Even Insertion Sort can work if we use binary search to look for the insertion point. While Insertion Sort + Binary Search requires a suboptimal $$$O(\mathbf{N}^2)$$$ number of operations, it uses an optimal $$$O(\mathbf{N} \log \mathbf{N})$$$ number of comparisons.
For any of these algorithms we need a way to simulate a binary "less than" operation between two arbitrary items $$$i$$$ and $$$j$$$. One way to do that is to ask for the median of $$$i$$$, $$$j$$$ and $$$k$$$ while knowing $$$k$$$ is not the median. So, we could try to find an overall minimum or maximum and then use that as $$$k$$$ for every other query. Notice that there are $$$2$$$ elements that can be minimum and/or maximum and neither would be the median of any query. So, we can do a query for the median of the first three elements. We can discard the median of those and keep the other $$$2$$$ as candidates. We add any element we have not checked and do another median query, discarding the median and keeping $$$2$$$ candidates again. After $$$\mathbf{N}-2$$$ queries, we have discarded $$$\mathbf{N}-2$$$ elements, and the $$$2$$$ that remain are the minimum and maximum.
Test Set 3
To solve Test Set 3 we can observe that our implementation of Insertion Sort can actually extract more than $$$1$$$ bit per query and have a smaller constant. Instead of looking for the minimum/maximum first, we simply use the minimum of our current range in the median query as $$$k$$$. This means it is not guaranteed to never be the median. However, if the "current minimum" is the median of our query, we know exactly where to insert and can stop searching. This effectively makes our query a binary comparison with a little bit of extra information, and that little bit (plus being careful about never overspending) can be enough to pass Test Set 3. More importantly, it enables us to not find for the minimum first, which is a significant overexpenditure.
We can also find solutions that have more wiggle room by extracting a lot more than $$$1$$$ bit per query. Specifically, we want to extract something closer to the optimal $$$\log_2 3 \approx 1.58$$$ bits per query. That means considering all $$$3$$$ possible outcomes of the query, and have them happen with approximately equal probability (see the information theory article for details on the link between the probability distribution of outcomes and the information content of the query response).
We can further refine the Insertion Sort implementation to use a ternary search (in this case, this means a search similar to binary search that splits into three parts instead of two) to extract the full potential out of the median query. At each step, we query the two elements that are $$$1/3$$$ and $$$2/3$$$ of the way into our current range, together with the element to be inserted. The result narrows down the search to one of three ranges (roughly first, middle or last third). Notice that any query that we do to handle border cases (like inserting at the very beginning or very end) does not get the optimal $$$1.58$$$ bits of information, so we want to be careful not to use those, or to use them infrequently.
A different option is to do a two-pivot randomized quicksort. By using two pivots, we make full use of each median query involving them and each other element, as there are three buckets where the other elements can fall, each corresponding to a possible response to the query. The only issue with this approach (and any other approach based on a divide and conquer sorting algorithm) is that there are two ways to orient each recursive result if they have more than one element. If we use a query to decide which way is consistent with our decision on how to order the pivots, that query gives us only $$$1$$$ bit of information. Luckily, this is rather infrequent as it only happens proportional to the number of branches in the recursion tree that contain more than one element, which is a small number.
Analysis — E. Cheating Detection
Solutions for this problem are based on the fact that the cheater's advantage pumps up their numbers independently of the difficulty. Judged by their total number of correct answers, a cheater with base skill level $$$B$$$ is going to look like a player with skill $$$B+\Delta$$$ for some significant $$$\Delta$$$ ($$$\Delta$$$ depends on $$$B$$$). However, this cheater does worse on easy problems than a player of actual $$$B+\Delta$$$ skill level, and better on hard problems, because the correct answers that are coming from cheating happen uniformly instead of more heavily on easier problems like skill-based improvements.
Test Set 1
There are multiple ways to get to $$$10\%$$$ accuracy to pass Test Set 1. One such way is to estimate each question's difficulty as its number of correct answers, then sort by that difficulty, and check how uniform the distribution of corrects for each candidate is. The closer to uniform a candidate looks, the more they look like a cheater. One possible metric is the number of pairs of questions with different answers such that the incorrect answer is estimated to be for an easier question than the correct one. Using this metric is just enough to pass Test Set 1.
Test Set 2
The issue with counting inversions as the suggested metric for Test Set 1 is that it is a metric that is very susceptible to the contestant's strength. More concretely, a list that has few corrects or few incorrects has fewer opportunities to have inversions than one that is fairly evenly split. We can solve this by dividing the number of inversions by the expected number of inversions in a randomly arranged one. This reduces the noise enough to pass Test Set 2.
Another way to increase accuracy, of invesions or any other metric, is to check super-easy and super-hard questions, because the difference between a uniform distribution of correct answers and a heavily biased distribution is more pronounced in those. Exactly how much depends on the metric, but around the easiest and hardest $$$5\%$$$ of questions seems like the right number experimentally for our solutions.
Other metrics are more accurate than inversions and also help solve the problem. We found two techniques that work well enough: sort the players by estimated skill level (i.e., by total number of correct answers) and compare the number of corrects only in the "extreme" questions with the number of corrects of other players with similar estimated skill level among those. Then, assume that the cheater will have the greatest difference with its neighbors. Another technique could be to estimate the actual skill level (by computing the inverse sigmoid of the accuracy of each player) and the actual difficulty of questions (again, the inverse sigmoid of its proportion of corrects). Then, using those two, estimate the expected number of correct answers for each player in the extreme questions. The player with the largest difference between that estimation and the real value is the cheater. Using this latest technique can get a solution above $$$90\%$$$ accuracy.