PROBLEM LINK:Author: Erfan alimohammadi DIFFICULTY:Easy PREREQUISITES:None PROBLEM:Chef has $N$ markers. There is a cap on each marker. For each valid $i$, the $i_{th}$ marker has colour $a_i$. Initially, for each valid $i$, the colour of the cap on the $i_{th}$ marker is also $a_i$. Chef wants to rearrange the caps in such a way that no marker has the same color as its cap. (Obviously, each marker must have exactly one cap.) Can he do that? If he can, find one such way to rearrange the caps. If there are multiple solutions, you may find anyone. EXPLANATIONIf there's one color such that there's more than $\lfloor \frac{N}{2} \rfloor$ pens having this color then it's impossible to do the task. Because if for each pen we bring one cap from different color, at least one pen of these won't have any remaining different cap to match with it. Let's sort pens according to their color value (sorting itself is not important) but we need to make sure that all pens that have the same color are consecutive in the sorted list. Let $h=\lfloor \frac{N}{2} \rfloor$ and let's assume that the list is 0indexed. For the $i_{th}$ pen in the sorted list that has color $a_i$ let's match it with the $((i+h)\, mod\, N)_{th}$ pen cap. It's guaranteed that we would have a different color. According to our hypothesis that we can't have more than $h$ pens having the same color, and since each color's pens are consecutive. Definitely, our cap will have a different color. (Think about it a little bit). AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 26 Mar, 00:01

nice editorial. any test case where this code would fail. https://www.ideone.com/s8MNJ9 answered 26 Mar, 01:34

I have a very weird solution which works! Can you provide any testcase where it may fail ? : 1) https://www.codechef.com/viewsolution/23671648 Thanks! :) answered 26 Mar, 02:44

I am implementing the same logic still getting wrong answer. Here is my solution https://www.codechef.com/viewsolution/23664693 answered 26 Mar, 10:43
sorry for wrong link to solution correct link is https://www.codechef.com/viewsolution/23672298
(26 Mar, 12:25)
