CF #637-C

C: Nastya and Strange Generators

Problem Statement: here

Solution-

If you figure out the problem statement, it is asking just one thing for you to implement. 

So, few observations are:

1. If my 1 is not on the extreme right, but rather at any arbitrary index i, then for all index up to n-1, all consecutive numbers will line up sequentially. 1 2 3 4 5 6 .....up to the time when index does not become the last index. You can easily figure it out yourself, the reason you will notice is that because the rj value for the immediate next empty cell is always greater than all cells ahead of it. 
2. If my 1 is on the extreme right side, then recursively apply the above algorithm for next value that is just the immediate next value after the one present at the n-1 position, but this time the last value of index up to which we will check if they are sequential will be just before index of 1. Because for indexes ahead of 1, we have already verified out. Similarly, we do this until we reach n.
3. For example the pattern : 4 5 6 1 2 3, this is a valid pattern and for this we first start from index 1 and go up to n-1 position. since all elements are sequential, we look for index of 4, because last element we fixed was 3. Now, this time we look from index of 4 up to index of 1, since all elements are sequential, we return yes. 
4. For example, the pattern : 5 6 4 1 2 3 is also a valid pattern, because here from 1 to 3, everything is sequential, from 4 up to 1 everything is sequential, from 5 up to 4, everything is sequential.

Code:

void solve() { int n; cin>>n; int a[n],ind[n+1]; rep(i,0,n){ cin >> a[i]; ind[a[i]]=i; } ll ct = 1; rep(i,ind[1],n){ if (a[i] != ct){ cout << "No" << endl; return; } else{ ct++; } } if (ct >= n){ cout << "Yes" << endl; return; } ll newfar,farind; farind = ind[1]; while(ct != n+1){ newfar = ct; rep(i,ind[ct],farind){ if (ct == n+1){ cout << "Yes" << endl; return; } else if (a[i] != ct){ cout << "No" << endl; return; } else{ ct++; } } farind = ind[newfar]; } cout << "Yes" << endl; }