Make all equal - codechef

Well, some problems can be real pain, and this problem was one of those, the fact that I took a bad approach on this problem is just making me angry cause I can't accept to have done such a stupid mistake, going the whole way wrong right from the start till the very end of the problem.

This is really unacceptable for me, I feel that if I would do such blunders in live competitions then I will be doomed, there's no way I can think of a fair rank with this condition. Trying to think of what went wrong and will make sure that next time I look at a problem, I just understand to its very depth.

Overall, the problem was based on tricking our minds to make us think like it is about implementing a complex solution, and yaaah I did implement one, although that was a mess and didn't even pass all the cases, was giving wrong answer. Congo to the stupid me... but the whole core of this problem was based on such such such simple fact that I can't just take my mind over it, how? how can I do this? ahh.

The concept:-

Taking a simple example like: [1,1,1,1,7], and 

m=4, so here we can increment all the 1's altogether to get to 7, just 6 operations needed.

m=2, here we have the limitation of incrementing just 2 elems altogether at once, so firstly we increment the first two 1's with 6 operations and then the next two 1's with other 6 operations, total 12 operations.

m=1, will be the worst case where will have to increment every number separately, so giving us a total of 24 operations.

what about m=3 right? wait for that.

from this observation if you were careful enough and assuming that you have great visualization skills, you would have understood that we are just grouping the spread 1's summing upto 24 and then grouping them in m groups, 24/4 gave 6, 24/2 gave 12 and 24/1 gave 1.

now... what if m=3?  yeah you guessed it correct it's 8 operations!

The only thing to consider here is that suppose we were summing upto 25 and m was 3 so we would have got a remainder of 1 for 25%3, in such cases we just add one more operation to the whole answer, child's play right.

CORNER CASE ALERT: what if m=8 and the total we gotta sum upto is just 6, take example:

arr = [1,7,7,7,7,7,7,7,7,7], here our logic would say that we just need 1 operation, but.... noooo that's 6 operations we are gonna require, so for that we just use the simple logic in the end, that is if the result of our previous logic is less than max(arr) - min(arr) then the answer will be max(arr) - min(arr). 

That's it.

Code Implementation:

for _ in range(int(input())):

    n,m=map(int,input().split())

    arr=list(map(int,input().split()))

    mx=max(arr)

    left=mx*n-sum(arr)

    print(max( (left//m)+(1 if(left%m!=0) else 0) ,mx-min(arr)) )