Progressively Larger Rings
We have N circular rings from 0 to N-1. The area of the i-th ring is area[i]. Now we want to have progressively larger rings from the first ring to the last ring, so that each ring is bounded by the next ring. To make things simpler, let us assume that the i+1-th ring bounds the i-th ring if the area of (i+1)-th ring is atleast 1 unit more than the area of the i-th ring. So basically we want an array of progressively larger rings, such that the area of (i+1)-th ring is greater than or equal to (1 + area of i-th ring), for 0<=i<=N-2. You are given an array of area of rings. The areas may be in any order. To bring them to strictly ascending, you can increase or decrease the area of each circle by atmost C units. You cannot decrease the area of a circle to less than 1. All areas are initially given as integers and you can change them by intergral amounts only, i.e. after the change , the new area of each circle must be an integer. Also the change operation is expensive, a change of C has a cost proportional to C. Return the smallest possible non-negative integer C such that we can achieve our goal by allowing change of atmost C for every ring.
1st line: An Integer T denoting the number of test cases.
Each test Case Contains: a number N on the first line (N is the number of rings). This is followed by N integers where the i-th integer is area of the i-th circle.
Output a single line containing the value of C for this test case.
1 1 1 1 1
In the first test case the areas are already progressively larger, so no change is required.
In the second test case, we can allow a change of atmost 4, thereby converting the areas into 1,2,3,4,5. The first one is kept unchanged, the rest are increaded by 1,2,3 and 4 units respectively (thus every change<=4 and area of any circle doesnot fall below 1)
Each area lies between 1 and 1,000,000,000 (both inclusive).
Problem Setter : Souptik Sen