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

×

CHEFMOVR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Primary Tester: Prateek Gupta
Editorialist: Hussain Kara Fallah

PROBLEM EXPLANATION

Given an array consisting of n integers, Chef wants to make all elements of this array equal. He can apply the following operation:

Pick 2 numbers

(i,j) :: j = i + D

Decrementing $A_i$ OR $A_j$ by 1 and adding 1 to the other element. Please help chef by telling the minimum number of operations he needs to make all elements equal, or tell that such situation is impossible.

DIFFICULTY:

PREREQUISITES:

simple

EXPLANATION:

Applying our operation any number of times would keep the sum of elements in our array the same. (Since we are subtracting one from an arbitrary number and adding it to another one), so the sum of our numbers must be divisible by n

The final value of each element would be equal to $\frac{sum}{n}$

In any operation chef would choose 2 numbers (i,j):

(i,j) :: j = i + D

j mod D = i mod D

So you can notice that any pair of elements Ai , Aj such that j mod D ≠ i mod D are independent from each other. (That's true).

That means that we should group our elements by the remainder of their indexes after dividing by D. (And of course) solve each one independently. In fact we will have D groups, the ith group (0 ≤ i < D) contains all elements Aj (j mod D = i)

Let's tell now about handling each set, applying our operation any number of times would keep the sum of elements in our set the same. So the sum of elements in each set must be divisible by this set's size and of course the result of this division must be equal to $\frac{sum}{n}$ , having one set violating this condition would make Chef's mission impossible.

Let's now move to finding the minimum number of operations to fix each set, each set would have 3 kinds of numbers (numbers > $\frac{sum}{n}$) and (numbers < $\frac{sum}{n}$) and of course (numbers equal to $\frac{sum}{n}$) -that we can omit-.

Let's process numbers of each set in the same order of the array (from left to right) and separate them into 2 groups as described (first two types since we can omit the third). Maintaining 2 pointers each one iterating on the elements of one group, would just do the job, because if our processed element is less than $\frac{sum}{n}$ then optimal choice would be picking this number along with the closest number bigger than $\frac{sum}{n}$ to the right of it (the same when the opposite happens), and we should add the distance between them for each increment\decrement operation we apply (because we are using elements between them as mediators). After each iteration, one of the numbers referred to by out pointers would reach the desired value, so we move the pointer on. Practically, this part can be done in simpler way (like author's solution), but this is the detailed explanation. The implementation of this editorial can be found in my code.

AUTHOR'S AND TESTER'S SOLUTIONS:

AUTHOR's solution: Can be found here
TESTER's solution: Can be found here
EDITORIALIST's solution: Can be found here

This question is marked "community wiki".

asked 11 Aug '17, 14:17

deadwing97's gravatar image

3★deadwing97
118822
accept rate: 0%

edited 18 Aug '17, 15:26

admin's gravatar image

0★admin ♦♦
19.0k348495533


I solved this problem easier.

First I determined the target value (as explained in editorial).

Go through the array right to left. At each index, we take as many units from the left corresponding array index (if there is one) as is necessary to bring the value to the target.

If the resulting array is equal, we output it. Otherwise, no solution exists.

Example:

  1. [3, 2, 5, 1, 4], size of mover = 1
  2. [3, 2, 5, 2, 3]
  3. [3, 2, 4, 3, 3]
  4. [3, 3, 3, 3, 3]
  5. [3, 3, 3, 3, 3].

Resulting array is equal, so we output it.

link

answered 18 Aug '17, 16:30

sapfire's gravatar image

3★sapfire
412
accept rate: 0%

The problem PRLADDU set by me is a subproblem of this problem. Its editorial is really nicely written and explains a nice way of proving the greedy approach of this solution.

link

answered 18 Aug '17, 16:49

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k52132169
accept rate: 20%

edited 18 Aug '17, 16:50

Candy3 from spoj is also a subproblem of this problem.

