Something doesn't change after each operation.

The average of the entire array doesn't change after each operation. Simply check whether the average value of $$$a$$$ is $$$x$$$ or not.

Time complexity: $$$\mathcal{O}(n)$$$ per test case.

Submission: 310297520

Try to put as many people in cell $$$n$$$ as possible.

The minimum sum of distances will always be $$$1$$$.

The following configuration gives $$$1$$$ as the sum of distances.

For odd $$$k$$$: $$$n, n, \ldots, n, n, n-1$$$

For even $$$k$$$: $$$n-1, n-1, \ldots, n-1, n, n-1$$$

And the sum of distances cannot be $$$0$$$.

Time complexity: $$$\mathcal{O}(n)$$$ per test case.

Submission: 310297574

Prove that the optimal configuration is unique.

Rearrange the equation around.

Try to maximize the missing number.

The equation can be rearranged to

Choose $$$a_1$$$ as the largest number, $$$a_3, a_5, \ldots, a_{2n+1}$$$ as the next $$$n$$$ largest numbers, and the rest as $$$a_2, a_4, \ldots, a_{2n-2}$$$. The value of the missing number $$$a_{2n}$$$ will be larger than $$$a_1$$$, and so larger than every number in $$$b$$$.

Time complexity: $$$\mathcal{O}(n \log n)$$$ per test case. Logarithmic factor is from sorting.

Submission: 310297635

There are some randomization solutions where we just shuffle $$$b$$$ randomly, fill the missing number, and attempt it as a possible solution. I do not have a proof or disproof of whether this would work well enough.

It is optimal to place everyone on the same lane.

Think about the multiplier.

It is best to think of each $$$\tt{+}$$$ as "how much can we multiply this by".

This is the greedy solution.

When we get more people, place all to where the $$$\tt{x}$$$ will occur first. If both lanes have the next multiply at the same gate pair, then choose the one with higher multiply. If the multiply is the same, look to the next multiply.

Time complexity: $$$\mathcal{O}(n)$$$ per test case. $$$\mathcal{O}(n^2)$$$ implementations are also acceptable.

Submission: 310297718

This is the dynamic programming solution.

