Canadian Computing Olympiad: 2022 Day 2, Problem 3

Finn is playing a game of Twos and Threes. Twos and Threes is a one-player game played on a one-dimensional board. In the starting position, there are $N$ blocks arranged in a row, with each block labelled either $A$ or $B$. Blocks are numbered from $1$ to $N$ from left to right. Finn is allowed to make moves of the following form:

• Select $2$ or $3$ consecutive blocks that share the same label. Remove them from the board. Connect any remaining blocks together. Re-index the blocks from left to right, starting with index $1$.

Finn wins the game if all blocks are removed from the board. Your task is to help Finn determine a winning sequence of moves, or determine if the game cannot be won.

Input Specification

The first line of input will contain the integer $N$.

The second line of input will contain the string $S$, which is the starting position of the game.

There are $N$ characters in $S$, and each of these characters in $S$ is either A or B.

Marks Awarded	Bounds on $N$
$3$ marks	$1\le N\le 15$
$6$ marks	$1\le N\le 300$
$7$ marks	$1\le N\le 6000$
$9$ marks	$1\le N\le {10}^6$

Output Specification

If there is a winning sequence of moves, output $K$, the number of moves in the winning sequence. On each of the next $K$ lines, print an index $i$, followed by one space, followed by a number $j$, denoting a move that will remove the blocks currently at indices $i$ to $i+j-1$, inclusive.

If there is no winning sequence of moves, output -1.

If there are multiple winning sequences, then any winning sequence will be accepted. There is no need to minimize or maximize $K$.

Sample Input

9
ABAABBBAA

Possible Output for Sample Input

4
6 2
3 2
2 2
1 3

Explanation of Output for Sample Input

The sample output denotes this winning sequence:

$${\displaystyle \begin{array}{rl}& ABAAB\underset{―}{BB}AA\\ & AB\underset{―}{AA}BAA\\ & A\underset{―}{BB}AA\\ & \underset{―}{AAA}\end{array}}$$