OPPOSITE - EDITORIAL

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. :slight_smile:

3 Likes

i used the approach that if its a 4 sided polygon it should be a square or a rectangle but if n>4 it should be a regular polygon…and got 30 pts. can u please tell where have i gone wrong :frowning:

Man, fix the solution links!

1 Like

Can anyone please see my solution: https://www.codechef.com/viewsolution/20385781
I have done exactly the same as ‘tourist’ did.
Please let me know the reason of WA. :frowning:
Unable to find it.

@bidibaaz123

For n>4, the polygon need not be regular, but should have the opposite sides of equal length.

You’ve printed “-1” for odd n. It should be “NO”.

Solutions links are not working, please fix it.
Thanks.

1 Like

Posting ideone links.

Oh!

I couldn’t even think of that first half of the array was to be made equal to second half of it. Thank you for all the insightful lemmas and their proofs!! Really helpful! I was not very confident on no answer existing for odd n but with that proof its all clear :slight_smile:

I have been following your editorials since your ICO preparation round and I must say they are awesome!! They are the best in the discussion forum here, and I love the way how you concisely and elegantly explain the concepts and deliver the editorial on time. (The dp ones are little tough to understand, please make them also easy to understand like you do to all others using your magic :wink: ). 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 :smiley:

Added ideone link for solution.

whats wrong in my solution??
https://www.codechef.com/viewsolution/20402991

This was an amazing problem. Once we get the lemmas, I can understand how we can go about proving it. But I had a lot of difficulty finding lemma 3, and hence got only 30 points. Can you give the intuition behind finding lemma 3?

@vidhan_123
You wrote “N0” instead of “NO”.

Whats wrong with my solution it is working fine with subtask 2 and 3 but gives wrong answer for subtask 1 .
https://www.codechef.com/viewsolution/20391532

In 3rd lemma proof, how come distance D(X,Y) is same as D(X+1,Y+1) which is assumed as S/2 ? They may have different distance.

Let’s say all the cities are placed on a circle so the city opposite to the current city will be the diametrically opposite point on that circle. Now suppose our next city is at distance x from A1 then the diametrically opposite point will be x distance far from the city diametrically opposite to the previous city.
Suppose we have A2 city x distance away from A1 and B1 is the city opposite to A1 then city B2 which is opposite to A2 will be x distance away from B1.
Every city must have an opposite point so it is clear that odd number of cities cannot follow the conditions.
Now we can just start from city 1 and n/2 and check if the distance between the next cities are same or not.
If both the distances are not available then we give both of them the value 1 to minimize the total distance.
If one of them is available then we give the same value to the other. If both are available and are not equal then it is not possible to find an answer.
You can check my solution for more clarity
Solution Link

Yes, perfect.

Suppose S be distance to move From A back to A, moving in one direction. Then, opposite city is the city as distance S/2.

@sanket2000 you just need to remove the break statement on line number 45 as you must take all the input then only you should print answer.

you just need to remove the break statement on line number 45 as you must take all the input then only you should print answer.