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. 
since I was 2 star.