| Predictor | A | B | C | D | E | F | G |
|---|---|---|---|---|---|---|---|
| Proof_by_QED | 800 | 900 | 1100 | 1200 | 1400 | 1700 | 1900 |
| Intellegent | 800 | 900 | 1000 | 1200 | 1500 | 1900 | 2000 |
| RobinFromTheHood | 800 | 800 | 1100 | 1400 | 1600 | — | -| | yse | 800 | 900 | 1100 | 1300 | 1500 | 1800 | 1900 | | Edeeva | 800 | 800 | 1000 | 1100 | 1400 | 1700 | 2100 | | -firefly- | 800 | 800 | 800 | 900 | 1400 | 1800 | 1900 | | Non-origination | 800 | 1000 | 1000 | 1300 | 1400 | — | 2000 | | satyam343 | 800 | 800 | 1000 | 1200 | 1500 | 1700 | 2000 | | reirugan | 800 | 900 | 900 | 1000 | 1600 | 1800 | 2000 | | catgirl | 800 | 800 | 800 | 1000 | 1600 | 1900 | 1700 | | temporary1 | 800 | 800 | 900 | 1000 | 1600 | 1900 | 1700 |
2137A - Collatz Conjecture
Problem Credits: Proof_by_QED
The reverse of the Collatz conjecture can be written as follows:
- Multiply $$$x$$$ by $$$2$$$ (if $$$2x$$$ was even)
- Subtract $$$1$$$ from $$$x$$$, then divide by $$$3$$$ (if $$$\frac{x-1}{3}$$$ is an integer and is odd).
In this problem, we can ignore the second type completely, because $$$2x$$$ is always an integer and is always even. We can simply print out $$$x\cdot 2^k$$$ as our answer.
will be added after open hacks phase
2137B - Fun Permutation
Problem Credits: Proof_by_QED
We can show that the permutation $$$q$$$ defined by $$$q_i=n+1-p_i$$$ satisfies all required properties.
- Proof $$$q$$$ is a permutation: Since $$$p_i+q_i=n+1$$$ and elements of $$$p$$$ ranges from $$$1$$$ to $$$n$$$, elements of $$$q$$$ will also range from $$$1$$$ to $$$n$$$. Additionally, since $$$p$$$ is a permutation (all elements are distinct), $$$q$$$ must also be a permutation.
- Proof $$$GCD(p_i+q_i, p_{i+1}+q_{i+1})\geq 3$$$: Since $$$n\geq2$$$, $$$n+1\geq 3$$$. The GCD of any number with itself is itself.
Will be added after open hacking phase
2137C - Maximum Even Sum
Problem Credits: Proof_by_QED
First, observe that in order to maximize the sum of two positive numbers given that their product must stay constant, it is optimal to minimize one number as much as possible (and in the process, maximize the other).
Let's do casework on the parity of $$$a$$$ and $$$b$$$:
- $$$a$$$, $$$b$$$ are both even: in this case, we cannot choose a $$$k$$$ such that $$$\frac{b}{k}$$$ is odd, as $$$a$$$ will stay even, and $$$a+b$$$ will be odd. The optimal $$$k$$$ here is $$$\frac{b}{2}$$$.
- $$$a$$$ is even, but $$$b$$$ is odd: In this case, we should print $$$-1$$$, as it is impossible to make $$$a+b$$$ even.
- $$$a$$$ is odd, $$$b$$$ is divisible by $$$2$$$ and not $$$4$$$: This case is also impossible. No matter what $$$k$$$ we choose, one of $$$a$$$ and $$$b$$$ will always be odd.
- $$$a$$$ is odd, $$$b$$$ is divisible by $$$4$$$: Even though $$$a+b$$$ is initially odd, it is possible to make $$$a+b$$$ even in this case by choosing a $$$k$$$ so that $$$k$$$ and $$$\frac{b}{k}$$$ are both even. Once again, the optimal $$$k$$$ to use is $$$\frac{b}{2}$$$.
- $$$a$$$ and $$$b$$$ are both odd: In this case, the optimal $$$k$$$ to use is $$$b$$$. Note that $$$a+b$$$ will always be even no matter what $$$k$$$ is chosen.
Will be added after open hacking phase.
2137D - Replace with Occurrences
Problem Credits: Proof_by_QED
First, we should observe that the number of occurrences of $$$x$$$ in $$$b$$$ must be a multiple of $$$x$$$. This is true because if we have $$$b_i=k$$$, then there are $$$k$$$ occurrences of $$$a_i$$$ in the original array. Suppose we group up all equal elements in the array $$$a$$$. If the number of occurrences of $$$b_i$$$ is not a multiple of $$$b_i$$$, then there is at least one group which doesn't have $$$b_i$$$ elements. This is a contradiction.
If the number of occurrences of $$$b_i$$$ is a multiple of $$$b_i$$$ for all $$$i$$$, then we can construct as follows:
- keep a varible $$$z=1$$$.
- For each $$$x$$$ from $$$1$$$ to $$$n$$$, iterate through the all indices $$$i$$$ with $$$b_i=x$$$. Label the first $$$x$$$ numbers as $$$z$$$, then increase $$$z$$$ by $$$1$$$. Continue until all indices are labeled.
This solution works in $$$O(n)$$$.
Will be added after open hacks
2094E - Boneca Ambalabu
Problem Credits: Proof_by_QED
Let's first determine how to run the operation a single time.
Let $$$m$$$ be the MEX of the array, and let $$$occ_i$$$ be the number of occurrences of the number $$$i$$$. We have these cases: - If $$$a_i \gt m$$$, then $$$a_i$$$ will become $$$m$$$. - If $$$occ_{a_i}=1$$$ and $$$a_i \lt m$$$, then $$$a_i$$$ will still be itself after the operation. This is because after we remove $$$a_i$$$ from the array, $$$a_i$$$ will be the new MEX. - if $$$occ_{a_i} \gt 1$$$ and $$$a_i \lt m$$$, then $$$a_i$$$ will become $$$m$$$. This is because even after removing $$$a_i$$$, there will still be at least one more occurrence of $$$a_i$$$, so $$$a_i$$$ will simply become the MEX of the whole array.
From this, we notice that numbers with frequency $$$1$$$ and less than the MEX will not change, while other numbers will map to the MEX. Let the state of $$$a$$$ be $$$a'$$$ after one operation. We will now prove that performing further operations on $$$a'$$$ will make it alternate between at most two states.
Will be added after open hacks
2094F - Trulimero Trulicina
Problem Credits: Proof_by_QED
What would happen if we tried outputting the numbers $$$1, \dots, k, 1, \dots, k, \dots$$$ in the natural reading order? For example, for $$$n=3$$$, $$$m=4$$$, and $$$k=6$$$, we would output the following:
| 1 | 2 | 3 | 4 |
| 5 | 6 | 1 | 2 |
| 3 | 4 | 5 | 6 |
In which cases does this fail?
This fails if and only if $$$m$$$ is a multiple of $$$k$$$, because we see that horizontally adjacent elements differ by $$$1\pmod k$$$ and vertically adjacent elements differ by $$$m\pmod k$$$. Now try to resolve this case.
There are many working constructions for this problem; one of them is to case on whether or not $$$m$$$ is a multiple of $$$k$$$.
Suppose $$$m$$$ is not a multiple of $$$k$$$. For example, consider the second sample, where $$$n=3$$$, $$$m=4$$$, and $$$k=6$$$. Then we can output the numbers $$$1, \dots, k, 1, \dots, k, \dots$$$ in the natural reading order, as follows:
| 1 | 2 | 3 | 4 |
| 5 | 6 | 1 | 2 |
| 3 | 4 | 5 | 6 |
and we see that any two horizontally adjacent elements differ by $$$1\pmod k$$$, whereas any two vertically adjacent elements differ by $$$m\pmod k$$$, so no two adjacent elements are the same, as desired.
Now, suppose $$$m$$$ is a multiple of $$$k$$$. For example, consider the case $$$n=4$$$, $$$m=6$$$, and $$$k=3$$$. Suppose we were to try the above strategy, then we get:
| 1 | 2 | 3 | 1 | 2 | 3 |
| 1 | 2 | 3 | 1 | 2 | 3 |
| 1 | 2 | 3 | 1 | 2 | 3 |
| 1 | 2 | 3 | 1 | 2 | 3 |
which doesn't work, since vertically adjacent elements are the same. We can fix this by cyclically shifting every other row as follows:
| 1 | 2 | 3 | 1 | 2 | 3 |
| 2 | 3 | 1 | 2 | 3 | 1 |
| 1 | 2 | 3 | 1 | 2 | 3 |
| 2 | 3 | 1 | 2 | 3 | 1 |
and we see that any two horizontally adjacent elements differ by $$$1\pmod k$$$ as before, whereas any two vertically adjacent elements also differ by $$$1\pmod k$$$, so no two adjacent elements are the same, as desired.
Will be added after open hacks
2094G - Chimpanzini Bananini
Problem Credits: Proof_by_QED, cry
Note that reversing an array then pushing an element to the back is similar to simply pushing an element to the front. Thus, we would like to push elements to both ends of the array. What data structure supports this?
A deque is the most natural choice to use. Most languages, including C++, Java, and Python, include deques in their standard library, so you likely do not have to implement it yourself.
What other values do we need to maintain in order to keep track of score?
It suffices to keep track of the current score, the score of the array if it were backwards, the size of the array, and the sum of the array.
We can solve this using a deque. Let $$$score$$$ denote the current score, and $$$rscore$$$ denote the score of the array if it were backwards. Let $$$size$$$ denote the size of the array, and $$$sum$$$ denote the sum of the array. Then we consider how these three values change as each operation is performed.
Suppose operation 1 is performed. This is equivalent to popping the back element of the array and pushing it in the front. When you pop the back element of the array, $$$score$$$ decreases by $$$a_n \cdot size$$$. Then when you push it to the front, $$$score$$$ increases by $$$sum$$$ because $$$a_n$$$ is pushed to the first spot and every element from $$$a_1$$$ to $$$a_{n-1}$$$ moves forward one spot. Notice that $$$rscore$$$ changes in the reverse way; this is equivalent to popping the front element of the array and pushing it to the back. When you pop the front element of the array, $$$rscore$$$ decreases by $$$sum$$$, and when you push it to the back, $$$rscore$$$ increases by $$$a_n \cdot size$$$. Note that $$$size$$$ and $$$sum$$$ remain unchanged.
Suppose operation 2 is performed. Then we swap $$$score$$$ and $$$rscore$$$, and we also want to "reverse" the array. However, it is costly to entirely reverse the deque. Instead, we will set a flag to indicate that the array has been reversed (and similarly, if the flag is already set, we will unset it). If the flag is set, we simply switch the front and back ends whenever we access or modify the deque while performing operations 1 or 3.
Suppose operation 3 is performed. Then we see that $$$size$$$ increases by $$$1$$$ and $$$sum$$$ increases by $$$k$$$. Then $$$score$$$ increases by $$$k \cdot size$$$ and $$$rscore$$$ increases by $$$sum$$$ (using the new value of $$$sum$$$), by identical reasoning to that in operation 1.
Additional optimization: we don't actually have to maintain $$$rscore$$$; we can obtain it with the expression: $$$(n+1)\sum_{i=1}^na_i-score$$$. This is because $$$score + rscore = (n+1)\sum_{i=1}^na_i$$$ since the $$$i$$$-th term is counted $$$i$$$ times in $$$score$$$ and $$$n+1-i$$$ times in $$$rscore$$$.
Will be added after open hacks
