Special thanks to our hub of testuwuers for contributing solution explanations!
2044A - Easy Problem
Problem Credits: cry
Analysis: macaquedev
For any $$$n$$$, Cube can set $$$a$$$ = any integer between $$$1$$$ and $$$n-1$$$ inclusive, and set $$$b = n - a$$$. $$$a$$$ cannot be less than $$$1$$$, because then it would be non-positive, and $$$a$$$ cannot be greater than $$$n-1$$$, because then $$$b$$$ would be less than $$$1$$$, which would make it non-positive. Therefore the answer is just $$$n-1$$$ for all $$$n$$$.
2044B - Normal Problem
Problem Credits: Lilypad
Analysis: Lilypad, macaquedev
The letters she reads that comprise string $$$b$$$ are just the letters that comprise string $$$a$$$, flipped left-to-right. This means that 'p' becomes 'q', 'q' becomes 'p', and 'w' stays 'w', since it is vertically symmetrical. The order in which the letters are read is also reversed, because what used to be the left side of string $$$a$$$ gets flipped over to the right side of string $$$b$$$, and vice versa.
We now have an algorithm for constructing string $$$b$$$, which is to iterate from right-to-left on string $$$a$$$, outputting 'p' when there is a 'q', 'q' when there is a 'p', and 'w' when there is a 'w'.
2044C - Hard Problem
Problem Credits: cry
Analysis: macaquedev
Let $$$A$$$, $$$B$$$, $$$C$$$ be three sets of monkeys, such that monkeys in $$$A$$$ can only sit in row $$$1$$$, $$$B$$$ in row $$$2$$$, and $$$C$$$ can sit anywhere. It is clear that if there is free space in row $$$1$$$, and there are monkeys left in set $$$A$$$, it is optimal to seat a monkey from set $$$A$$$ onto row $$$1$$$. This is because a monkey from set $$$C$$$ can be seated on either row, and there might be space left on the other row for that same monkey in set $$$C$$$ after you've already seated the monkey from set $$$A$$$. However, this is not the case if you start by seating the monkeys in set $$$C$$$ in the front row, since you might now leave empty seats at the back, but then have monkeys from set $$$A$$$ still left unseated.
Therefore, the strategy is as follows: seat as many monkeys from set $$$A$$$ as you can in the front row, then seat as many monkeys from set $$$B$$$ as you can in the back row, then seat as many monkeys from set $$$C$$$ as you can, and that yields the answer.
2044D - Harder Problem
Problem Credits: cry, vgoofficial
Analysis: macaquedev
Observe that if you have an array where all elements are unique, they will all have frequency $$$1$$$, therefore they can all be classified as the mode. Therefore, it follows that the strategy for the construction is to just construct an array where for each prefix, the last element of this prefix appears in the array at least once. An easy way of doing is this is such:
For each element $$$a_i$$$, if this value has appeared previously in the array (you can use a set to check this), set $$$b_i$$$ equal to some random integer that isn't used elsewhere in the list $$$a$$$, and keep going. Otherwise, set $$$b_i = a_i$$$.
2044E - Insane Problem
Problem Credits: vgoofficial,Lilypad
Analysis: macaquedev, chromate00
Clearly, trying to bruteforce over all possible values of $$$x$$$ or $$$y$$$ is too slow, because the bounds are $$$1 \leq l_1 \leq r_1 \leq 10^9$$$. However, there is another variable that you can actually bruteforce over — and that is $$$n$$$. This is because exponentiation famously makes numbers very big very quickly — and if we set $$$k$$$ as small as possible (i.e. $$$2$$$), we only need to check $$$1 \leq n \leq 32$$$. This is because $$$2^{32} > 10^9$$$, so there cannot possibly be any solutions for $$$n > 32$$$ for any $$$k$$$.
Now, let's rephrase the problem. We need to find pairs $$$(x, y)$$$ such that $$$x \cdot k^n = y$$$. Now, we can check every value of $$$n$$$ from $$$1$$$ to $$$32$$$, and for each, binary search to find the smallest $$$x$$$ such that $$$y$$$ fits the conditions, and the largest $$$x$$$. Now, we can subtract these two values and add this to the answer.
Note that we do not need to care about more than $$$32$$$ different values of $$$k^n$$$, because obviously $$$k^{32} \ge 2^{32} > 10^9$$$. From here and on, we focus on solving for only one value of $$$k^n$$$.
When $$$k^n$$$ is fixed and you are given $$$\frac{y}{x}=k^n$$$, notice $$$y$$$ is fixed as $$$x k^n$$$. Therefore, if we count the values $$$x$$$ such that $$$y$$$ is in the given interval as well, we will be properly counting the ordered pairs.
Formally, this condition can be cleared out as:
- $$$l_2 \le x k^n \le r_2$$$
- $$$\frac{l_2}{k^n} \le x \le \frac{r_2}{k^n}$$$
- Because $$$x$$$ is an integer, $$$\left \lceil {\frac{l_2}{k^n}} \right \rceil \le x \le \left \lfloor {\frac{r_2}{k^n}} \right \rfloor$$$
Thus, when we intersect the two intervals, we get the following interval at last.
Compute the size of this interval for all $$$k^n$$$ (at most $$$32$$$ values) and the answer can be found.
Do note the following details while implementing:
- When $$$r < l$$$, the size of the interval is $$$0$$$, not negative.
- Beware of overflows. Dealing with big integers can be helpful in avoiding this, but it may make your solution slow.
- Do not round up a fraction using the
ceilfunction; This has been a recurring issue in almost every Div.4!
2044F - Easy Demon Problem
Problem Credits: chromate00, vgoofficial
Analysis: SkibidiPilav
This is an anti-hash test for python sets and dictionaries. Before you call us evil, we saved you from getting hacked in open hack phase. Beware!
Let's denote the beauty of the matrix as $$$B$$$, and denote $$$\text{SumA}$$$ as the sum of all the elements in the array $$$a$$$, and $$$\text{SumB}$$$ as the sum of all the elements in the array $$$b$$$.
Before applying an operation, the beauty of the matrix can be expressed as:
$$$B = b_1 \cdot a_1 + b_1 \cdot a_2 + b_1 \cdot a_3 + b_2 \cdot a_1 + b_2 \cdot a_2 + \ldots$$$
After factoring, this simplifies to:
$$$ B = b_1 \cdot (a_1 + a_2 + a_3 + \ldots) + b_2 \cdot (a_1 + a_2 + a_3 + \ldots) + \ldots $$$
Further factoring gives:
$$$ B = (a_1 + a_2 + a_3 + a_4 + \ldots) \cdot (b_1 + b_2 + b_3 + \ldots) $$$
This can be written as:
$$$ B = \text{SumA} \cdot \text{SumB}$$$
Now, consider the effect of an operation on a column $$$C$$$. The beauty decreases by $$$A_c \cdot \text{SumB}$$$. Similarly, when an operation is done on a row $$$R$$$, the beauty decreases by $$$B_r \cdot \text{SumA}$$$.
An important observation is that the element at position $$$(r, c)$$$ is counted twice, so we must account for this in the formula.
After considering this, let the beauty after the operations be denoted as $$$X$$$. Using the observations above:
$$$X = B - (b_i \cdot \text{SumA} + a_j \cdot \text{SumB} - a_j \cdot b_i)$$$
Simplifying further:
$$$X = \text{SumA} \cdot \text{SumB} - b_i \cdot \text{SumA} - a_j \cdot \text{SumB} + a_j \cdot b_i$$$
Factoring terms, we obtain:
$$$X = \text{SumA} \cdot (\text{SumB} - b_i) - a_j \cdot (\text{SumB} - b_i)$$$
Finally:
$$$X = (\text{SumB} - b_i) \cdot (\text{SumA} - a_j)$$$
At this stage, it is sufficient to iterate over the divisors of $$$X$$$. For each ordered pair of divisors whose product is $$$X$$$, we check whether the required values of $$$\text{SumB} - b_i$$$ and $$$\text{SumA} - a_j$$$ can be achieved.
This can be implemented using a simple map or boolean vector for faster computation, although such optimization is not required for this problem.
2044G1 - Medium Demon Problem (easy version)
Problem Credits: Lilypad
Analysis: macaquedev
This problem deals with a specific subclass of graphs called "functional graphs", also known as "successor graphs". The key feature that they have is that each node only has one successor. Therefore, the graph in the problem will necessarily be split into $$$k \geq 1$$$ components, where each component necessarily contains one cycle, and each node will either be in the cycle, or it will be on a path leading towards the cycle.
Observe that if a node that is not on a cycle currently has a plushie, this plushie will cause the arrangement to be unstable until the plushie reaches the cycle. Proof: suppose node $$$u$$$ has the plushie on day $$$i$$$. On the next day, $$$u$$$ will no longer have this plushie, because they will have passed it down to $$$r_u$$$, therefore, the arrangement has changed. This continues inductively until the plushie reaches the cycle of its component.
From this, we know that the answer is at least the distance of any node to the cycle. Now, since every node in the cycle already has a plushie, we know that these plushies just get passed round and round, so actually, nodes within the cycle cannot change the answer. Therefore, we've already found the final answer.
2044G2 - Medium Demon Problem (hard version)
Problem Credits: Lilypad
Analysis: vgoofficial
Note that similarly to G1, once all plushies end up in the hands of spiders who are in a loop, the process becomes stable.
Let's model the input as a collection of rooted forests. For each spider $$$i$$$, if $$$i$$$ is part of a loop, then let's compress the loop into a single node and use that as the root of a tree. Otherwise, if spider $$$i$$$ gives a present to spider $$$r_i$$$, then let's draw an edge from $$$i$$$ to $$$r_i$$$. Now, let $$$i$$$ be any node that is not part of a loop. How long will it take until spider $$$i$$$ runs out of presents? We can see that it is the subtree size of $$$i$$$, as one present leaves the subtree each year.
Thus, our challenge now is to process the nodes in an efficient order such that we can find the subtree size of all nodes. This can be done with topological sorting, which gives us an order that processes all nodes starting from the leaf upwards. After the topological sort, we may do dynamic programming to find subtree sizes of all nodes. Let $$$dp[i]$$$ be the number of days until spider $$$i$$$ runs out of presents. Let's suppose that we already calculated $$$dp[i]$$$ (we initialize it to be $$$1$$$ for all nodes since each spider starts with a present). Then, we should add $$$dp[i]$$$ to $$$dp[r_i]$$$. Doing this and adding up all $$$dp$$$ values of nodes directly before a cycle will yield the answer.
2044H - Hard Demon Problem
Problem Credits: cry
Analysis: chromate00
Consider translating the sum back onto the matrix. For simplicity we discuss about querying the whole matrix.
The sum we would like to find is $$$\sum_i i\cdot A_i$$$. Here, $$$A_i$$$ corresponds to $$$M_{(x,y)}$$$, so we will translate this to $$$\sum_{x,y} i\cdot M_{(x,y)}$$$. The issue left is on the $$$i$$$ multiplied to it.
Remember that we index the entries in increasing order of $$$y$$$, and then increasing order of $$$x$$$. Assuming $$$y$$$ and $$$x$$$ were $$$0$$$-indexed, this will mean entry $$$(x,y)$$$ corresponds to $$$x\cdot n + y$$$ (also $$$0$$$-indexed). You can notice that this naturally corresponds to the order we had defined as well.
Then, what we want to find is $$$\sum_{x,y} (x \cdot n + y + 1)\cdot M_{(x,y)}$$$. Notice $$$x \cdot n$$$, $$$y$$$, $$$1$$$ are independent, and we can split them into sums $$$\sum_x x \cdot n \cdot M_{(x,y)}$$$, $$$\sum_y y \cdot M_{(x,y)}$$$, $$$\sum M_{(x,y)}$$$. Each of these three sums can be precomputed entry by entry, and a 2D prefix sum can solve the answer for the entire matrix.
The query for a submatrix is very similar. Formally, you have to care about:
- That we have $$$y_2-y_1+1$$$ columns instead of $$$n$$$ now;
- That the precomputed values might not start from $$$0$$$ on the first row/column of the query.
Still, these two issues can be fixed using the three sums we have precomputed. The time complexity becomes $$$\mathcal{O}(n^2+q)$$$.
