×

# SALARY - Editorial

Author: Ivan Zdomsky
Tester: Anton Lunyov
Editorialist: Anton Lunyov

CAKEWALK

None

# PROBLEM:

You are given the array W[1], W[2], ..., W[N] of salaries of the workers. At each operation you can increase by 1 salaries of any N − 1 workers. Your goal is to make salaries of all the workers to be equal. What is the minimum number of operations needed for this?

# QUICK EXPLANATION:

The answer is just sumW − N * minW, where sumW is the sum of all W[i] and minW is the minimum over all W[i]. See author's solution and tester's first solution as a reference.

# EXPLANATION:

The operation can be treated as follows: we at first decrease salary of some worker by 1 and then increase salaries of all workers by 1. But why do we need to do the second part? Since we want all salaries to be equal the second part of the operation could be simply ignored. So we may assume that at each operation we decrease salary of some worker by 1.

Now if we have some salary greater the minimum salary then without applying operation to it we can't achieve the goal in any way - the minimum could only decreases during operations so this salary will be always not equal to the minimum one. Hence we need to apply at least W[i] − minW operations for the i-th worker. The summation of this over all i is exactly sumW − N * minW. But, clearly, applying exactly W[i] − minW operations to the i-th worker (for all i) makes all salaries to be equal to minW, which is our goal. Therefore, this number of operations is also sufficient. Hence it is the answer as stated above.

# ALTERNATIVE SOLUTION:

The constraints were quite moderate. So alternatively one could model the process of applying all the operations. But the following naive implementation will get TLE: at each step we at first check whether all salaries are equal, if no, then choose the worker with the maximal salary and increase by 1 salaries of all other works. Such solution has complexity O(maxW * N * N) in the worst case that have the form W[1] = 0, W[2] = maxW, W[3] = maxW, ..., W[N] = maxW, where maxW = 10000. Since we also have like 100 tests in a file, such solution could consume more than 8 seconds on one test file. And we indeed have test files having all 100 tests of this or similar form.

In order to get AC with modeling one should at least figure it out the first step of the solution explained above: instead of increasing salaries of N − 1 workers one should decrease salary of just one worker at each operation. But even this will get TLE if it would be implemented as above. The simplest way to make such solution fast enough is to decrease by one all maximum salaries at one step (so we perform several operations at once). Then the solution will have complexity O(maxW * N) and passes the TL easily. Namely now at each step we at first check whether all salaries are equal and if no we find the maximal salary and then decrease by 1 all salaries equal to this maximum. See tester's second solutions as a reference.

# AUTHOR'S AND TESTER'S SOLUTIONS:

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

# RELATED PROBLEMS:

This question is marked "community wiki".

