Editorial for COCI '07 Contest 2 #5 Kemija
Submitting an official solution before solving the problem yourself is a bannable offence.
For smaller inputs (all numbers up to ) we can try all possible pairs of values for the first two numbers in the ring (which uniquely determines all remaining numbers), calculate all remaining numbers and check if the ring generated by adding neighbours to a number is equal to the input ring.
For larger rings, the solution is much more complex. Label the numbers in the first ring to , and the second ring to . We need to find a ring such that it generates ring , and that all numbers in it are positive.
First, notice that the sum of ring must be exactly one third of the sum of ring .
Also, from the input ring we can determine for each position the difference . This, with the sum of ring , suffices to solve the task.
When the length of ring is not divisible by , the solution is unique. Suppose the first element of the ring () equals . From the calculated differences we determine . Because is relatively prime to , we will have determined all numbers to before returning to . We just need to ensure that the sum of ring is appropriate (one third of the sum of ring ). For this it suffices to add to each element of the value of the expression .
When is divisible by , the solution is not unique and it is less obvious how to ensure that the numbers are positive. This time the differences generate three separate "chains":
- ;
- ;
- .
We need to determine the numbers , and (and increase the numbers in their respective chains so that the differences are right) so that all numbers are positive and that the sum of ring is correct. It is not hard to show that a ring which satisfies this generates the input ring .
For each of the chains, it is possible to determine the smallest possible value of the first number so that all numbers in the chain are positive. For example, if the differences generate the chain , then we need to add at least to all numbers so that all numbers are positive.
We can set to the smallest value so that the first chain is positive (in the previous example would be ) and similarly for and the second chain. is uniquely determined by the expression .
Comments