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

×

PRCS16B - Editorial

PROBLEM LINK:

Practice
Contest

Author: Satyam Kumar
Tester: Parth Mittal
Editorialist: Rounaq Jhunjhunu Wala

DIFFICULTY:

EASY

PREREQUISITES:

Arrays

PROBLEM:

Given a filled array $A$ and an empty array $B$, we need to copy the elements from $A$ to $B$ via the following two operations:
* Copy $A[i]$ to $B[i]$
* Cyclic Shift $B$ 1 position to the right (Shift $b_i$ to $b_{i+1}$ and $b_n$ to $b_1$).
We need to minimize the number of operations to make the elements in $B$ equal.

QUICK EXPLANATION:

Let us try to make all the elements of $A$ equal to some $x$. Then, immediately, we can note that we will need to do at least $N$ copy operations. Further, for all indices such that $B_i \neq x$, we need to move from the nearest $i$ to its left. So the answer would be the maximum distance for that $x$ + $N$. Now we take the minimum over all $x$. Since $x$ is small, we can use an array of vectors.

EXPLANATION:

The question asks you to create the array B. The only thing we need to decide in the problem is the element in $A$ which should be copied to $B$.
For choosing the element, we can devise the following method. We choose the maximum occurring element. But this might not give the optimal answer if the max occurring element is clustered at one place (because we would need to shift the array a lot more number of times).
A better strategy would be to pick an element, whose largest gap between copies is minimum. This comes from tha fact that the minimum (and required) number of copy operations is $|A|$, and hence we need to minimise the number of shift operations, which can be done for an element which doesn't require much shifting. For example, if the array $A = [1,2,1,1,2,1,3]$, we can see that the element 1 has a distance of maximum 1 between any copy, 2 has distance of maximum 3 ($A_5$ to $A_2$), and 3 is a lone element, so we can simply ignore it. Note that we also take wrap-around distances into account because the shift is cyclic. So in the above example, we get 1 as the best element, and we would do $7+1$ operations to copy 1 to $B$.
Complexity: $O(N)$

This question is marked "community wiki".

asked 12 Oct '16, 22:23

rounaqwl66's gravatar image

2★rounaqwl66
263
accept rate: 25%

edited 02 Jan '17, 19:16

admin's gravatar image

0★admin ♦♦
19.7k350498541

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,492
×3,707
×836
×21
×3

question asked: 12 Oct '16, 22:23

question was seen: 427 times

last updated: 02 Jan '17, 19:16