Problem Link-https://www.codechef.com/problems/RNUM
Im unable to understand this piece of code except sorting-https://www.codechef.com/viewsolution/13608311
This piece of code finds and processes fragments (in sorted array) where each number=previous number+1.
K is a length of current fragment. If first condition if((a[i]+1)==a[i+1]) is true, then a[i+1] belongs to current fragment and we increment K, else the fragment ended and we need to process it.
Minimum number of turns for fragment is achieved with this strategy - partition fragments into segments of length 3 and shoot into center of each segment (killing three numbers with one shot), that is k/3 shots. You also need one extra shot if you have some numbers remaining (k%3!=0).
Maximum number of shots achieved this way - always shot in the first living number in the fragment, thus killing only two numbers with each of (k/2) shots. You may need one extra shot if you have one number remaining after k/2 shots if(k%2!=0).
It is easy to see that shots in one fragment cannot kill numbers in other fragments (since the difference between any two numbers in different fragments is at least 2, else it would be one fragment, not two), thus you can derive min and max for whole array by summing min and max for every fragment.
1 Like
why k=1 at last in else condition? reason?
nice explanation
because all are distinct? thats why? why not error for index out of bound access?
k=1 means that we processed current fragment and need to start finding next fragment.
Array a is 100005 length, so there will not be out-of bounds errors, although there can be some false data on (a[n-1]+1==a[n]) comparison, I suppose, so it would be prudent to initialize a[n] with something that cannot be in array.
1 Like