PROBLEM LINK:
Author: Prateek Gupta
Editorialist: Chandan Boruah
DIFFICULTY:
SIMPLE
PREREQUISITES:
Brute Force, Maths.
PROBLEM:
Given a 2D array, print the minimum number of steps you need to take to reach the rightmost index. Each index has a value which is the maximum number of steps that can be taken, and that value can be negative. Print -1, if it is impossible to reach the rightmost index.
QUICK EXPLANATION:
For each index, find the number of steps to which it can reach to. Maintain that value in a variable. If in any position, that value is less than the current position then we cannot reach and also towards the right of that position. Print -1, in that case.
To find the minimum number of steps required, we can do the following.
For each index, add to the variable the index to which it can reach to. Keeping the maximum in each case. Whenever we find that the next index to reach requires the current index’s value too, then we add the required return output.
NOTE:
The solution has few bugs, especially the steps required calculation part.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define pf push_front
#define lli long long int
#define ll long long
#define inf 1000000000000000000
#define mp make_pair
#define vc vector
#define pq priority_queue
#define pll pair<ll,ll>
#define pls pair<ll,string>
#define psl pair<string,ll>
#define plc pair<ll,char>
#define pcl pair<char,ll>
#define pss pair<string,string>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FOR1(i,a,b) for(int i = a; i<=b; i++)
#define T ll t=0;cin>>t; while(t--)
using namespace std;
ifstream in("input.txt");
ofstream out("output.txt");
vector <int> v[500001];
vector <vector<int>> v2(101),g2(101);
vector < pair<int,int>>vi[100001];
// vi[x].push_back(make_pair(y,c));
set<int>st;
//st.insert(1);
// int top=*st.begin();
//st.erase(top);
int ph[2000001]={0};
/*for (int k = 1; k < K; ++k)
for (int i = num - K + k; i >= k; i--)
for (int j = k - 1; j < i; j++)
dp[i] = max(dp[i], dp[j] + (sum[i] - sum[j]) / (i - j));
*/
//dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i-1][j-1];
//dp[row2+1][col2+1]-dp[row2+1][col1]-dp[row1][col2+1]+dp[row1][col1];
int main()
{
fast
int n;
cin>>n;
ll a[n];
for(int i=0;i<n;i++)
cin>>a[i];
ll ma=0;int f=1;
for(int i=0;i<n;i++)
{
if(ma<i)
f=0;
ma=max(ma,a[i]+i);
}
if(f==0)
cout<<"-1";
else
{
ll s=0,ans=0;ma=0;
for(int i=0;i<n;i++)
{
if(s<i)
{
s=ma;
ma=i;
ans++;
}
ma=max(i+a[i],ma);
}
cout<<ans<<endl;
}
return 0;
}