## 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

This subtask was intended to reward brute force solutions.

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

From here on, we will define of a positive integer as the highest integer exponent such that divides (also known as the -adic order of ). This subtask provides the constraint that .

First, consider the case where , in other words when is odd. If , then it is not hard to see that the construction of alternating s and s is verifiable. For cases where , consider the repeated homothetic (rescaling) reduction by a factor of until . Note that since , it is guaranteed that when reaches , since a homothetic reduction by a factor of reduces both values by . This inspires the construction of alternating blocks of s and s where each block has a size of , and that is sufficient to pass this subtask.

Time complexity: For full marks, first consider the impossible cases. Clearly is impossible since there is only subarray of length , which is guaranteed to have a non-zero product. Also, is impossible since the parity of the final sum would be odd. Thus, we now only consider cases where and .

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

It remains to consider cases where . If , we may once again apply the solution from subtask . If , note the previous observation that when we change a to a in the array, we are changing the signs of the adjacent subarray products. This inspires the solution of continuously placing adjacent "blocks" of length until the sum of the block lengths is exactly . However, we run into trouble with the cyclic property of the array when is too large. The key observation now is to realize that if a construction works for the pair , it must also work for the pair , which will be left as a short exercise for the reader. With this in mind, we can limit , and we no longer have to worry about the cyclic property. If the blocks of length extend too far (greater than ), 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: #### Bonus

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

Interestingly, if the answer is not impossible, a random array of and 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 cyclic subarray products ending at each index, and their sum. We can then check if the sum is . If it is, we can print the array and terminate. Otherwise, we can choose a random index to multiply by . We will also update the range in the segment tree (wrapping around the end) to maintain the subarray product sums. We will repeat this until we have a sum of .
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 of arrays are non-verifiable, the birthday paradox says that the chance of failure (per case) is about if you test 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 at best, whereas the solution given in the editorial can achieve memory usage with ease. For now, I have reduced the memory limit to so that excessive memory usage would cause a verdict. Thanks for discovering this solution!