Editorial for DMOPC '20 Contest 4 P5 - Cyclic Cypher
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
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.
Can you solve the problem if the array permitted any non-zero integers?