PROBLEM LINK:
Author: Erfan alimohammadi
Tester & Editorialist: Hussain Kara Fallah
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.
EXPLANATION
If 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 0-indexed.
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).