[PYTHON] [Competition Pro] Algorithm that turns the sandwiched part over to make it ● ○ ●● ○○○ ● → ○○○○○○○○ (JSC2019-C Cell Inversion) [Explanation in the figure]
I'm not afraid to count anymore ~ 35 competition pro counting problems ~ --Qiita One of the problems introduced in the article seemed to be interesting, so I solved it. I tried it. By the way, I wrote it including thinking while solving the problem, so I have not arrived at the solution in the shortest time. If you want to see the shortest & best solution, please see the model answer linked from the question sentence page.
problem
$ 2N $ cells are lined up in a row on the left and right, and given a string $ S $ of length $ 2N $ that represents the color of each cell. The color of the $ i $ th cell from the left is black when the $ i $ letter of $ S $ is'B'and white when it is'W'. You pick different $ 2 $ squares and perform the operation of flipping the colors of those squares and the squares between them exactly $ N $ times. Here, to invert the color of a square means to make it white if the color of the square is black, and to make it black if it is white. However, you cannot select the same cell more than $ 2 $ times through the operation. This means that each cell will be chosen exactly $ 1 $ times. Find the remainder by dividing $ 10 ^ 9 + 7 $ by how many ways you can make all the squares white after $ N $ operations. Here, the difference between the $ 2 $ methods that satisfy the conditions is that the $ 1 $ second method is the $ 2 $ pair of cells selected in the $ i $ th way. $ 2 $ It means that there exists $ i (1 \ leq i \ leq N) $ that has a different set of $ 2 $ squares selected by the second method.
Let's touch a little
B is represented by ● or black, and W is represented by ○ or white. The word "turn over" is used for "reversal". Imagine Othello. There is an example of ● ○ ●● ○○○ ● in the problem statement, so let's solve it.
As a starting point, let's turn it over according to the procedure.
This did not become ○○○○○○○○.
Let's try it again.
This is now ○○○○○○○○.
Let's describe the procedure for turning over, pairing the positions in the order of turning over. In the above example, it would be $ (2,8) (1,4) (6,7) (3,5) $. Let's call such an arrangement of pairs in the order of flipping ** inversion column **.
The order of turning over does not matter
After trying a few things, if the flipping pairs are the same, you can see that the flipping order has nothing to do with the pattern of the final square.
For example, $ (2,8) (1,4) (6,7) (3,5) $ and $ (1,4) (2,8) (3,5) (6,7) $ have the same result. Will be.
Hereafter, the square pattern is called ** black and white pattern **.
Normalize the inverted column
Since the pattern (black and white pattern) that is finally created is the same even if the pairs are exchanged in the inverted column, set a rule so that it is uniquely determined. Let's call this operation ** inverted column normalization **.
- Write the smaller number on the left
- Arrange the pairs in ascending order of numbers on the left
If $ (2,8) (1,4) (6,7) (3,5) $ is arranged according to the above rules, $ (1,4) (2,8) (3,5) (6) , 7) $.
Also, let's call the one that extracts only the left side of the normalized inversion column ($ \ {1,2,3,6 \} $ in this case) ** left inversion column **.
Think the other way around
Well, I still have no idea how to turn it over to make all of ● ○ ●● ○○○ ● white.
Therefore, check what happens when all white squares (○○○○○○○○) are turned over according to the procedure, within the range where $ N $ is small.
There is an opposite relationship between changing ● ○ ●● ○○○ ● to ○○○○○○○○ and changing ○○○○○○○○ to ● ○ ●● ○○○ ●. This is because if you change ○○○○○○○○ to ● ○ ●● ○○○ ● and then turn it over in the same inverted column, it will return to ○○○○○○○○.
N=1
When $ N = 1 $, there is one way to turn it over.
N=2
When $ N = 2 $, there are 3 ways to turn it over, but there are 2 types of black and white patterns.
N=3
When $ N = 3 $, there are 15 ways to flip and 5 black and white patterns.
Discovery of rules
There are some discoveries so far, so let's summarize them.
Ultimately white or black depends on the number of lines drawn below
The number of lines underneath (or extending from yourself) is flipped over, so the number of lines will ultimately determine whether the square will be white or black. It is white when the number of lines is even and black when it is odd.
Both ends of the black and white pattern are black
Both ends are black because they are flipped over when you select yourself and are not sandwiched between other squares.
When split into clusters, both ends of each cluster are black
Dividing into a cluster means that the inversion is completed within a certain interval as shown below.
When split into clusters, both ends of each cluster are black.
Looking at the inverted columns of each pattern, the numbers in the left inverted column are common.
With $ N = 3 $, put together the swap columns for each black and white pattern.
If you group the inverted columns for each black and white pattern, you will notice that the left and right sides of the inverted column are the same for each black and white pattern. For example, in the inverted column that changes ○○○○○○ to ● ○○○○ ●, $ \ {1,2,4 \} $ appears on the left side of the pair, and $ \ {3, on the right side. 5,6 \} $ will appear.
The result is the same even if the overlapping (L1, R1) (L2, R2) is replaced with (L1, R2) (L2, R1).
The black and white patterns of the bottom two inverted columns $ (L_1, R_1) (L_2, R_2) $ and $ (L_1, R_2) (L_2, R_1) $ are the same. This is because the number of lines under the square does not change.
There is only one inverted column in each black and white pattern where the lines do not intersect each other
Crossing lines refers to the following situations:
When connecting flipping pairs with a line, there is only one inverted row for each black and white pattern where the lines do not intersect. If $ N = 3 $, this is the inverted column respectively.
Let's call the inverted columns whose lines do not intersect each other ** non-intermesh inverted columns **.
In the non-intermesh inversion column, the inversion pairs have the same color
In the non-intermesh inversion column, those with connected lines will have the same color after the operation is completed. In a swap row where the lines do not intersect each other, the flipping pair is either surrounded by or separated from the other pairs, so it either flips at the same time or does not flip at the same time.
Find a pair next to each other
In a non-intermeshing inverted column, there is at least one pair of adjacent values. The pair has the same color in the black and white pattern. When looking at the squares from the left, if the colors are different, they are not a pair next to each other.
Put it on the stack and find the pair
When I was vaguely looking at the list of non-intermeshed inverted columns, it seemed to correspond to the parentheses in the formula.
Use the stack to create such a correspondence.
First, find a pair next to each other. Since they are next to each other, the values are continuous. Stack them up until you find a series of colors.
Take ● ○ ●● ○○○ ● as an example.
It is the initial state.
Put the first ● on the stack.
The second circle is a different color from the first, so put it on the stack.
The third ● is a different color from the second, so put it on the stack.
The 4th ● is the same color as the top of the stack, so take the top of the stack and pair it with the 4th.
The 5th circle is the same color as the top of the stack, so take the top of the stack and pair it with the 5th.
The 6th circle is a different color from the top of the stack, so put it on the stack.
The 7th circle is the same color as the top of the stack, so take the top of the stack and pair it with the 7th.
Finally, the 8th ● is the same color as the top of the stack, so take the top of the stack and pair it with the 8th.
Up to this point, $ (1,8) (2,5) (3,4) (6,7) $ is one solution to change ● ○ ●● ○○○ ● to ○○○○○○○○ It turned out to be. When you actually check it, it surely turns white.
Dealing with exception cases
The above is the case where the inverted column exists, but let's look at the exception here.
The bottom of the stack is white
Unless both ends are black, they cannot all be white. In other words, when you put it on the stack, the bottom must be black. Given an input that puts white at the bottom, there are $ 0 $ ways to make all cells white.
The stack is not empty when reading the square to the end
If the stack is not empty when you read the squares to the end, there is no combination that gives the given pattern. In this case, there are $ 0 $ ways to make all the cells white.
Number of cases where (L1, R1) (L2, R2) is replaced with (L1, R2) (L2, R1)
Replacing $ (L_1, R_1) (L_2, R_2) $ with $ (L_1, R_2) (L_2, R_1) $ gives the same result. Consider how many patterns of such replacements are for $ (1,8) (2,5) (3,4) (6,7) $.
Put $ \ {4, 5, 7, 8 \} $ in the part from $ R_1 $ to $ R_4 $, but since there is a constraint of $ L_i <R_i $, let's start with $ R_4 $. ..
$ R_4 $: $ 7 $ or $ 8 $ $ R_3 $: One of $ 4 $, $ 5 $, $ 7 $, $ 8 $ (but not including the numbers used in $ R_4 $) $ R_2 $: $ 4 $, $ 5 $, $ 7 $, $ 8 $ (but not including the numbers used in $ R_4 $, $ R_3 $) $ R_1 $: 1 remaining number
Calculating this, $ 2 \ times 3 \ times 2 = 12 ways $.
Multiply by the number of flips
So far, the inverted columns have been normalized, but we want to distinguish the flip order, so multiply by $ N! $.
$ 12 \times 4! = 288 $
Divide by 10000000007
Finally, divide the calculated number by $ 10 ^ 9 + 7 $. In actual programming, in the process of calculating the above combination, divide it appropriately by $ 10 ^ 9 + 7 $ and devise so that the digits do not overflow.
$ 288 \bmod (10^9+7) = 288$
The answer 288 was derived.
Can be solved without a stack
I used the stack this time, but it can be solved without the stack. For details, please see the explanation of the head family.
Source code
I implemented the above algorithm (improved) in Python (version 3.7). (Implemented before dividing by $ 10 ^ 9 + 7 $, so it can handle only a small range of $ N $)
Further challenges
The black and white pattern that appears for every $ N $ is $ N = 1 $ and $ 1 $ type $ N = 2 $ and $ 2 $ type $ 5 $ type with $ N = 3 $ I found out that there is. What happens if you increase the number to $ N = 6, 7, 8 $?
Afterword
I wrote it briefly, but it took me three days to come up with an algorithm after I started thinking about the problem in earnest. (I saw the explanation because there was a part I didn't understand at the end.) I solved it a lot more than the explanation of the head family, but I enjoyed the various discoveries. When I think that the contest participants are solving such a problem at a glance, I get only a shallow impression that it is scary.
Recommended Posts