In this question when I read the editorial, it was quite simple. But I don’t understand how did he come to this conclusion. Please explain. And what should I do, when I am not able to pick up this kind of thing in a contest? I mean if I am not understanding how he reached the conclusion, I would have never got to that conclusion myself quickly in a contest. What should I do then?
You don’t worry if u don’t get such logic rn(right now)… Cuz it will come with experience… All you have to do in contest is take some examples and just find the answer and that’s it… it will automatically strike u after some experience…
I will share my thinking process…
I would have taken some examples and tried to make all of them equal… then I would have realized that maybe I can make at least n-1 of them equal (by taking some examples)… after that I ll take some corner cases to verify that I get at least n-1 of them equal or not
Brute force cases in my mind :-
Click to view
1)all elements equal
2)all in increasing order
3) random
all of above with size of 4-5
4) size 1
5)size 2
6) size 3
Now by observation I will be sure that it is n-1 or n
Now I ll think that when can I make it “n”
I ll look what is similar in some examples I remember in which I can get n as answer…
Further I ll think that isn’t it dividing a value in n equal parts ? Cuz adding +1 and subtracting 1 from other won’t change the sum right… and u need max of them to be equal… so either sum is divisible by n or not… so ans is n-1 or n…
This is the worst case thinking process from which I can get an answer…
In best case I could have realized earlier that +1 -1 is nothing but dividing their sum in n parts as I need them to be… so that’s what experience gives…
And even this worst case thought process won’t take more than 15-20 mins…
1 Like
and
It becomes more obvious from constraints about it is O(n) soln or O(Nlogn) or O(logn) or O(sqrtn) or O(n^2) or O(n^3)
So for example it looks O(n) then it is pretty obvious that soln would be of type I thought or hashing… if it’s O(logn) then first thing I ll think of is tree (probably segment , fenwick etc)
If Nlogn then I ll think for sorting them…
Sqrtn means sqrt decomposition…
So in this way I get a direction to think…