# MARCAPS Editorial

Tester & Editorialist: Hussain Kara Fallah

Easy

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

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

AUTHORâ€™s solution

TESTERâ€™s solution

6 Likes

nice editorial.
any test case where this code would fail.

I have a very weird solution which works!

Can you provide any test-case where it may fail ? :-

Thanks!

I am implementing the same logic still getting wrong answer. Here is my solution
https://www.codechef.com/viewsolution/23664693

1

7

2 5 5 4 2 2 5

1 Like

sorry for wrong link to solution correct link is https://www.codechef.com/viewsolution/23672298

Can anyone tell me where does my solution fail? Any suggestion appreciated.
My solution : https://ideone.com/irBC3L

The output for 1st Example test case is wrong.
It should be 2 2 3 3 3 1 1 1 2.
Correct it.

I tried explaining this question in my blog. I have tried to go very easy on beginners.
https://codeforces.com/blog/naruhodou

5 Likes

Wow thatâ€™s really helpful !!! Keep up the good work â€¦

1 Like