Finding hints for the solution by trial and error

In competitive programming, “experimenting” with cases such as sample inputs can sometimes lead to clues for the solution.

Let’s consider a concrete example right away: how to change the state from the initial 00000 to 01010. For example, you might think about it by trial and error as follows:

Since we want to match each character one by one, let’s first think about turning the second character into 1. If we press A, A, B in order, it goes from 00000 → 10000 → 11000 → 01000. Now we just need to turn the fourth character into 1. But how do we proceed from here?

• For example, if we press A three times in a row, it goes from 01000 → 11000 → 11100 → 11110. However, the effort to turn only the second character into 1 is wasted.
• Maybe we should have pressed B somewhere. For example, after pressing A once to make it 11000 and then pressing B, it becomes 01000. However, pressing A again returns it to 11000. So, in the end, it’s the same as before.

In other words, even if you turn the second character into 1 once, trying to match the fourth character to 1 will waste that effort. Therefore, you must first consider turning the fourth character into 1. You can achieve the state 01010 as follows:

• First, we want to turn the fourth character into 1. If we press A, A, A, A, B, B, B in order, it goes from 00000 → 10000 → 11000 → 11100 → 11110 → 01110 → 00110 → 00010.
• Now we just need to turn the second character into 1. If we press A, A, B in order, it goes from 00010 → 10010 → 11010 → 01010 (the same method as the previous example).

How to solve the puzzle

First, to turn only the \(k\)-th character into 1 from the state 000...0, you need to “press switch A \(k\) times in a row, then press switch B \(k-1\) times in a row”. This method can also be used when you want to change characters before the \(k\)-th character into 1 afterward.

Therefore, assuming that 1 appears as the \(x_1\)-th, \(x_2\)-th, \(\dots\), \(x_k\)-th characters of \(S\) \((x_1 < x_2 < \dots < x_k)\), you can achieve the desired state as follows:

• Press A \(x_k\) times in a row, then press B \(x_k-1\) times in a row (the \(x_k\)-th character changes to 1)
• (Omitted)
• Press A \(x_2\) times in a row, then press B \(x_2-1\) times in a row (the \(x_2\)-th character changes to 1)
• Press A \(x_1\) times in a row, then press B \(x_1-1\) times in a row (the \(x_1\)-th character changes to 1)

Sample implementations

A sample implementation in C++ is at https://atcoder.jp/contests/arc177/submissions/53281593.

In Python, the solution can be implemented as follows:

# Input
n = int(input())
s = input()

# Find the solution
ans = ''
for i in range(n-1, -1, -1):
	if s[i] == '1':
		ans += 'A' * (i+1) + 'B' * i

# Output
print(len(ans))
print(ans)