Editorial for DMOPC '20 Contest 4 P5 - Cyclic Cypher

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: 4fecta

Subtask 1

This subtask was intended to reward brute force solutions.

Subtask 2

This subtask was intended to reward solutions with the correct idea, but which are too inefficient to pass for full marks.

Subtask 3

From here on, we will define $\nu_2$ ~\nu_2~ of a positive integer $n$ ~n~ as the highest integer exponent such that $2^{\nu_2}$ ~2^{\nu_2}~ divides $n$ ~n~ (also known as the $2$ ~2~-adic order of $n$ ~n~). This subtask provides the constraint that $\nu_2(N) > \nu_2(K)$ ~\nu_2(N) > \nu_2(K)~.

First, consider the case where $\nu_2(K) = 0$ ~\nu_2(K) = 0~, in other words when $K$ ~K~ is odd. If $\nu_2(N) > 0$ ~\nu_2(N) > 0~, then it is not hard to see that the construction of alternating $1$ ~1~s and $-1$ ~-1~s is verifiable. For cases where $\nu_2(K) > 0$ ~\nu_2(K) > 0~, consider the repeated homothetic (rescaling) reduction by a factor of $2$ ~2~ until $\nu_2(K) = 0$ ~\nu_2(K) = 0~. Note that since $\nu_2(N) > \nu_2(K)$ ~\nu_2(N) > \nu_2(K)~, it is guaranteed that $\nu_2(N) > 0$ ~\nu_2(N) > 0~ when $\nu_2(K)$ ~\nu_2(K)~ reaches $0$ ~0~, since a homothetic reduction by a factor of $2$ ~2~ reduces both $\nu_2$ ~\nu_2~ values by $1$ ~1~. This inspires the construction of alternating blocks of $1$ ~1~s and $-1$ ~-1~s where each block has a size of $2^{\nu_2(K)}$ ~2^{\nu_2(K)}~, and that is sufficient to pass this subtask.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Subtask 4

For full marks, first consider the impossible cases. Clearly $N = K$ ~N = K~ is impossible since there is only $1$ ~1~ subarray of length $K$ ~K~, which is guaranteed to have a non-zero product. Also, $\nu_2(N) = 0$ ~\nu_2(N) = 0~ is impossible since the parity of the final sum would be odd. Thus, we now only consider cases where $\nu_2(N) > 0$ ~\nu_2(N) > 0~ and $K < N$ ~K < N~.

Now, consider an array of all $1$ ~1~s. When we change a $1$ ~1~ to a $-1$ ~-1~ in this array, we are changing the signs of the $K$ ~K~ adjacent subarray products. Note that the initial sum of products must be even since $\nu_2(N) > 0$ ~\nu_2(N) > 0~. If $\nu_2(K) > 0$ ~\nu_2(K) > 0~, then the parity of the number of positive subarray products remains constant after changing an element from $1$ ~1~ to $-1$ ~-1~. However, when $\nu_2(N) = 1$ ~\nu_2(N) = 1~, we need an odd number of positive subarray products to get a total sum of $0$ ~0~, which is impossible when $\nu_2(K) > 0$ ~\nu_2(K) > 0~. Thus, the case with $\nu_2(N) = 1$ ~\nu_2(N) = 1~ and $\nu_2(K) > 0$ ~\nu_2(K) > 0~ is impossible. If $\nu_2(N) = 1$ ~\nu_2(N) = 1~ and $\nu_2(K) = 0$ ~\nu_2(K) = 0~, we may simply apply the solution from subtask $3$ ~3~.

It remains to consider cases where $\nu_2(N) > 1$ ~\nu_2(N) > 1~. If $\nu_2(K) = 0$ ~\nu_2(K) = 0~, we may once again apply the solution from subtask $3$ ~3~. If $\nu_2(K) > 0$ ~\nu_2(K) > 0~, note the previous observation that when we change a $1$ ~1~ to a $-1$ ~-1~ in the array, we are changing the signs of the $K$ ~K~ adjacent subarray products. This inspires the solution of continuously placing adjacent "blocks" of length $K$ ~K~ until the sum of the block lengths is exactly $N/2$ ~N/2~. However, we run into trouble with the cyclic property of the array when $K$ ~K~ is too large. The key observation now is to realize that if a construction works for the pair $(N, K)$ ~(N, K)~, it must also work for the pair $(N, N - K)$ ~(N, N - K)~, which will be left as a short exercise for the reader. With this in mind, we can limit $K \le N/2$ ~K \le N/2~, and we no longer have to worry about the cyclic property. If the blocks of length $K$ ~K~ extend too far (greater than $N/2$ ~N/2~), then we may simply shift the last block backwards by an appropriate amount to accommodate for that. If implemented correctly, the code for this solution should be extremely short.

Time complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Bonus

Can you solve the problem if the array permitted any non-zero integers?

Comments

7

wleung_bvg commented on March 15, 2021, 4:19 a.m.

Interestingly, if the answer is not impossible, a random array of $1$ ~1~ and $-1$ ~-1~ appears to have a decent probability of being valid (I have no idea what the actual probability is). We can start with a random array and use a segment tree to maintain the $N$ ~N~ cyclic subarray products ending at each index, and their sum. We can then check if the sum is $0$ ~0~. If it is, we can print the array and terminate. Otherwise, we can choose a random index $l$ ~l~ to multiply by $-1$ ~-1~. We will also update the range $[l, l + K - 1]$ ~[l, l + K - 1]~ in the segment tree (wrapping around the end) to maintain the subarray product sums. We will repeat this until we have a sum of $0$ ~0~.

3

4fecta commented on March 15, 2021, 5:12 p.m. ← edited →

That's quite interesting indeed. I think the reason this works is due to the birthday paradox rather than a high frequency of verifiable arrays. Even when $99.99\%$ ~99.99\%~ of arrays are non-verifiable, the birthday paradox says that the chance of failure (per case) is about $0.004538\%$ ~0.004538\%~ if you test $100,000$ ~100,000~ different arrays, which a segment tree would allow you to do quite easily. However, one caveat to this solution is that its memory usage is about $\mathcal{O}(2N)$ ~\mathcal{O}(2N)~ at best, whereas the solution given in the editorial can achieve $\mathcal{O}(1)$ ~\mathcal{O}(1)~ memory usage with ease. For now, I have reduced the memory limit to $32\text{MB}$ ~32\text{MB}~ so that excessive memory usage would cause a $\text{MLE}$ ~\text{MLE}~ verdict. Thanks for discovering this solution!

Edit: Adjusted memory limits so that they are appropriate for their corresponding languages.