CP07 Editorial

editorial
, ,
1

Problem link

Click here

Difficulty level

Hard

Solution

We will use binary search to solve this problem. We know that the answer lies between 1 and n, so they will be our lower and upper limit for the binary search respectively.

Let’s say we want to know if it is possible to construct the given sequence using only a mid number of distinct characters.

We may face 3 different cases-

  1. When arr_i > arr_{i-1}
  2. When arr_i = arr_{i-1}
  3. When arr_i < arr_{i-1}

The first case is easy to handle, it is always optimal to extend s_{i-1} to the length of s_i by adding 0s in the end of s_{i-1}. For the second case, we can just keep s_i = s_{i-1}.
For the third case, we find the rightmost character among the first arr_i characters of s_{i-1} which is not equal to mid, let’s say at j^{th} index, then it is always optimal to have the first j-1 characters of s_i and s_{i-1} same, the jth character of s_i one place higher than that of s_{i-1} and the remaining characters as 0s.
To implement this, we just need to be aware of the character that we have used at each index for the just preceding string, which can be done using a data structure like stack. Note that at most of the indices we will be placing 0 only, so to ensure that the size of our stack doesn’t blow up the memory we will store information corresponding to only those indices which have the character something greater than 0.

Code

#include<bits/stdc++.h>
using namespace std;
bool check(vector<int>&arr, int n,int mid)
{
    vector<pair<int,int> >store;
    for(int i=1; i<n; i++){
        int len=arr[i];
        if(len>=arr[i-1])
         continue;
        if(mid==1)
         return false;
        while(!store.empty() && store.back().first>len){
            store.pop_back();
        }
        while(true){
            if(store.empty() || store.back().first<len){
                store.push_back({len,1});
                break;
            }
            if(store.back().second+1<mid){
                auto var=store.back();
                store.pop_back();
                store.push_back({len,var.second+1});
                break;
            }
            store.pop_back();
            len--;
            if(len<=0)
             return false;
        }
    }
    return true;
}
int main()
{
    int T;
    cin>>T;
    while(T--){
    int n;
    cin>>n;
    vector<int>arr(n);
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    int start=1;
    int end=n;
    int ans=end;
    while(start<=end){
        int mid=(start+end)/2;
        if(check(arr,n,mid)){
            ans=mid;
            end=mid-1;
        }
        else
         start=mid+1;
    }
    cout<<ans<<"\n";
    }
    return 0;
}