RECNDROT - Editorial

editorial
, , , , , ,
43

I think I implemented a similar approach but I am getting TLE.
https://www.codechef.com/viewsolution/32354950

45

how it is O(N Log n) soltion ???

46

@tor_baap @tmwilliamlin @rishup_nitdgp

here is my code to this problem

Blockquote
#include<bits/stdc++.h>
using namespace std;
int main()
{
string s,v;

char temp;
int t;
cin>>t;
while(tā€“)
{
cin>>s;
v=s;
int n=s.length();
temp=v[0];
for(int i=0;i<=n-1;i++)
{
v[i]=v[i+1];

}
v[n-1]=temp;
temp=s[n-1];
for(int i=n-1;i>0;iā€“)
{

s[i]=s[i-1];

}
s[0]=temp;
if(s==v&&s.length()==v.length())
cout<<ā€œYESā€<<endl;
else
cout<<ā€œNOā€<<endl;

}

}

but the it is giving error the only bug in this code is

s[0]=temp;
is written inside for loop but how will it effect the code as temp value is constant and it is finally assigned to s[0] at last execution of loop

plz help

47

hey this is my solution , I calculated LIS of current arr and then removed all the element occured in the curr LIS from the arr . then again i performed LIS on the updated arr and remove the elements i got from the LIS . I did these steps until the size of arr is not zero .
my complexity is MNlog(N)
https://www.codechef.com/viewsolution/32368004
please help i am not able to found the error in my solution

48

Can someone tell me the problem with my code.

If you canā€™t understand my code it basically does these:

My solution: CodeChef: Practical coding for everyone

  1. cur_pos = 0, ans = 1
  2. Does the next element have a position which is greater than cur_pos
  3. If yes, cur_pos = idx
  4. Else answer increases and cur_pos = the first occurrence of the element
  5. Print the answer
49

Your logic seems correctā€¦issue must be with implementation.
Your Binary Search is incorrectā€¦I just replaced it with linear search.
link to correct submission-
https://www.codechef.com/viewsolution/32387752
I leave the work to correct BS to you.

50

Setterā€™s Solution code is very beautiful. I have used a lot of pointers and written a very length, shabby code to find lower bound, you have implemented it very beautifully in just 5-6 lines and still made it very reader friendly with the right variable names

51

Hereā€™s a test case where your code goes wrong :

5
6 8 5 6 10

52

Hereā€™s a test case where your code goes wrong:
5
7 6 9 1 6

54 
def search(l,pos1,pos2,a):
    for i in range(pos1,pos2+1):
        if l[i]==a:
            return i
    return -1

t=int(input())
for i in range(0,t):
    n=int(input())
    l=list(map(int,input().split()))
    f1=set(l)
    #set identifies distinct elements and store in a sorted way
    f=[]
    for k in f1:
        f.append(k)
        
    for i in range(0,n):
        if l[i]==f[0]:
            curr=i
            break
   
    x=1
    m=1
    while(x<len(f)):
        temp=search(l,curr+1,n-1,f[x])
        if temp==-1:
            m=m+1
            temp=search(l,0,curr-1,f[x])
            curr=temp
            x=x+1
        else:
            curr=temp
            x=x+1
        
    print(m)

kindly tell my mistake in this, or any TC that will give a WA.
I have exhausted my TCs and also most of the TCs present in the above replies, got right answers in of all them.
this is my solution link( if you may need it):CodeChef: Practical coding for everyone
Thanks in advance

56

I corrected your code but after correcting I got a TLE
This is the code:

#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
ll t;
cin >> t;
while(tā€“)
{

  ll n;
  cin >> n;
  ll a[n];
  set<ll>s;
  vector<ll>v;
  map< ll, vector<ll> >m;
  for(ll i=0;i<n;i++)
  { 
    cin >> a[i];
    s.insert(a[i]);
    m[a[i]].push_back(i);
  }
  for(auto i:s)
  { 
     v.push_back(i);
  }
  
  n = v.size();   
  
  ll c = 1;
  
  
  ll var = -1;
  
  for(ll i=0;i<n-1;i++)
  { 
    	    vector<ll>v1 = m[v[i]];
    	    vector<ll>v2 = m[v[i+1]];
    	    
    	    ll y = v2.size();
    	    ll alpha = -1;
    	    if(  var == -1){
        	        vector<ll>::iterator low;
        	        low = lower_bound(v2.begin(),v2.end(),v1[0]);
        	        if( low != v2.end() ) {
        	            alpha = *low;
        	        }
        	        if(alpha>=0){    //element found
        	            var = alpha;
        	            continue;
        	        }
        	        else{            // element not found
        	            c = c + 1;
        	            var = v2[0];
        	            continue;
        	        }
    	    }
    	    else{
        	        vector<ll>::iterator low;
        	        low = lower_bound(v2.begin(),v2.end(), var);
        	        if( low != v2.end() ) {
        	            alpha = *low;
        	        }
        	        if(alpha>=0){    //element found
        	            var = alpha;
        	            continue;
        	        }
        	        else{     // element not found
        	            c = c + 1;
        	            var = v2[0];
        	            continue;
        	        }
    	    }
  }
    cout << c << endl;
}
return 0;

}

58

For Sorting the array (N Log N) .
Inside for loop , LogN time is for finding upper_bound of the prev_index.
Effectively it is N log N.

59

Hey I corrected your code Here is the correct solution

#include <bits/stdc++.h>
typedef long long int ll;
using namespace std;

int main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t;
cin >> t;
while(tā€“)
{
ll n;
cin >> n;
ll a[n];
sets;
map< ll, vector >m;
for(ll i=0;i<n;i++)
{
cin >> a[i];
s.insert(a[i]);
m[a[i]].push_back(i);
}
n = s.size();
ll c = 1;
ll var = -1;
for(auto i : s)
{
vectorv = m[i];
vector::iterator low;
low = lower_bound(v.begin(),v.end(),var);
if(low != v.end())
{
var = *low;
}
else
{
c = c + 1;
var = v[0];
}
}
cout << c << endl;
}
return 0;
}

60

Here is a test case where it will fail :

1
6
6 2 1 2 3 4

61

can someone pls help

62

can anybody tell why i am getting WA ,nearly i tried all test cases even then i am getting WA please help.
code link :
https://www.codechef.com/viewsolution/32463793