SALARY - Editorial

editorial
, , , ,
5

@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 :slight_smile: and this unlucky one is the one having salary higher than the minimum salary…

I hope u will get my point…

23 Likes
6

I used the same logic but getting wrong ans during submission … Any reason ???

1 Like
7

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 :frowning:

2 Likes
8

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 :slight_smile:

7 Likes
9

Can someone explain this to me in a little bit easier way?

10

Can anyone pls tell me how to optimise this code : CodeChef: Practical coding for everyone

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 !

11

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
2 Likes
12

@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

13

what can I do to optimise this code?
https://www.codechef.com/viewsolution/20272381

14

#include
#include<stdio.h>
#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

15

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()

16

Can anyone please tell me the derivation of that formula?

3 Likes
17

I am getting correct ans for my test case. But codechef compiler is giving time sigtstp error.



	int T,N,moves,minW;
	long sum = 0;
	cin >> T;
	
	for(int t=0; t<T; t++)
	{
	    cin >> N;
	    vector<int> W(N);
	    
	    for(int i=0; i<N; i++)
	        {
	            cin >> W[i];
	            sum += W[i];
	        }
	    
	    minW = *min_element(W.begin(),W.end());
	    
	    moves= sum -N*minW;
	    cout <<moves << endl;
	}
	
	return 0;
}
18

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

1 Like
19

Consider test case:
3
0 2 2
The answer is 4 but your answer is 2 if I understand all properly.

3 Likes
20

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.

1 Like
21

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.

1 Like
22

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.

23

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.

24

hi… don’t bother. I got my mistake :slight_smile: