Codechef Starters 24 Special String

Revision en1, by SagarPrasad, 2022-02-03 11:36:47

Question

The above is the link to the problem. I have written a solution using upper_bound function which is getting TLE for 2 out of 13 test cases and barely passing one 1 testcase. Any help in either reducing time in my code or telling the solution will not be accepted with this method will be appreciated. Thank you.(I have put comments in my code to help in understanding.)

#include<bits/stdc++.h>
#include <iostream>
using namespace std;



void solve(){
  int n,m;
  string s;
  cin>>n>>s>>m;

  //Values is like a 2d vector which stores all the occurences of a in val[0], that of b in val[1],etc
  //I also put a value n at the end of all the alphabets to mark a end point.
  //indexes a zero based index
   vector<vector<int>> values(26);
  for(int i=0;i<n;i++){
      values[s[i]-'a'].push_back(i);
  }
  for(int i=0;i<26;i++){
      values[i].push_back(n);
  }
  //In the above two loop i have filled values vector with all the indexes of all the alphabets
  //Note : All the occurences are sorted and there is a end point n present in all the vectors
  //containing the occurencesof each element.


  //I am initially setting my solution as INT_MAX so if i have a solution lower then this by the end
  //of the program i will print that solution(lowest answer) else i will print -1.
  int sol=INT_MAX;

  //We always have to start our subsequences with the letter a so i have decided that i will create
  //a loop with in which i try to find all the answers which start with each occurences of a.
  for(int i=0;i<values[0].size()-1;i++){
      //The temp variable is just to there to check the size of the subsequence will be m.
      int temp=m-1;

      //K is used to identify the position of the alphabet i will be finding next (k%26).
      //K is one since we already have a.
      int k=1;

      //Start is the position of the alphabet a from which we are going to find our answer/subsequence.
      int start=values[0][i];
      //If there are not enough element in the string to find a answer we get out of loop.
      if(start+m-1>=n)
          break;
      //In the beginning we name end=start as the subsequence we have found till now is only till position start
      int end=start;

      //In this loop we will find all m element of the subsequence
      while(temp!=0){
          //D is the alphabet to find.
          int d=k%26;
          //it iterator gives us the alphabet we need to find and we put the position of this alphabet in
          //end.Note we find upper_bound to end as end was the position of our last element
          auto it=upper_bound(values[d].begin(),values[d].end(),end);
          end=values[d][it-values[d].begin()];

          //If end==n we won't able  to complete thi subsequence or any new subsequence so we
          //can finish the program here.
          if(end==n){
              if(sol==INT_MAX){
                  cout<<-1<<"\n";
                  return;
              }
              //SInce we need to print the total numbers to deleted it is sol-m
              cout<<sol-m<<"\n";
              return;
          }
          //If before finding all the element,we find that the current to be solution is
          //greater then actual solution, we can skip this partcular subsequence.
          if(end-start+1>=sol){
              break;
          }
          temp--;
          k++;
      }
      //if end<n i.e there is a soolution
      if(end!=n)
      sol=min(sol,end-start+1);
      //No other soolution is smaller then this so we can end.
      if(sol==m)
          break;
  }
  //This is discussed above.
  if(sol==INT_MAX){
      cout<<-1<<"\n";
      return;
  }
  cout<<sol-m<<"\n";
}
int main(){

#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t=1;
    cin>>t;
    while(t--) {
        solve();
    }
    return 0;
}

Tags codechef, upper_bound

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English SagarPrasad 2022-02-03 11:39:45 12
en2 English SagarPrasad 2022-02-03 11:38:58 1542
en1 English SagarPrasad 2022-02-03 11:36:47 4207 Initial revision (published)