(19 Aug '17, 22:57) siddharthp5384★

is there anybody who has an easy solution for this question . I can only understand this solution upto this line

In any operation chef would choose 2 numbers (i,j):

After that I cannot understand what is the solution trying to tell . somewhere its saying j mod d = I mod d then saying j mod d is not equal to d ??? I cannot understand this after the line above.

please help . thanks in advance

link

answered 19 Aug '17, 19:53

geforce's gravatar image

2★geforce
476
accept rate: 0%

try out some examples of different size and different D. you will notice that for some values there will be a range of elements which are not accessible. if all values are same after operations then possibly all element were accessible. see my code for understanding https://www.codechef.com/viewsolution/14804664

(19 Aug '17, 20:15) aminuteman1★
Answer is hidden as author is suspended. Click here to view.

answered 19 Aug '17, 19:59

raj79's gravatar image

4★raj79
(suspended)
accept rate: 10%

Can anyone please explain to me why there's this condition in Author's solution? Thanks

       if (curSum % cnt != 0) {
                ans = -1;
                break;
            }
link

answered 21 Aug '17, 09:26

kunnu120's gravatar image

2★kunnu120
5079
accept rate: 5%

edited 21 Aug '17, 10:22

As in the editorial reduce the problem to $D$ independent subproblems - one for each subset based on residue$\mod D$.

Let $a_1, a_2, ... a_k$ be such a subset. A move operation is performed on two adjacent elements in this subset. Let $\bar a$ be the target (mean) value. Consider partial sums $s_i=\sum_{j=1}^i a_j$. Each $s_i$ for $i < k$ has to be brought to the target value $i \bar a$. $s_k$ must be at the target value, otherwise the mission is unachievable. Observe that a move between $a_i$ and $a_{i+1}$ affects exactly one partial sum - $s_i$, and it changes it by 1. So for each $1 \le i \le k - 1$ we need at least $|s_i - i \bar a| = |\sum_{j=1}^i a_j - i\bar a|=|\sum_{j=1}^i (a_j - \bar a)|$ moves to bring $s_i$ to its target value.

Thus we have the following lower bound for the number of moves: $$\sum_{i=1}^{k-1} \left| \sum_{j=1}^i (a_j - \bar a)\right|$$

It's easy to show that as long as the condition for $s_k$ is satisfied, this bound is always achievable. At each iteration let $a_i, i < k$ be the first element not equal to $\bar a$. If there is no such element - we are done. If $a_i > \bar a$ perform a move operation to $a_{i+1}$. Otherwise, let $j > i$ be the first such that $a_j > 0$ (it must exist). Perform a move operation to $a_{j-1}$. Since at each iteration a partial sum gets closer to its target value by 1, the total number of moves will be equal to the bound.

Here is the code.

link

answered 23 Aug '17, 01:50

eugalt's gravatar image

4★eugalt
1584
accept rate: 5%

edited 23 Aug '17, 03:22

I am doing the same thing as AUTHOR's solution in C, but still I am getting WA in Task 3 of Sub-Task 2.

include<stdio.h>

include<stdlib.h>

include<math.h>

int main(void) { long long int t,n,d,i,sum,di,a[100015],f,c,j,s,ans; scanf("%lld",&t); while(t--) { scanf("%lld%lld",&n,&d); sum=0; for(i=0;i<n;i++) { scanf("%lld",&a[i]); sum+=a[i]; } ans=0; if(sum%n==0) { di=sum/n; for(i=0;i<d;i++) { s=f=c=0; for(j=i;j<n;j+=d) { s+=a[j]-di; ans+=abs(s); c+=a[j]; f++; } if(c%f!=0) { ans=-1; break; } } } else ans=-1; printf("%lld\n",ans); } return 0; } Can you please see where am I getting it wrong?

link

answered 25 Aug '17, 22:39

arnab_11's gravatar image

2★arnab_11
1
accept rate: 0%

The link to solution wrong.

link

answered 01 Sep '17, 08:39

prateekcoding's gravatar image

3★prateekcoding
11
accept rate: 0%

edited 18 Sep '17, 17:42

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:

×14,429
×865
×504
×193
×9

question asked: 11 Aug '17, 14:17

question was seen: 1,601 times

last updated: 18 Sep '17, 17:42