SALARY - Editorial

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

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.

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.

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

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

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.

1 Like

yup…thnx a lot.

yup!
thank you :slight_smile:

this one is a lot simple and better explanation than the above

Read both my answers there- https://discuss.codechef.com/questions/91459/explaniation-for-the-salary-editorial?page=1#91462

How should I convince myself that this problem will always have a solution ? Can someone give an induction proof on why there always exists a solution for this problem ?
Second, How can you get the final salaries of all the workers?

No Problem. I figured it out - https://mission-apollo.blogspot.com/2019/04/the-minimum-number-of-moves.html

For those who still cannot understand the problem. Here final salaries of employees are not important. We are only concerned with number of steps.

  1. What is given in question?

Increase N-1 Workers salaries. And keep 1 worker’s salary as it is.

  1. Instead of given statement, what can we think of?

Here salaries are relative to each other. So we can also think the question in different. What if we decrease one worker’s salary by 1? It will be alright.

Let us take some examples:

Method 1
(As per given in question) :
Input:
3
1 3 6
step1 : 2 4 6
step2 : 3 5 6
step3 : 4 6 6
step4 : 5 7 6
step5 : 6 7 7
step6 : 7 7 8
step7 : 8 8 8

So answer is 7 steps.

Method 2
(Considering relative salaries and decreasing 1 worker’s salary each time whose salary is greater than minimum salary present in all workers)

Input:
3
1 3 6 (minimum is 1)
step1 : 1 2 6
step2 : 1 1 6
step3 : 1 1 5
step4 : 1 1 4
step5 : 1 1 3
step6 : 1 1 2
step7 : 1 1 1

You can refer my C++ solution here : Link

Hope it helps! :smile:

3 Likes

Finally, the explanation i was looking for. Thanks a lot for this.

Glad to head that :smile:

whats wrong with my code here!!
import java.util.;
import java.lang.
;
import java.io.*;

class cd9
{
public static void main(String args[])throws IOException
{

	  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      
      int i;
	  
	  int N = Integer.parseInt(br.readLine());
	
	  Stack<Integer>[] list = (Stack<Integer>[]) new Stack()[N];;		
	  
      String input = br.readLine();

	  String[] strs = input.trim().split("\\s+");

	  int values[]  = new int[strs.length];

	  for (i = 0;i< strs.length; i++) 
	  {
	  values[i] = Integer.parseInt(strs[i]);
	  
	  list[i].push(values[i]);
	  
	  }
	  
	  int count = 0;
	  
	  int flag=0;

      int max = Integer.MIN_VALUE;	
	  
	  int index_max = 0;
	  
	  while(flag==0)
	  {
		 for(i=0;i<N;i++) 
		 {
			if(list[i].peek()>max){
									
				index_max = i;
				
			}
		 }  
		    flag=check(list);
			
			if(flag==1){
				
				break;
				
			}
		  
		 addOne(list,index_max);
		  
		  count++;
	  }
	  
	  
	  System.out.println(count);

}

static int check(Stack<Integer>[] list){
	
int n  = list.length;

int i;

int flag=0;

int temp = list[0].peek();

for(i=1;i<n;i++)
{
	if(temp!=list[i].peek())
	{
		return 0;
		
	}

}	

return 1; 	
	
}


static void addOne(Stack<Integer>[] list,int index)
{
	int i;
	
	int x;
	
	for(i=0;i<list.length;i++)
	{
		if(i!=index){
			
			 x = list[i].peek();
			
			 list[i].push(x+1);
			
		}else{
		
		  list[i].push(list[index].peek());
			
		}
		
	}
		
	
}

}

Since we need the minimum number of operations shouldn’t it be
max(a)-min(a)+1
for example: if we have 5 workers with w[]={ 12 , 13 , 14 , 15, 18 }
the above logic will take 7 moves and this way will increase the salary of every worker by one i.e. in the end w[]={ 19,19,19,19,19 }.
But according to tester’s code, the answer is 12. Can someone please help me out.

You have to increase salary of N-1 workers at a time, after 7cases, there is no way everyone gets 19.
Read problem again.

Bro the only error i see is u should initialise sum inside for loop.

I dont get solution still ,i read all comments and both solution but derivation of formula is still not upto mark explain!! plz explain more!!