You are not logged in. Please login at www.codechef.com to post your questions!

×

# OPPOSITE - EDITORIAL

Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

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:

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

This question is marked "community wiki".

asked 30 Sep '18, 01:07 4.0k31104
accept rate: 22%

1

Man, fix the solution links!

(30 Sep '18, 08:33)

(30 Sep '18, 11:50)

 0 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 answered 30 Sep '18, 20:31 86●3 accept rate: 37% Yes, perfect. (30 Sep '18, 20:33)
 1 Solutions links are not working, please fix it. Thanks. answered 30 Sep '18, 10:12 2★xtraepic 11●1 accept rate: 0% Posting ideone links. (30 Sep '18, 11:02)
 0 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 :( answered 30 Sep '18, 04:27 1 accept rate: 0%
 0 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. :( Unable to find it. answered 30 Sep '18, 09:19 1 accept rate: 0% You've printed "-1" for odd n. It should be "NO". (30 Sep '18, 09:49)
 0 For n>4, the polygon need not be regular, but should have the opposite sides of equal length. answered 30 Sep '18, 09:40 1 accept rate: 0%
 0 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 :) 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 ;) ). 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 :D answered 30 Sep '18, 11:04 35●2 accept rate: 0%
 0 whats wrong in my solution?? https://www.codechef.com/viewsolution/20402991 answered 30 Sep '18, 12:37 0 accept rate: 0%
 0 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? answered 30 Sep '18, 12:41 124●5 accept rate: 7%
 0 @vidhan_123 You wrote "N0" instead of "NO". answered 30 Sep '18, 12:49 57●4 accept rate: 25%
 0 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 answered 30 Sep '18, 13:42 0 accept rate: 0% 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. (01 Oct '18, 02:42)
 0 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. answered 30 Sep '18, 18:43 2★user913 1●1 accept rate: 0% 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. (30 Sep '18, 20:34)
 0 @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. answered 30 Sep '18, 20:43 86●3 accept rate: 37%
 0 https://www.codechef.com/viewsolution/20452504 Find the error and provide the test case for which it fails please. answered 03 Oct '18, 23:13 1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,820
×968
×724
×264
×48
×48
×10

question asked: 30 Sep '18, 01:07

question was seen: 2,284 times

last updated: 03 Oct '18, 23:13