MARCAPS Editorial

PROBLEM LINK:

Practice
Contest

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

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 ? :-

  1. CodeChef: Practical coding for everyone

Thanks! :slight_smile:

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 CodeChef: Practical coding for everyone

Can anyone tell me where does my solution fail? Any suggestion appreciated.
My solution : irBC3L - Online C++0x Compiler & Debugging Tool - Ideone.com

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.

5 Likes

Wow that’s really helpful !!! Keep up the good work …

1 Like