While solving the codechef problem WALK I figured out an algorithm to solve the problem using divide and conquer kind of approach , according to my algorithm we find the maximum in the array and divide our array into 2 parts (one from starting to the Max element and the other half from the next to Max element to the end of the array) and after that we find the initial velocity for first part(the part contesting the Max elemeny) of the array using : Max +(n-1) where n is the number of elements in that part of the array .... We do this thing for every part of the array and after computing the initial velocity for every part we check if the initial velocity of a part of array is less than or equal to the Max + 1 where Max is the maximum element of the part of the array just before the part under consideration , if this is the case we do nothing else we find out the difference between Max + 1 and initial velocity and add that difference to the initial velocity of the part previous to the part under consideration and we keep repeating this process until no more changes are required. Now this algorithm will work surely but it will exceed the time limit .. When I saw the editorial it has one line solution of this problem .. Can someone please explain that solution to me I couldn't understand it . Thanks in advance.
Let initial velocity be V. When they are at the first(0-based indexing) shop, their velocity is still V, also, V >= W1. When they cross it and go to the second shop, the velocity becomes V-1. and we know that V-1 >= W2. Similarly When they cross it and go to the third shop, the velocity becomes V-2. and we know that V-2 >= W3. Continuing this way, we see that this relation holds: V-i >= Wi for all i in [0,n-1]
V0 >= W0 + 0
V1 >= W1 + 1
V2 >= W2 + 2
V3 >= W3 + 3 ...
Therefore, Vi >= Wi + i for all i.
Choose the V as which is maximum among all Wi+i