SSWAP - Editorial

PROBLEM LINK:

Practice

Contest

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.

//