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

×

CHEFHAM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Mugurel Ionut Andreica
Editorialist: Kirill Gulin

PROBLEM

You're given an array $a$ of size $N$, each number in the array appears no more than twice. Shuffle the array in such a way that the Hamming distance between the original and the shuffled array is maximized. The Hamming distance between two arrays $a$ and $b$ is the number of indexes $i$ such that $a_i \neq b_i$.

QUICK EXPLANATION

Count how many numbers in the array have their frequences equal to $1$ or $2$. Solve the problem depending on are these numbers more than $1$.

EXPLANATION

Subtask 1

All elements in the array are unique. Just cyclically shift the array. So for the first substask the answer is $0$ if $N = 1$ and $N$ if $N \geq 2$.

Subtask 2

If you pass only the second subtask it means you missed some corner cases while solving the 3rd subtask.

Subtask 3

For each number existing in the array count its frequence. Suppose there are $x$ numbers with their frequence equal to $1$ and $y$ numbers with frequence equal to $2$.

Suppose $x, y \geq 2$. We can separately shuffle the numbers with frequence $1$ and with frequence $2$, getting the answer equal to $N$ for this case. Shuffling here and below means you'll need to write out indexes of number's entries and set the other number on its entries (for example, cyclically shift the array of indexes by 1). For example, if the array is $[a, b, c, d, d, c]$ you'll get an array $[b, a, d, c, c, d]$ after such a shuffle.

There are two ways of solving the problem now: random shuffle and dealing with corner cases.

The first way

Random shuffle the array several times and choose the one with the maximum Hamming distance. The answer you've got is correct with high enough probability.

The second way

Suppose $x = 1$ and $y \geq 2$. Then shuffle only the numbers with frequence $2$ and swap the number with frequence $1$ with any other number.

Suppose $x \geq 2$ and $y = 1$. Then shuffle only the numbers with frequence $1$ and swap the indexes of the number with frequence $2$ with any two other different indexes.

After these cases, $N \leq 4$ so you can try all possible shuffles of the array in $O(N!)$ time. But still sorting out the cases is possible :)

If $x = 2, y = 0$ then $N = 2$. Just swap the values.

Cases with $x = 0, y = 2$ or $x = y = 1$ or $x = 1, y = 0$ or $x = 0, y = 1$ are left. For any of them you can cyclically shift the array twice. Calculate the Hamming distance and print the answer.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 13 Dec '17, 22:30

kefaa's gravatar image

6★kefaa
1148
accept rate: 0%

edited 21 Dec '17, 02:27


Could you share the source code of your proposed solution? Thanks

link

answered 16 Dec '17, 08:07

ryuxin's gravatar image

3★ryuxin
1
accept rate: 0%

I followed a different approach which was more easy to code. In this method you have to keep track of the indexes of the element using structures.

The outline of my solution is to compare to adjacent elements and swap them if they are different, else swap these two elements with the next two elements. Then you have to take care of some corner cases like odd number of elements, one element array, and few more. But it was easy to code.

link

answered 17 Dec '17, 14:46

gomu's gravatar image

4★gomu
2084
accept rate: 5%

My approach:

For n=2, swap values.

For n>2, sort indexes according to the value on that index. Then shift it by 2. This will ensure maximum hamming distance.

Code

link

answered 17 Dec '17, 15:37

dushsingh1995's gravatar image

4★dushsingh1995
92313
accept rate: 11%

I followed a simpler approach, i just shift the whole array to the right, and when I have v[i] = v[i-1] so i just swap(v[i-1],v[i+1])

link

answered 17 Dec '17, 15:38

we7d's gravatar image

2★we7d
222
accept rate: 0%

edited 17 Dec '17, 15:38

counted occurences of each digit calculated possible area of rotation https://www.codechef.com/viewsolution/16510278

link

answered 31 Dec '17, 19:30

paranoia's gravatar image

3★paranoia
1
accept rate: 0%

Rotate the array approx 100 times and check for maximum hamming distance. At last print the best you have got during the 100 rotations.
My Solution: https://www.codechef.com/viewsolution/19845450

link

answered 24 Aug '18, 20:30

srvptk's gravatar image

3★srvptk
102
accept rate: 0%

toggle preview
Preview

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,684
×188
×7

question asked: 13 Dec '17, 22:30

question was seen: 1,737 times

last updated: 31 Dec '17, 19:30