PROBLEM LINK:
Author: Anubhav Bindlish
Tester: Anmol Gulati
Editorialist: Anmol Gulati
DIFFICULTY:
CAKEWALK
PREREQUISITES:
None
PROBLEM:
Given a N-length string, you need to carry out N-D+1 operations, wherin the i^{th} operation you reverse the substring S[i..i+D-1] and print the final output string in the end.
EXPLANATION:
Let’s simulate every operation, and see what’s exactly happening.
Initially: S = S_{1}S_{2}S_{3}...S_{D-1}S_{D}S_{D+1}...S_{N-1}S_{N}
operation 1: S = S_{D}S_{D-1}...S_{2}S_{1}S_{D+1}...S_{N-1}S_{N}
operation 2: S = S_{D}S_{D+1}S_{1}...S_{D-1}S_{D+2}...S_{N-1}S_{N}
operation 3: S = S_{D}S_{D+1}S_{D+2}S_{D-1}S_{D-2}...S_{2}S_{1}S_{D+3}...S_{N-1}S_{N}
…
operation 2K: S = S_{D}...S_{D+K-1}S_{1}S_{2}...S_{D-1}S_{D+K}...S_{N-1}S_{N}
operation 2K+1: S = S_{D}...S_{D+K}S_{D-1}S_{D-2}...S_{1}S_{D+K+1}...S_{N-1}S_{N}
So, if you carefully observe, doing all the operations, we will have two cases for the solution based on the pairity of the number of operations,i.e, N-D+1.
Clearly,
if N-D+1 is even: S^{'} = S_{D}...S_{N}S_{1}S_{2}...S_{D-1}
else if N-D+1 is odd: S^{'} = S_{D}...S_{N}S_{D-1}S_{D-2}...S_{1}
AUTHOR’S AND TESTER’S SOLUTIONS:
Tester’s solution can be found here.