USACO

USACO 2024 February Contest, Silver

Problem 2. Test Tubes

Contest has ended.

Log in to allow submissions in analysis mode

Bessie has recently gotten into chemistry. At the moment, she has two different colors $1$ and $2$ of various liquids that don't mix well with one another. She has two test tubes of infinite capacity filled with $N$ $(1 \leq N \leq 10^5)$ units each of some mixture of liquids of these two colors. Because the liquids don’t mix, once they settled, they divided into layers of separate colors. Because of this, the two tubes can be viewed as strings $f_1f_2\ldots f_N$ and $s_1s_2\ldots s_N$ where $f_i$ represents the color of the liquid that is $i$ units from the bottom of the first tube, and $s_i$ represents the color of the liquid that is $i$ units from the bottom of the second tube. It is guaranteed that there is at least one unit of each color of liquid.

Bessie wants to separate these liquids so that each test tube contains all units of one color of liquid. She has a third empty beaker of infinite capacity to help her in this task. When Bessie makes a "pour", she moves all liquid of color $i$ at the top of one test tube or beaker into another.

Determine the minimum number of pours to separate all the liquid into the two test tubes, and the series of moves needed to do so. It does not matter which test tube ends up with which color, but the beaker must be empty..

There will be $T$ ($1 \leq T \leq 10$) test cases, with a parameter $P$ for each test case.

Suppose the minimum number of pours to separate the liquids into the original tubes is $M$.

If $P=1$, you will receive credit if you print only $M$.
If $P=2$, you will receive credit if you print an integer $A$ such that $M \leq A \leq M+5$, followed by $A$ lines that construct a solution with that number of moves. Each line should contain the source and the destination tube ($1$, $2$, or $3$ for the beaker). The source tube must be nonempty before the move and a tube may not be poured into itself.
If $P=3$, you will receive credit if you print $M$, followed by a valid construction using that number of moves.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $T$, the. number of test cases. For each test case, the next line contains $N$ and $P$ representing the amount each test tube is initially filled to, and the query type. The following line contains $f_1f_2f_3\ldots f_N$ representing the first test tube. $f_i \in \{ 1,2 \}$ and $f_1$ represents the bottom of the test tube. The subsequent line contains $s_1s_2s_3\ldots s_N$ representing the second test tube. $s_i \in \{ 1,2 \}$ and $s_1$ represents the bottom of the test tube.

It is guaranteed that there will be at least one $1$ and one $2$ across both input strings.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, you will print a single number representing the minimum pours to separate the liquid in the test tubes. Depending on the query type, you may also need to provide a valid construction.

SAMPLE INPUT:

SAMPLE OUTPUT:

In the first three test cases, the minimum number of pours to separate the tubes is $4$. We can see how the following moves separate the test tubes:

Initial state:

1: 1221
2: 2211
3:

After the move "1 2":

1: 122
2: 22111
3:

After the move "1 3":

1: 1
2: 22111
3: 22

After the move "2 1":

1: 1111
2: 22
3: 22

After the move "3 2":

1: 1111
2: 2222
3:

In the last test case, the minimum amount of pours is $5$. However, since $P=2$, the given construction with $6$ moves is valid since it is within $5$ pours from the optimal answer.

SCORING:

Inputs 2-6: $P = 1$
Inputs 7-11: $P=2$
Inputs 12-21: No additional constraints.

Additionally, it is guaranteed that $T=10$ for all inputs besides the sample.

Problem credits: Suhas Nagar

Contest has ended. No further submissions allowed.