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 
Can anyone please see my solution: CodeChef: Practical coding for everyone
I have done exactly the same as ‘tourist’ did.
Please let me know the reason of WA. 
Unable to find it.
For n>4, the polygon need not be regular, but should have the opposite sides of equal length.
Solutions links are not working, please fix it.
Thanks.
1 Like
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 
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?
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
@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.
https://www.codechef.com/viewsolution/20452504
Find the error and provide the test case for which it fails please.
Man, fix the solution links!
1 Like
You’ve printed “-1” for odd n. It should be “NO”.
Posting ideone links.
Added ideone link for solution.
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.
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.