[problem:https://codeforces.me/gym/471619/problem/A]
Hints
Hint 1
Do we really need to create stack ?
Hint 2
What would the smallest element in the first stack ?
Hint 3
every stack can be reduced to any value we want, but how much can it be increased ?
Explanation
We can simple use a vector to store the sizes of stack, the minimum ascending order series we can form is 0,1,2,3,4....n We can keep a buffer for extra elements, that means set a[0] = 0 and add the remaining value to the buffer. a[i] -= i; and buffer += a[i] — i;
if at any point our buffer becomes negative that will mean that particular sequence till that point isn't possible, and since that is the minimal series that means it isn't possible to form a valid sequence for those set of stacks.
Solution
// Aur Bhai Dekhne aagaye ;)
// Author: Abhijit Mishra
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vi;
#define nl cout << "\n"
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
int main()
{
fast;
ll t = 1;
cin >> t;
while (t--) // each testcase
{
ll n;
cin >> n;
vi a(n);
for (int i = 0; i < n; i++) { cin >> a[i]; }
ll buffer = 0;
int i = 0;
while (i != n)
{
if (a[i] >= i)
{
buffer += a[i] - i;
}
else
{
ll x = i - a[i];
a[i] += x;
buffer -= x;
}
if (buffer < 0)
{
break;
}
i++;
}
cout << (i == n ? "YES" : "NO");
nl;
}
return 0;
}