Let $$$dp_l[i]$$$ and $$$dp_r[i]$$$ be the maximum possible multiplication possible that can be applied if a person enters the $$$i$$$-th left and right gate, respectively. Then we have the following equation (only for left is written, it's the same for the right).

If the gate is $$$\tt{+}$$$

If the gate is $$$\tt{x}$$$ by $$$a$$$

For each $$$\tt{+}$$$, we choose to place people at the side with more multiplication.

Time complexity: $$$\mathcal{O}(n)$$$ per test case.

Submission: 310297763

$$$n = 30$$$ constraint is due to overflow. The maximum answer is the case with $$$n = 30$$$, the first pair of gates is $$$\tt{+} 1000$$$ $$$\tt{+} 1000$$$, and the other pairs of gates are $$$\tt{+} 1000$$$ $$$\tt{x} 3$$$, giving the answer $$$171644573789571884 \lt 10^{18}$$$.

It is possible to solve this task under modulo and force $$$\mathcal{O}(n)$$$ solution, but it will be hard, or maybe impossible, to implement the DP solution which requires min/max operations, so I decided against it.

Try to get information on half of the bits.

Alternate the bits.

The queries are $$$\ldots 0101_2$$$ and $$$\ldots 1010_2$$$.

It's easier to look at the case with only two binary digits first.

Let the result of query $$$01_2$$$ be $$$q_1$$$ and $$$10_2$$$ be $$$q_2$$$.

Observe that if

• $$$q_2 = 100_2$$$ then the first (from the right) digit of both $$$x$$$ and $$$y$$$ is $$$0$$$.

• $$$q_2 = 101_2$$$ then the first (from the right) digit of one of $$$x$$$ or $$$y$$$ is $$$0$$$, and the other one is $$$1$$$.

• $$$q_2 = 110_2$$$ then the first (from the right) digit of both $$$x$$$ and $$$y$$$ is $$$1$$$.

Similarly, if

• $$$q_1 = 10_2$$$ then the second (from the right) digit of both $$$x$$$ and $$$y$$$ is $$$0$$$.

• $$$q_1 = 100_2$$$ then the second (from the right) digit of one of $$$x$$$ or $$$y$$$ is $$$0$$$, and the other one is $$$1$$$.

• $$$q_1 = 110_2$$$ then the second (from the right) digit of both $$$x$$$ and $$$y$$$ is $$$1$$$.

To generalize to every other digit, apply the same logic to every consecutive pair of digits in $$$x$$$ and $$$y$$$. Note that you must account for the carries from the digits before too.

After this, you will know for every digit position whether both $$$x$$$ and $$$y$$$ are $$$0$$$, are $$$1$$$, or have one $$$0$$$ and one $$$1$$$. You can use this information to find $$$(m|x) + (m|y)$$$ for any $$$m$$$.

Time complexity: $$$\mathcal{O}(\log \max (x))$$$ per test case.

Submission: 310297820

Find a closed-form expression for the score of a binary string.

The closed-form expression for the score of a binary string is

Where $$$cnt_0$$$ and $$$cnt_1$$$ are the number of $$$\tt{0}$$$ and $$$\tt{1}$$$ in the binary string, respectively.

The expression for counting subsequences might be simpler than you think.

Think of $$$\tt{0}$$$ as $$$-1$$$ and $$$\tt{1}$$$ as $$$1$$$. Let us count the number of subsequences of a binary string which will have the sum of $$$i$$$. Let $$$cnt_0$$$ and $$$cnt_1$$$ as the number of $$$\tt{0}$$$ and $$$\tt{1}$$$ in the binary string. The number of subsequences is

So the desired sum of the score over all subsequences (see expression of score of a single string in Hint 2) is

At this point, you can throw convolution at the problem by precomputing the answer for $$$cnt_0 = 0, 1, \ldots, n$$$ and solve it in $$$\mathcal{O}(n \log n + q)$$$.

Submission: 310298025

Alternatively, you can do more algebra to arrive at a closed-form expression.

Time complexity: $$$\mathcal{O}(n+q)$$$ per test case.

Submission: 310297950

Find a way to get the answer if you fixed the largest value or the first value of the subsequence.

Sufficiently long (which is not that long) arrays will definitely be polygon side lengths.

Suppose we consider some integer $$$x$$$, and we try to find the lexicographically largest subsequence (say $$$s$$$) such that the maximum element of $$$s$$$ is $$$x$$$.

We can do it greedily.

For the subsequence $$$s$$$ to be valid, we need to ensure that the sum of the elements of $$$s$$$ is greater than $$$2x$$$.

So, our greedy strategy is like we have an empty vector $$$s$$$, and we iterate over the array $$$a$$$ from left to right, and for each element $$$a_i$$$, we do the following:

If $$$s$$$ is not empty and $$$a_i$$$ is greater than the last element of $$$s$$$, we will check whether we can make the total sum of $$$s$$$ greater than $$$2x$$$, if we remove the last element of $$$s$$$. Now what can be the maximum possible sum of $$$s$$$? We can just append all the elements of $$$a$$$ which are less than or equal to $$$x$$$, and are present to the right of $$$a_i$$$ to $$$s$$$.

Append $$$a_i$$$ to $$$s$$$.

Thus, we see that the subsequence $$$s$$$ is the lexicographically largest subsequence such that the maximum element of $$$s$$$ is $$$x$$$.

Now, we have $$$O(n)$$$ candidates for the maximum element of $$$s$$$. We cannot find the best subsequence for each candidate, as it will be too slow.

Here comes the key observation.

Now, what can be the maximum possible size of a sorted vector $$$v$$$ such that there does not exist any subsequence of $$$v$$$ which can form the sides of a valid polygon?

We should have $$$v_i \gt \sum_{j=1}^{i-1} v_j$$$.

Now, to get the maximum possible size of $$$v$$$, we should have $$$v_1 = 1$$$ and $$$v_i = 2^{i - 2}$$$ for $$$i \geq 2$$$.

Thus, the maximum possible size of $$$v$$$ can be $$$p = \log_2(10^9) + 2$$$.

Our claim is that in the lexicographically largest subsequence $$$s$$$, the maximum element should be one of the largest $$$p + 1$$$ elements of $$$a$$$.

Suppose we do not have the maximum element of $$$s$$$ in the largest $$$p + 1$$$ elements of $$$a$$$. Let's consider the multiset of the largest $$$p + 1$$$ elements of $$$a$$$. As we saw above, there should be a subsequence (say $$$t$$$) of this multiset which forms the sides of a valid polygon. Now if we insert the elements of $$$t$$$ in $$$s$$$, we will get a subsequence $$$s'$$$ such that $$$s'$$$ is valid and $$$s'$$$ is lexicographically larger than $$$s$$$.

Thus, we cannot have a subsequence $$$s$$$ such that $$$s$$$ is the largest possible subsequence and the maximum element of $$$s$$$ is not in the largest $$$p + 1$$$ elements of $$$a$$$.

Time complexity: $$$\mathcal{O}(n \log \max(a))$$$ per test case.

Submission: 310298095

Folding is basically alternating the parity of the indices.

Maximum subarray sum.

As mentioned in Hint 1, we can see that if the darkness of the cells $$$i_1, i_2, \ldots, i_k$$$ increases in some operation, the parity of $$$i_j$$$ should be different from that of $$$i_{j+1}$$$ for $$$1 \le j \le k - 1$$$

Let us try to find $$$f(a[1, n])$$$.

Consider an array $$$b$$$ such that $$$b_i = (-1)^i a_i$$$ for all $$$1 \le i \le n$$$.

Let us perform exactly one operation, and say our subsequence of indices is $$$i_1, i_2, \ldots, i_k$$$.

Let $$$a'$$$ be the updated array after performing the operation, and $$$b'_i = (-1)^{i'} a'_i$$$ for all $$$1 \le i \le n$$$.

Now we can see that

for all $$$1 \le l \le r \le n$$$.

This is so because for any subarray $$$b[l, r]$$$, if $$$x$$$ elements at odd indices and $$$y$$$ elements at even indices were selected, we should have $$$|x - y| \le 1$$$.

So, we can see that after any operation, the absolute sum of any subarray of $$$b$$$ decreases by at most $$$1$$$.

Thus, this gives us a lower bound for the value of $$$f(a[1, n])$$$, which is

Now let us consider the following greedy algorithm for selecting a subsequence $$$s$$$ of indices:

• Start from $$$i = 1$$$ and move to the right.
• If $$$b_i$$$ is zero, we continue.
• If $$$s$$$ is empty, we append $$$i$$$ to $$$s$$$, and continue.
• If $$$i$$$ does not have the same parity as the last element of $$$s$$$, we append $$$i$$$ to $$$s$$$, and continue.
• Otherwise, we continue.

Now suppose $$$T$$$ is the set of pairs of indices $$$(l, r)$$$ such that $$$b_l$$$ and $$$b_r$$$ are nonzero and

is maximized.

We can prove that the absolute sum of all subarrays in $$$T$$$ would be reduced by $$$1$$$ after performing the operation.

We can notice that if $$$(l, r) \in T$$$, then $$$l$$$ and $$$r$$$ should have the same parity. Otherwise,

Next, we claim that $$$l$$$ should be in $$$s$$$.

Suppose $$$l$$$ is not in $$$s$$$. This means that there should be an index $$$k$$$ in $$$s$$$ such that $$$k$$$ has the same parity as $$$l$$$ and there are no nonzero elements between $$$k$$$ and $$$l$$$ that have a parity different from $$$l$$$.

Now if that is the case, then $$$b[k, r]$$$ would have a greater absolute sum than $$$b[l, r]$$$.

Thus, we conclude that $$$l$$$ will always be in $$$s$$$.

Now let $$$d$$$ be the largest index in $$$s$$$ smaller than or equal to $$$r$$$.

First of all, we should have $$$d \ge l$$$.

Now $$$d$$$ should have the same parity as $$$r$$$.

This is so because if that is not the case, we should have $$$d \lt r$$$ and we would have selected $$$r$$$ or any other element having the same parity as $$$r$$$ after $$$d$$$ in $$$s$$$.

Thus, we can see that for all the pairs $$$(l, r) \in T$$$, we should have $$$l$$$ in $$$s$$$ and the largest element smaller than or equal to $$$r$$$ in $$$s$$$ should have the same parity as that of $$$r$$$. This implies that the absolute sum of all subarrays in $$$T$$$ would be reduced by $$$1$$$ after performing the operation.

This is because if $$$l$$$ is odd, we would have added $$$1, -1, 1, -1, \ldots, 1$$$ to the subarray $$$b[l, r]$$$, increasing the subarray sum of $$$b[l, r]$$$ by $$$1$$$.

And if $$$l$$$ is even, we would have added $$$-1, 1, -1, 1, \ldots, -1$$$ to the subarray $$$b[l, r]$$$, decreasing the subarray sum of $$$b[l, r]$$$ by $$$1$$$.

Now we can see that the greedy algorithm would achieve the lower bound.

So, the answer for the array $$$a$$$ is the maximum absolute sum over all subarrays of $$$b$$$.

Let us consider an array $$$c$$$ such that

We can further notice that the maximum absolute sum over all subarrays of $$$b$$$ is equal to

Now we can see that

Thus,

So,

Finding the value of

is a fairly standard exercise, which can be done using a stack in $$$O(n)$$$ time.

Submission: 310317161

Characterize the property of a good pair of arrays.

Think about the last operation that turns a good pair of arrays into the same array.

$$$(a, b)$$$ is a good pair only if at least one of these two conditions hold

• $$$a = b$$$

• There exist two distinct indices $$$i$$$, $$$j$$$ such that $$$b_i$$$ is a submask of $$$b_j$$$.

We need to check the two cases.

In the first case, the minimum cost will be $$$\sum_{i=1}^n |a_i - b_i|$$$.

In the second case, we want the minimum cost to create a submask-supermask pair in $$$b$$$.

Solution 1

For explanation simplicity, consider the graph $$$G$$$ with $$$2m$$$ vertices, representing the numbers from $$$1$$$ to $$$2m$$$. In this graph, there's an unweighted edge from vertex $$$i$$$ to vertex $$$i+1$$$, and from vertex $$$i$$$ to all submask vertices. Color all vertices in which its value appears in $$$b$$$. The answer is the shortest path between all pairs of distinct colored vertices.

The implementation itself (see below) uses dynamic programming consisting of three phases. The dynamic programming tracks the first and second closest vertex to each vertex, because the first closest vertex would be itself.

• Propagate each colored vertices up (from $$$i$$$ to $$$i+1$$$).

• Propagate to the submasks (from $$$i$$$ to its submasks).

• Propagate down (from $$$i$$$ to $$$i-1$$$).

Time complexity: $$$\mathcal{O}(n \log n + m \log m)$$$ per test case. The $$$\log n$$$ factor is from the implementation which checks for duplicates in $$$b$$$ by sorting.

Submission: 310298215

Solution 2

Submission: 310317931

It might help to solve this task with two colors first. As in, minimize the difference between red and blue.

In the two-color version (in Hint 1), we created a state graph on the parity. Can a similar idea be used?

Think about each color separately first.

Let

• the edge weights of the red edges be $$$r_1, r_2, \ldots$$$, the green edges be $$$g_1, g_2, \ldots$$$ and the blue edges be $$$b_1, b_2, \ldots$$$.

• $$$\gcd(r_1, r_2, \ldots)$$$, $$$\gcd(g_1, g_2, \ldots)$$$ and $$$\gcd(b_1, b_2, \ldots)$$$ be $$$c_r, c_g, c_b$$$.

• the sum of weights of red, green and blue edges traversed be $$$d_r, d_g, d_b$$$.

Define $$$ \lt d_{r_1}, d_{g_1}, d_{b_1} \gt = \lt d_{r_2}, d_{g_2}, d_{b_2} \gt $$$ only if $$$d_{r_1}-d_{g_1} = d_{r_2}-d_{g_2}$$$, $$$d_{r_1}-d_{b_1} = d_{r_2}-d_{b_2}$$$ and $$$d_{g_1}-d_{b_1} = d_{g_2}-d_{b_2}$$$.

In a similar manner to hint 1, there's a walk that passes through every edge and have $$$ \lt d_r, d_g, d_b \gt = \lt 0, 0, 0 \gt $$$. Furthermore, if we have $$$ \lt d_r, d_g, d_b \gt $$$, then we can have $$$ \lt d_r + 2g_r, d_g, d_b \gt $$$ and $$$ \lt d_r - 2g_r, d_g, d_b \gt $$$. The analogous statement holds for the other two colors.

Consequently, from any reachable $$$ \lt d_r, d_g, d_b \gt $$$, we can have $$$ \lt s_r, s_g, s_b \gt $$$, where $$$s_r$$$ is either $$$0$$$ or $$$c_r$$$ depending on whether $$$d_r \equiv 0$$$ ($$$\mod 2c_r$$$) or $$$d_r \equiv c_r$$$ ($$$\mod 2c_r$$$). The idea holds similarly for the other two colors. This invites us to look at each vertex as $$$8$$$ possible states, corresponding to $$$3$$$ binary options of each color.

We simply need to solve the answer for each reachable state then take the minimum. Each state corresponds to the following system of linear congruences.

We aim to minimize $$$\max(d_r, d_g, d_b) - \min(d_r, d_g, d_b)$$$ over all triplets which satisfy the conditions.

To do so, we will fix one of them, which we'll suppose is $$$d_r$$$, as the minimum.

Denote $$$f_g(p)$$$ and $$$f_b(p)$$$ as the minimum possible $$$d_g - (d_r + 2pc_r)$$$ and $$$r_b - (d_r + 2pc_r)$$$ where $$$r_g, r_p \geq d_r + 2pc_r$$$.

We want to find

Observe that $$$f_g(k + c_g) = f_g(p)$$$ and $$$fb(k + c_b) = f_b(p)$$$. By the Chinese remainder theorem, the expression above reduces to

Which can be evaluated in $$$\mathcal{O}(x)$$$.

Time complexity: $$$\mathcal{O}(n \log x + x)$$$ per test case. The logarithmic factor is from gcd computations.

Submission: 310298269

This contest was originally proposed as a Div. 2 only. It was changed to Div. 1 + Div. 2 because we found task 1G, which was originally proposed with only two colors as 2D.

The contest itself retained little of the original proposal, and most of the tasks were once proposed for a lower position.

• 2B was proposed as 2A.

• 1A/2C was proposed as 2A.

• 2D was proposed as 2B. The base story is credited to my friend Punpun.

• 1B/2E was proposed as 2C.

• 1C/2F was proposed as 2E with $$$n \leq 5000$$$. The testers found the solutions for the current version.

• 1D was originally made for permutation arrays only. Credit to satyam343 for making the task.

• 1E/2G was proposed as 2D with binary arrays. The testers found the solutions for the current version. The idea of folding and dropping color is credited to my friend Punpun.

• 1F was proposed in a much easier form as 2B. It was buffed by satyam343.

• 1G was proposed as 2D with two colors. Solving this easier version can hint the full solution.

Arcaea is a good rhythm game with good mechanics, music, and story. In some tasks, I put music from Arcaea in it because I want to.