This Forum is in read only mode now.

You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 26 Mar, 00:01

deadwing97's gravatar image

3★deadwing97
1181234
accept rate: 0%

edited 26 Mar, 00:35

nehak_21's gravatar image

0★nehak_21 ♦♦
11


nice editorial. any test case where this code would fail. https://www.ideone.com/s8MNJ9

link

answered 26 Mar, 01:34

aditya_dope's gravatar image

3★aditya_dope
1
accept rate: 0%

1

1

7

2 5 5 4 2 2 5

(26 Mar, 01:58) swetankmodi ♦♦6★

I have a very weird solution which works!

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

1) https://www.codechef.com/viewsolution/23671648

Thanks! :-)

link

answered 26 Mar, 02:44

secrex's gravatar image

4★secrex
1
accept rate: 0%

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

link

answered 26 Mar, 10:43

onbit_syn's gravatar image

3★onbit_syn
1
accept rate: 0%

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

(26 Mar, 12:25) onbit_syn3★

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,877
×3,828
×974
×26
×6

question asked: 26 Mar, 00:01

question was seen: 403 times

last updated: 26 Mar, 12:25