The first thought we should get here is that,↵
↵
We will try to find the number of moves if we want to explode from ith index,and then we will take the minimum for all i from 1 to n.↵
↵
Now, for each index i we have to calculate the number of moves required in O(1) or O(log(n)).↵
↵
My solution deals with this in O(1) so I will explain that,↵
↵
Ideally before exploding at index i, what we have to do is to make the array strictly decrease from index i to n (except for the fact that we will not decrease any element beyond 0) and strictly increase from index 1 to i (here also we will not decrease any element beyond 0) because this will be the case when the chain reaction will eat all the elements.↵
↵
Now, since elements to the left of index i and to the right of index i are independent now , we will check for them separately.↵
↵
Now let us try to find the number of moves required to make the array increasing from index 1 to i.↵
↵
To do this in O(1):↵
↵
We want to know 2 indexes say i1 and i2 :↵
↵
1. i1 will be the index from where we have to make all the elements equal to 0 all the way to 1st element.↵
so i1=max(1,i-a[i]).↵
↵
↵
2. now to explain what i2 will be↵
suppose a case: ↵
1 2 3 11 12 9 ↵
if we want to explode at the 6th element we will start decreasing the elements from the 5th index but look carefully ↵
we don't have to decrease elements beyond 4th element as they are already smaller, so the final array will look like↵
1 2 3 7 8 9↵
so in total, there will be a total (12-8)+(11-7)=8 moves required before exploding.↵
↵
So,i2 will tell the 1st index to the left of index i from which we don't have to further decrease elements to make the ↵
array increasing from index 1 to i.↵
↵
↵
We can find i2 using stack datastructure for each index i, How?↵
↵
Suppose we want to calculate i2 for i so,↵
↵
a[i]-(i-i2)<=a[i2] should hold,↵
↵
i.e ↵
↵
a[i]-i<=a[i2]-i2↵
↵
So, using stack we can find i2 for each index i from 1 to n in total of O(n)...(i.e. avg O(1) for each index i) by :↵
↵
(suppose S is our stack of integers containing the indexes of orignal array)↵
S.push(1);↵
for(i=2;i<=n;i++){↵
while(S.size() && a[S.top()]-S.top()>a[i]-i){↵
S.pop();↵
}↵
i2=0; // i2=0 means , there isn't any valid i2 from 1 to i-1.↵
if(S.size()) i2=S.top();↵
S.push(i);↵
}↵
↵
Now there will be 2 cases :↵
i1<i2 :↵
In this case, the Number of moves required to make the array strictly increase from index 1 to i will be↵
(number of moves to make the array strictly increasing from index 1 to i2) +↵
(number of moves to make the array strictly increasing from index i2+1 to i)↵
↵
we will be storing the number of moves required to make the array strictly increasing from index 1 to index i↵
so we will get (number of moves to make the array strictly increasing from index 1 to i2) in O(1).↵
Also,↵
To calculate (number of moves to make the array strictly increasing from index i2+1 to i) in O(1)↵
we will maintain a prefix sum array of a[j]-j say pre1 (the name of this prefix array).↵
So,↵
(number of moves to make the array strictly increasing from index i2+1 to i) =↵
(pre1[i-1]-pre1[i2])-(i-i2-1)*(a[i]-i).↵
↵
i1>i2 :↵
In this case, Number of moves required to make the array strictly increase from index 1 to i will be↵
(number of moves to make the array strictly increasing from index 1 to i1) +↵
(number of moves to make the array strictly increasing from index i1+1 to i)↵
↵
To calculate (number of moves to make the array strictly increasing from index 1 to i1)↵
we just want the sum of elements from index 1 to index i1↵
which we can easily get by keeping another prefix sum array of a[j]'s ↵
because we have to make all the elements equal to 0 from 1 to i1.↵
↵
Now,↵
Calculation of (number of moves to make the array strictly increase from index i1+1 to i) is already described in above ↵
case of i1<i2.↵
i.e↵
(pre1[i-1]-pre1[i1])-(i-i1-1)*(a[i]-i).↵
↵
So finally we have got the number of moves required to make the array increasing from index 1 to index i in O(1).↵
A Similar thing, we can do to find the number of moves required to make the array decreasing from index i to index n.↵
↵
Now we can just explode at ith index with power a[i] so in total we will have to expend↵
↵
a[i]+(number of moves required to make the array increase from index 1 to index i)+(number of moves required to make the array decrease from index i to index n).↵
↵
And hence in O(n) we can find the minimum :)↵
↵
solution -> https://mirror.codeforces.com/contest/1795/submission/193942204↵
↵
I hope this helps.
↵
We will try to find the number of moves if we want to explode from ith index,and then we will take the minimum for all i from 1 to n.↵
↵
Now, for each index i we have to calculate the number of moves required in O(1) or O(log(n)).↵
↵
My solution deals with this in O(1) so I will explain that,↵
↵
Ideally before exploding at index i, what we have to do is to make the array strictly decrease from index i to n (except for the fact that we will not decrease any element beyond 0) and strictly increase from index 1 to i (here also we will not decrease any element beyond 0) because this will be the case when the chain reaction will eat all the elements.↵
↵
Now, since elements to the left of index i and to the right of index i are independent now , we will check for them separately.↵
↵
Now let us try to find the number of moves required to make the array increasing from index 1 to i.↵
↵
To do this in O(1):↵
↵
We want to know 2 indexes say i1 and i2 :↵
↵
1. i1 will be the index from where we have to make all the elements equal to 0 all the way to 1st element.↵
so i1=max(1,i-a[i]).↵
↵
↵
2. now to explain what i2 will be↵
suppose a case: ↵
1 2 3 11 12 9 ↵
if we want to explode at the 6th element we will start decreasing the elements from the 5th index but look carefully ↵
we don't have to decrease elements beyond 4th element as they are already smaller, so the final array will look like↵
1 2 3 7 8 9↵
so in total, there will be a total (12-8)+(11-7)=8 moves required before exploding.↵
↵
So,i2 will tell the 1st index to the left of index i from which we don't have to further decrease elements to make the ↵
array increasing from index 1 to i.↵
↵
↵
We can find i2 using stack datastructure for each index i, How?↵
↵
Suppose we want to calculate i2 for i so,↵
↵
a[i]-(i-i2)<=a[i2] should hold,↵
↵
i.e ↵
↵
a[i]-i<=a[i2]-i2↵
↵
So, using stack we can find i2 for each index i from 1 to n in total of O(n)...(i.e. avg O(1) for each index i) by :↵
↵
(suppose S is our stack of integers containing the indexes of orignal array)↵
S.push(1);↵
for(i=2;i<=n;i++){↵
while(S.size() && a[S.top()]-S.top()>a[i]-i){↵
S.pop();↵
}↵
i2=0; // i2=0 means , there isn't any valid i2 from 1 to i-1.↵
if(S.size()) i2=S.top();↵
S.push(i);↵
}↵
↵
Now there will be 2 cases :↵
i1<i2 :↵
In this case, the Number of moves required to make the array strictly increase from index 1 to i will be↵
(number of moves to make the array strictly increasing from index 1 to i2) +↵
(number of moves to make the array strictly increasing from index i2+1 to i)↵
↵
we will be storing the number of moves required to make the array strictly increasing from index 1 to index i↵
so we will get (number of moves to make the array strictly increasing from index 1 to i2) in O(1).↵
Also,↵
To calculate (number of moves to make the array strictly increasing from index i2+1 to i) in O(1)↵
we will maintain a prefix sum array of a[j]-j say pre1 (the name of this prefix array).↵
So,↵
(number of moves to make the array strictly increasing from index i2+1 to i) =↵
(pre1[i-1]-pre1[i2])-(i-i2-1)*(a[i]-i).↵
↵
i1>i2 :↵
In this case, Number of moves required to make the array strictly increase from index 1 to i will be↵
(number of moves to make the array strictly increasing from index 1 to i1) +↵
(number of moves to make the array strictly increasing from index i1+1 to i)↵
↵
To calculate (number of moves to make the array strictly increasing from index 1 to i1)↵
we just want the sum of elements from index 1 to index i1↵
which we can easily get by keeping another prefix sum array of a[j]'s ↵
because we have to make all the elements equal to 0 from 1 to i1.↵
↵
Now,↵
Calculation of (number of moves to make the array strictly increase from index i1+1 to i) is already described in above ↵
case of i1<i2.↵
i.e↵
(pre1[i-1]-pre1[i1])-(i-i1-1)*(a[i]-i).↵
↵
So finally we have got the number of moves required to make the array increasing from index 1 to index i in O(1).↵
A Similar thing, we can do to find the number of moves required to make the array decreasing from index i to index n.↵
↵
Now we can just explode at ith index with power a[i] so in total we will have to expend↵
↵
a[i]+(number of moves required to make the array increase from index 1 to index i)+(number of moves required to make the array decrease from index i to index n).↵
↵
And hence in O(n) we can find the minimum :)↵
↵
solution -> https://mirror.codeforces.com/contest/1795/submission/193942204↵
↵
I hope this helps.
