PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Proving lemmas, Observations.
PROBLEM:
Given N cities arranged in a cycle form, and distance between each adjacent city pair is given, except some were lost. We need to tell whether we can assign distances so that for every city, so each city has one opposite city.
For city i, Opposite city is such city j \neq i such that the clockwise distance between cities i and j is equal to the counterclockwise distance between these cities.
OBSERVATIONS
- Every city may have at most one opposite city.
- If city A is opposite to city B, city be is also opposite to city A.
- No possible assignment exist for odd N.
- Answer exist if and only if we can assign distances such that A[i] == A[N/2+i] for all 0 \leq i < N/2.
EXPLANATION
Beware light hearted proof fearing people, this problem is not for those who don’t like lemmas. (Just kidding)
We’ll be discussing lemmas after which you’ll yourself find out the answer immediately.
Lemma 1: Any City x can have at most 1 opposite city.
I’ll be using proof by contradiction because i like to contradict :P.
Suppose there are two cities X and Y opposite to city A after assigning all missing distances. Let sum of all distances be S. Since A and X are opposite, distance between A and X is same in both clockwise and counter-clockwise direction and is same as S/2. But Y is also opposite to A, this means that distance between A and Y is also S/2. But the only city at distance S/2 from A is X. Distance between X and Y has to be 0. But Zero distance would mean merging of cities, which is not allowed, thus, contradicting the fact that A has two opposite cities. Thus, Any city can have at most one opposite city.
Lemma 2: If city A is opposite to city B, city be is also opposite to city A.
This is easy to prove. distance between A and B is S/2 which is same as distance be between B and A.
Lemma 3: For every city to have one opposite city, the necessary and sufficient condition is A[i] == A[i+N/2].
Proof: Now we are going to use Mathematical Induction type proof. Assume city X and Y are opposite. We have to prove that Cities X+1 and Y+1 are opposite if and only if A[X] == A[Y].
Let D(a,b) be distance between city A and B in clockwise direction.
We know, Distance between X and Y clockwise is A[X] + D(X+1,Y) which is same as S/2. Lets write D(X+1, Y) = S/2 - A[X].
For city X+1 and Y+1 to be opposite, we need D(X+1, Y+1) == S/2. which is same as D(X+1, Y)+A[Y] == S/2.
Substituting D(X+1, Y) in this equation, required condition becomes S/2 - A[X]+A[Y] == S/2 which implies A[X] == A[Y] as required condition for Cities X+1 and Y+1 to be opposite, given cities X and Y are opposite.
One more thing, If City X and Y are opposite, we can see that city X+1 can be opposite only with a city after Y, say city Z, since if Z lies on path of X and Y, D(X+1, Z) < D(X, Y) == S/2. This way, we can see that in an arrangement where every city has opposite city, the city opposite to ith city can only be (i+N/2)th city.
This completes all our proofs for today, so, I guess you all have guess the answer, so give it one more try, after all these observations.
Now, All that is left in problem is to make A[i] same as A[i+N/2] for all 0\leq i < N/2. If we cannot, answer is NO. If either of i and i+N/2 are not assigned, assign them the value of other one. If both are unassigned, we can assign them any value, but we need to minimize total distance, so we will assign them minimum possible distance, which is 1.
So, with this, our editorial-cum-proofs ends, Have a look at implementation if you still need help.
Edit: Proof that answer doesn’t exist for odd N, is that we get pairs of cities which are opposite to each other. The last city remaining cannot be opposite to any other city, making final assignment invalid.
TIME COMPLEXITY
Time complexity is O(N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Edit: Until above solutions are not available, you may refer solution here.
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
). Everytime I see you in the editorialist panel I feel twice more enthusiastic to give the contest knowing that the best quality editorials would be waiting (written by our one and only you!!) for me once the contest is over, and I’d learn a lot from them. Please keep posting editorials just like this!! I am a huge fan of yours 