RMNTREV - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: S.Manuj Nanthan
Tester: Nishank Suresh
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

Observation

PROBLEM

Alice initially has a string S of length N, and she decides to modify it! Her modification consists of K steps numbered from 1 to K. In the i-th step, Alice reverses the prefix of length i of S.

For example, suppose Alice starts with S = \texttt{abferty}, and she modifies it via 3 steps, then:

  • After the first step, \textcolor{blue}{\texttt{a}}\texttt{bferty} \rightarrow S = \texttt{abferty}
  • After the second step, \textcolor{blue}{\texttt{ab}}\texttt{ferty} \rightarrow S = \texttt{baferty}
  • After the third step, \textcolor{blue}{\texttt{baf}}\texttt{erty} \rightarrow S = \texttt{faberty}
    So after 3 steps, her string becomes S = \texttt{faberty}.

After performing her K-step modification, Alice ends up with the string S'. Now she challenges you to find the original string S. Can you do it?

QUICK EXPLANATION

  • All characters after k-th character are unaffected, so those can be appended to the answer at the end.
  • The net effect of all K operations forms a pattern like 53124 for 5 operations, so it is easy to recover the original string from the given string.

EXPLANATION

The first thing we can observe is that the i-th operation reverses only the first i characters. Since there are K operations, all operations affect only the order of the first K characters, leaving the rest of them in the original order. Hence, We can simply append the string after k-th character to the final answer.

Now, let’s try applying %5% operations on string 1234567.

  • After 1 operation, the string becomes 1234567
  • After 2 operations, the string becomes 2134567
  • After 3 operations, the string becomes 3124567
  • After 4 operations, the string becomes 4213567
  • After 5 operations, the string becomes 5312467.

We can easily see the pattern in which the characters appear. We can obtain string 54321 by maintaining two pointers, left one at position 0 and the right one at position K-1. Now we repeat the following process K times.

If the index of current turn is odd (1 based), then pick the character at the position of the left pointer, and move the left pointer one position to the right. Otherwise, pick the character at the position of the right pointer, and move the right pointer one position to the left.

This way, we obtain string 54321, which we can reverse to obtain 12345, and append 67 from the given string.

Hence, all needed to solve this problem was trying out a couple of strings and identifying the pattern.

TIME COMPLEXITY

The time complexity is O(N) per test case.

SOLUTIONS

Setter's Solution
test_cases=int(input())
for _ in range(test_cases):
    N,K=map(int,input().split())
    S=input().rstrip('\n')
    S1=list(S)
    Current_Character=0
    for i in range(K,0,-2):
	    S1[i-1]=S[Current_Character]
	    Current_Character+=1
    Next=1+(K%2)
    for i in range(Next,K,2):
	    S1[i-1]=S[Current_Character]
	    Current_Character+=1
    print(''.join(S1))