6.7k62119138
accept rate: 12%

 11 @herman look this thing in this way... increasing salary of (n-1) workers is like all the (n-1) workers get 1 point each and the 1 worker left gets a 0 ..but we are concerned with the number of moves we need to perform to make all salaries equal which will be equal to the scenario where we just decrease the salary of a worker by 1.. i.e now instead of giving 1 point we give 0 point each to (n-1) workers and -1 point to the unlucky worker :-) and this unlucky one is the one having salary higher than the minimum salary... I hope u will get my point.. answered 15 Jan '13, 19:36 645●2●4●11 accept rate: 0% yup...thnx a lot. (16 Jan '13, 19:35) herman2★ this one is a lot simple and better explanation than the above (29 Jun '13, 00:38)
 4 I did what the question said by increasing 1 to get all the salaries equal in an O(N) solution for each case. 1- Sort the list of salaries in increasing order. 2- In each step and starting from the last term I need to make seq[i - 1] = seq[i]. Each step needs (N - i) * (seq[i] - seq[i - 1]). The final answer becomes (seq[N - 1] - seq[N - 2]) + (2 * (seq[N - 2] - seq[N - 3]) + ... + (N - 1) * (seq[1] - seq[0]). I think this is a simple explanation. In case u need an example I'm ready to give one :) answered 15 Jan '13, 23:06 4★bondoc73 106●2●4●10 accept rate: 10%
 2 I think any Cakewalk problem can be used here as related problem :) Especially if it also has almost no pre-requisites or very simple ones... For example, LEBOMBS and also maybe, SAD. answered 15 Jan '13, 15:58 3★kuruma 17.7k●72●143●209 accept rate: 8% 1 I have added DRGNBOOL and LECANDY. Yours both seems too straightforward like just do what is written in the problem statement. But thanks for your effort. (15 Jan '13, 21:56)
 0 I tried doing this in the opposite way! I took max of the array and for each element of the array a[i] sum+=max-a[i] but I dunno why I was getting wrong answer! anybody help? answered 15 Jan '13, 18:09 2★big_d 76●1●3 accept rate: 0% 2 Consider test case: 3 0 2 2 The answer is 4 but your answer is 2 if I understand all properly. (15 Jan '13, 21:45) yup! thank you :) (16 Jan '13, 20:42) big_d2★
 0 though we are getting answer from tester's second approach but can someone plz elaborate what is the reason behind decreasing maximum element by 1...is there any logic or it is just an observation? answered 15 Jan '13, 19:00 2★herman 51●4●5●12 accept rate: 0% let 7,8,12 then to make all the numbers equal, we'll have to keep 12 as it is and increase the others ,otherwise if we'll increase all the numbers then, they never gonna be equal . 7,8,12 increase first and second number 8,9,12 increase first and second number 9,10,12 increase first and second number 10,11,12 increase first and second number 11,12,12 increase only first number 12,12,12 all are equal. so keep the max constant and increase all the other numbers or in other words we can say decrease the max by 1 and then increase all the numbers by 1. max-1+1=max (16 Jan '13, 14:44) akrai482★ 1 You are wrong. We can't get 12,12,12 from 11,12,12. Next we should increase 11 and 12 to get 12,13,12 and then we increase 12 and 12 to get 13,13,13. (16 Jan '13, 14:51)
 0 I used the same logic but getting wrong ans during submission .... Any reason ???? answered 15 Jan '13, 20:41 2★sonuk7 12●2 accept rate: 0% 1 Actually you get TLE and it is expected for your solution. The test case where your program works too slow is described in the editorial. But I repeat here: T = 100 N = 100 for each test salaries are {0, 10000, 10000, ..., 10000} for each test (15 Jan '13, 21:43)
 0 I didn't use this approach. Here is my approach. 1) I determine the MAX of the array and the MIN. The difference of MAX and MIN gives rise to DELTA. 2) Then, I consider the first element with value MAX and increase the salaries of all the other elements by delta. 3) The above can give rise to a new set of MAX and MIN and thus DELTA. I re-compute DELTA and iterate the above operation of selecting the element with a value of MAX and increase salaries of other elements by DELTA. 4) This operation is repeated until DELTA becomes equal to 0. Yet I am getting a wrong answer. Can you please see point out my mistake. This problem is very simple yet :( answered 15 Jan '13, 22:59 31●1●2●3 accept rate: 0% 1 Actually, the only your mistake is that you did not print the newline after the answer for each test. Fixing this give AC: http://www.codechef.com/viewsolution/1724864 I was noticed this during the contest but, of course, I could not pointed out this to you. (15 Jan '13, 23:12) Oh Dear Lord!!! Thanks anton_lunyov for answering. I was baffled whether there is something wrong with my approach because this is such an easy problem. Thanks again. (15 Jan '13, 23:14) hi anton_lunyov, I am getting a wrong answer despite putting a new line character. http://www.codechef.com/viewsolution/1724887 Can you please guide. (15 Jan '13, 23:23) hi.. don't bother. I got my mistake :) (15 Jan '13, 23:30)
 0 Can someone explain this to me in a little bit easier way? link This answer is marked "community wiki". answered 18 Mar '17, 16:26 1 accept rate: 0% Read both my answers there- https://discuss.codechef.com/questions/91459/explaniation-for-the-salary-editorial?page=1#91462 (18 Mar '17, 18:55)
 0 Can anyone pls tell me how to optimise this code : https://www.codechef.com/viewsolution/16553743 I am using Merge Sort AFAIK its the best sorting algorithm for time complexity but still Code Chef compiler says time limit exceeded. Kindly help me out in optimising it ! answered 11 Dec '17, 18:24 0★adarshbl 1 accept rate: 0%
 0 in the given test case 3 1 2 3 can i can do it in 2 steps? by stopping 3 for the first 2 3 3 and now stopping 2 and 3 we get 3 3 3  answered 27 Feb '18, 01:24 3★vartult 1 accept rate: 0%
 0 @Vartult: You can't stop 2 numbers at a time according to the question,"choose some worker and increase by 1 salary of each worker, except the salary of the chosen worker".Here it is given as worker and not as workers. So 2 3 3 >>> 3 4 3 >>> 4 4 4 answered 01 Mar '18, 20:34 1 accept rate: 0%
 0 what can I do to optimise this code? https://www.codechef.com/viewsolution/20272381 answered 22 Sep '18, 17:57 0●2 accept rate: 0%

# include<conio.h>

using namespace std; int main() { int t,n,a[100],small=10001,sum=0,tot_sum=0; cin>>t; for(int i=0;i<t;i++) {="" cin="">>n; for(int j=0;j<n;j++) {="" cin="">>a[j]; if(small>a[j]) { small=a[j]; } } for(int k=0;k<n;k++) { sum=a[k]-small; tot_sum+=sum; } cout<<tot_sum;

}


} ........................................................... Its output is correct ......why it is not getting accepted

1
accept rate: 0%

 0 here is my approach using binary_search! def main(): #codechef question SALARY t = input() t = int(t) while t > 0: n = input() n = int(n) val = list(map(int, input().split(" "))) initial_sum = sum(val) min_value = min(val) left = 0 right = 10000000000 while left <= right: mid = (left + right) // 2 may_be = initial_sum + (mid * (n-1)) mean = may_be / n diff = mean - min_value if diff == mid: break elif diff < mid: right = mid - 1 else: left = mid + 1 print(mid) t -= 1  if name == 'main': main() answered 22 Feb, 00:08 1 accept rate: 0%
 0 Can anyone please tell me the derivation of that formula? answered 25 Feb, 23:14 1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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,851
×1,688
×968
×19
×8

question asked: 15 Jan '13, 15:00

question was seen: 15,158 times

last updated: 25 Feb, 23:14