Intermediate.
Put your skills to the test.

Problem summary

Produce the effect of rotating a word left N times using the fewest reversals of contiguous substrings. Repeated letters can make fewer operations possible than the usual three-reversal rotation.

Constraints

1 ≤ word length ≤ 20; 1 ≤ N ≤ 10000.

Worked example

Input and output for the worked example discussed below.

ALABALA
8

1
1 6

Solution analysis

1. Reduce N modulo the word length and construct the exact target rotation. If it equals the original word, zero reversals are optimal even when the reduced shift is nonzero, because periodic words can be unchanged.
2. Enumerate every nontrivial interval and test whether reversing it reaches the target. If none does, enumerate every ordered pair of intervals. At length 20 there are only 190 intervals, so comparing all pairs is practical.
3. If zero, one, and two operations all fail, three always suffice: reverse the first k characters, reverse the remaining suffix, then reverse the entire string. This changes A+B into B+A. Because smaller answers were exhaustively excluded, the three-operation construction is optimal.
4. For ALABALA and N=8, the effective shift is 1. Reversing positions 1…6 changes ALABALA into LABALAA, exactly the target, so one operation is enough. The output is a witness; different optimal intervals may be accepted.

Why it works

The first three search stages exhaust every sequence of length 0, 1, or 2. Reversing A, B, then all of reverse(A)+reverse(B) produces B+A, proving a solution of length at most 3 always exists. The first successful stage therefore has minimum length.

Watch out. Do not assume three is always minimal. Reduce the rotation count before constructing intervals. Output inclusive 1-based endpoints. The target is a left rotation.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<string>
#include<utility>
#include<vector>
using namespace std;
void print(const vector<pair<int,int>>&operations){
    cout<<operations.size()<<'\n';
    for(auto[left,right]:operations){
        cout<<left+1<<' '<<right+1<<'\n';
    }
}
int main(){
    string word;
    int rotations;
    cin>>word>>rotations;
    int length=word.size();
    int shift=rotations%length;
    string target=word.substr(shift)+word.substr(0,shift);
    if(word==target){
        print({});
        return 0;
    }
    vector<pair<int,int>>intervals;
    for(int left=0;left<length;left++){
        for(int right=left+1;right<length;right++){
            intervals.push_back({left,right});
        }
    }
    for(auto first:intervals){
        string changed=word;
        reverse(changed.begin()+first.first,changed.begin()+first.second+1);
        if(changed==target){
            print({first});
            return 0;
        }
    }
    // Exhaust all two-operation solutions before using the guaranteed upper bound.
    for(auto first:intervals){
        string changed=word;
        reverse(changed.begin()+first.first,changed.begin()+first.second+1);
        for(auto second:intervals){
            string result=changed;
            reverse(result.begin()+second.first,result.begin()+second.second+1);
            if(result==target){
                print({first,second});
                return 0;
            }
        }
    }
    print({{0,shift-1},{shift,length-1},{0,length-1}});
}