Tester's Solution
for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    ans = list(s)
    ans[k-1::-2] = s[0:(k+1)//2]
    ans[k%2:k:2] = s[(k+1)//2:k]
    print(''.join(ans))
Editorialist's Solution
import java.util.*;
import java.io.*;
class RMNTREV{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), K = ni();
        String S = n();
        int L = 0, R = K-1;
        StringBuilder ans = new StringBuilder();
        for(int i = 0; i< K; i++){
            if(i%2 == 0)ans.append(S.charAt(L++));
            else ans.append(S.charAt(R--));
        }
        ans = ans.reverse();
        ans.append(S.substring(K));
        pn(ans.toString());
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new RMNTREV().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

3 Likes
#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long t;
    cin>>t;
    while(t--){
      long n,k,i,j,l,r,temp;
      cin>>n>>k;
      temp=k;
      string s,s1;
      cin>>s;
      s1="";
        j=k/2;
        if(k%2==0){
            l=j-1;
            r=j;
            while(l>=0 && r<temp){
                s1=s1+s[r];
                s1=s1+s[l];
                r++;
                l--;
            }
        }
        else{
            l=j-1;
            r=j+1;
            s1=s1+s[j];
            while(l>=0 && r<temp){
                s1=s1+s[r];
                s1=s1+s[l];
                r++;
                l--;
            }
        }
        if(temp<n)
        s1=s1+s.substr(temp,n-temp);
        cout<<s1<<"\n";
    }
    return 0;
}
``` This is getting TLE ...can someone explain why
2 Likes

#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
int N;
cin>>N;
int i;
int K;
cin>>K;
string s;
cin>>s;
string a=s.substr(0,K);
string ans;
int n=a.size();
if(n%2==0)
{
for(i=0;i<n;i++)
{
if(i%2==0)
{
ans=ans+a[n/2+i/2];
}else
{
ans=ans+a[n/2-(i+1)/2];
}
}
}else
{
for(i=0;i<n;i++)
{
if(i%2==0)
{
ans=ans+a[n/2-i/2];
}else
{
ans=ans+a[n/2+(i+1)/2];
}
}
}
ans=ans+s.substr(K,N-K);
cout<<ans<<endl;
}
return 0;
}

Even this got TLE. i don’t understand how an O(n) solution can give TLE.

Thank goodness I didn’t attend this contest live.

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

int main()
{
int t ; cin >>t;
while( t–)
{

    int n , k;   
    cin >> n >> k ;
      string s;
    
    string ans(n,0);
    cin>>s;
    cout<<s<<endl;
    int j =0;
    
        for(int i =0 , j= k-1 , point = k-1 ; point >= 0 ; i++, j--, point -=2 )
        {
             ans[point]    = s[i];
             
             if(point-1 >=0)
              ans[point -1] = s[j];
           
        }
        
                                                                                                                   
     for(int i =k ;i<n ;i++)
        ans[i] = s[i];
      
 
         cout<<ans<<endl;
      
}

return 0 ;
}

1 Like

https://www.codechef.com/viewsolution/55456186

I did the same thing but still got WA. What am i missing here…https://www.codechef.com/viewsolution/55456186

I do understand the logic behind. I observed that formation of sequence ‘531024’ (0-based indexing) for k=6. So i just ran for loops for populating string. It does seem to give me right answers for given test cases and other test cases i formed. Can you guys please tell me what do i seem to miss. Or maybe my whole logic seem to be wrong somewhere.

int main(){
    file_io();
    int tc;
    cin>>tc;
    while(tc--){
        ll n,k; string s;
        cin>>n>>k>>s;
        char news[n];
        memset(news, '0', sizeof news);
        if(k==1){
            cout<<s<<endl;
            continue;
        }
        // if(k<=2000){
        //     for(ll i=k; i>=0; i--){
        //         reverse(s.begin(), s.begin()+i);
        //     }
        //     cout<<s<<endl;
        //     continue;
        // }
        ll tmp=k-1,j=0;
        if(tmp%2){
            for(ll i=tmp; i>=1; i-=2,j++){
                news[i]=s[j];
                // cout<<news[i];
            }
            for(ll i=0; i<k; i+=2,j++){
                news[i]=s[j];
                // cout<<news[i];
            }
        }
        else{
            for(ll i=tmp; i>=0; i-=2,j++){
                news[i]=s[j];
            }
            for(ll i=1; i<k; i+=2,j++){
                news[i]=s[j];
            }
        }
        while(j<n){
            news[j]=s[j];
            j++;
        }
        cout<<news<<endl;
    }
    return 0;
}

Mine is O(N) soln.
Still gives TLE!
Why?

https://www.codechef.com/viewsolution/55418975

mine is giving TLE for the last test case.

The reason for TLE with most of the solutions in the comments
is the string + operation

a = a + b;
will copy the whole string making it n^2.
Instead do a+= b; which will be O(n)

TLE solution :
https://www.codechef.com/viewsolution/55460267

AC solution with +=
https://www.codechef.com/viewsolution/55469847

7 Likes
3 Likes

Oh man, I never knew += actually overloads push_back char operation. I normally do this kinda thing using push_back :stuck_out_tongue: since I was 2 star.
Thanks for the knowledge.

Any suggestion why my O(N) solution was timing out.
https://www.codechef.com/viewsolution/55419426

Is it because string = char + string takes more time than string += char?

string ans = “”
ans = ‘a’ + ans;
ans += ‘a’;

Is it the case here?

yes it is.

consider
P1 : ans = ‘a’ + ans;
P2 : ans1 = ‘a’ + ans;

Here ‘a’ + ans will create an entirely new string by copying since it can’t modify ans.

1 Like

This didn’t work for me.
Please help me figure it out.

https://www.codechef.com/viewsolution/55473528

Sorry no idea about java.
But I suspect something to do with string

This says string in java is immutable. So I think += will do copy of whole string.

Can somebody tell me why my code is giving an error and WA
I think I am correct and something wrong with the string datatype

https://www.codechef.com/viewsolution/55572827

Your solution, is absolutely correct Sir, But the time Complexity is O(n^2).
Thus, the TLE.