can any one please explain this editorial for salary problem.
The Q was quite cunning, I will remark.
First, you must understand this part of Q-
Q says that salaries of all but 1 worker increased by 1 in an operation. We will now prove that its equivalent to “reducing salary of a worker by 1”
THINGS YOU MUST UNDERSTAND-
1. Since its equalizing salary, things are RELATIVE
2. We are looking for NUMBER of operations required to equalize salary, and are NOT concerned with final salaries and stuff. So we NEED NOT follow exactly operation stated by Q ( increasing salaries of all but one worker by 1) and we can twist the statement into another equivalent form (i.e. reducing salary of 1 worker by 1) due to relative nature.
I think my point 2 needs better understanding.
Take this example-
There are two boys, one with 5 marbles and another with 9 marbles. We want to equalize the number of marbles. Now, we can “only add 1 marble to one of the boys collection”. So, number of operations would be-
Final state-
5+1+1+1+1=9
No. of operations = 4.
But look at Q closely, we are NOT asked anything about final state, but simply number of operations. Now, what the operation is actually doing? It is increasing marbles of boy with less marbles as to reduce the difference to 0
Any other way to reduce the difference? YES! What if instead of increasing marbles of first boy by 1, we reduce the marbles of other boy by 1? See for yourself, it has SAME impact of difference!!
Consider reducing marble of other boy by 1.
Final state-
9-1-1-1-1=5
Operations =4
The final state is difference, but due to relative nature, the number of operations are same.
This is the key to solve this Q.
What the author transformed the statement into, is that, instead of increasing salary of all but 1 worker by 1, what if we reduce the salary of that worker by 1.
Look at relative scale!
The difference between salary of other workers and that worker reduces in same pattern, whether we “increase salary of all but one worker by 1” or “reduce salary of that worker by 1”
Since this is the pivot point of this Q, let me illustrate it via example-
Consider salaries as-
1,2,3,4
Increasing salary by one-
2,3,4,4
Look closely! The difference b/w salary of that worker and other workers has reduced by 1 each! Diff b/w 1st and 4th worker, earlier 3, is now 2. And so on… Is it not equivalent to reducing that worker’s salary by 1?
Decreasing salary by 1-
1,2,3,3
Look! The difference remains the same!! Diff. b/w first and last is still 2…and so on.
Now, if you understood what I said earlier regarding number of operations, you will get this very important statement-
If 2 operations reduce difference in a exactly same fashion, the number of operations in them are ALSO exactly same
Illustration 4-
Now, increasing salaries of ALL BUT ONE worker by 1- (the “…X” denotes number of operation)
2,3,4,4.....1
3,4,4,5.....2
4,5,5,5.....3
5,6,6,5.....4
6,7,6,6.....5
7,7,7,7.....6
Now case of reducing salary of 1 worker by 1-
1,2,3,4-
1,2,3,3.....1
1,2,3,2.....2
1,2,3,1.....3
1,2,2,1.....4
1,1,2,1.....5
1,1,1,1.....6
Now, assuming that you understood the reason equivalence of the two methods in finding number of operations, let me tell you what the author did-
Closely notice in our method of reducing difference by one, the number of operation done on ith worker.
For last worker with salary 4, we did 4-1-1-1 ==>3 operations
For worker with salary 3, we did 3-1-1===>2 operations
For worker with salary 2, we did 2-1===>1 operation.
Observing this, you’d arrive to this result of mine-
The number of operations done on i'th worker is equal to Salary_of_i'th_worker - Minimum_Salary. And on adding the number of operations done on all workers, we get the total number of operations done.
Meaning, number of operation of i’th worker = Salary[I]-Min_Salary_in_array.
Adding this for all workers, from 1 to N-
(Salary[1st worker]-Min_Salary) + (Salary[2nd worker] - Min salary)…+(Salary[n worker]-min salary)
Write it on paper and check, you will find it is equal to-
Sum of salary of all worker - (Min salary +min salary+ …upto n times)
=Sum of salary of all worker - N*Min_Salary
And that is the solution given by editorial.
I hope this answer made the concept clear to you!! If not, feel free to comment 
1 Like
@vijju123
Yeah, I understand but can you please elaborate more on equivalence of both operation I am still not feeling I have understood it good enough.
What part are you getting stuck on equivalence?
Firstly, be in view that this “equivalence” holds good because of relative nature.
What i mean by equivalence is that, both the operations are having same effect on difference and hence on number of operation.
Please see, both operations are NOT equivalent in sense that they will have same result/final state. Meaning both operations wont result in same final array, as obvious in my cited example (1st method==>6,6,6,6 2nd ===>1,1,1,1)
What i mean by equivalence is that they both affect difference in exactly same way, and since number of operation depends on difference, they affect number of operation in same way.
So, giving clarification on how they are equivalent with respect to difference-
Sample case-
1,2,3,4
1st method, i.e. Increasing-
2,3,4,4
Diff b/w salaries-
4th & 1st ==2
4th n 2nd==> 1
4th and 3rd==>0
2nd Method, i.e. Decreasing-
1,2,3,3
Diff b/w salaries-
4th & 1st ==>2
4th & 2nd==>1
4th n 3rd ==>0
See, the difference being affected in same way is true. You can prove it by methods like Mathematical Induction that this is true for all cases.
The question used this fact (that the difference is being affected in exactly same way) to make implementation easier.
So, yeah, get back to me with what is not clear in this and i will try to my level best to give further clarification.
1 Like
@vijju123
Very nice explanation now everything seems clear to me and I wish you would have been the editorial of this problem.
Thank you! very much.
People this days don’t explain in that detail on forum. It would be great if you could share your email, for future help.
You wont need my email dear, I think I will be staying on this forum for some time XD.
BTW, m glad that things became clear to you in the end
1 Like
Thanks @vijju123 for taking time to type this much out and helping others understanding solution in a clear way
<33333333
Thanks!!
I found it a genuine question then, and fortunately had enough time to elaborately answer
1 Like
Thanks brother, A whole hearted thanks !!