Google Code Jam Archive — Round 2 2021 problems
Overview
Code Jam's 2021 Round 2 was a different kind of challenge, with no easy points on the table. The first problem, Minimum Sort, was interactive, which is always tricky. However, it could be solved with one of the first algorithms most of us learned. Matrygons had a geometry glazing but it was actually about arithmetic observations and a recursion. As usual, the third problem is when things really heated up. Pancakes had a pretty shy year, waiting until Round 2 to show up, and even then, they were Hidden Pancakes. A classical problem of optimizing a dynamic programming through combinatorics. The round's last problem had a more classical flavor. Retiling was all about properly modeling the problem with graphs and then applying the right algorithm.
The scoreboard saw action pretty fast this time, with several successful submissions in the first 10 minutes and a few contestants getting the first two problems done within 15 minutes. Radewoosh was the fastest to a perfect score at 36 minutes and 9 seconds, and with no penalty attempts, which assured them the top position. ksun48 followed less than 30 seconds later for second place. maroon was the only other coder that had a perfect score with under 40 minutes of penalty, rounding out the top 3. At the end, 3862 contestants got a positive number of points and 284 of them finished with a perfect 100 points. The preliminary cutoff to advance to Round 3 is 66 points and a low enough penalty.
The results will be reviewed in the coming days. Those who are in the top 1000 after the round is marked finalized advance to the last elimination round of the year! There are 3 weeks to get and/or stay in good shape until Round 3 (see the schedule for details). You can practice with any of our past problems from the archive.
For those of you for whom this round is the end of the season, we hope you are very proud of making it this far. We are certainly amazed by how the problem solving skills of everyone keep getting better every year. You can see a certificate highlighting your accomplishment in your profile page.
Cast
Minimum Sort: Written and prepared by Mohamed Yosri Ahmed.
Matrygons: Written by Ian Tullis. Prepared by Artem Iglikov.
Hidden Pancakes: Written and prepared by Ikumi Hide.
Retiling: Written by Pablo Heiber. Prepared by Darcy Best.
Solutions and other problem preparation and review by Andy Huang, Artem Iglikov, Darcy Best, Hannah Angara, Ikumi Hide, Liang Bai, Max Ward, Md Mahbubul Hasan, Mekhrubon Turaev, Mohamed Yosri Ahmed, Nafis Sadique, Pablo Heiber, Pi-Hsun Shih, Shane Carr, Swapnil Gupta, Timothy Buzzelli, Vaibhav Tulsyan, and Yui Hosaka.
Analysis authors:
- Minimum Sort: Pablo Heiber.
- Matrygons: Pablo Heiber.
- Hidden Pancakes: Darcy Best, Pablo Heiber and Timothy Buzzelli.
- Retiling: Pablo Heiber.
A. Minimum Sort
Problem
In this problem, you need to sort a list of $$$\mathbf{N} = 100$$$ distinct integers in strictly increasing order. You can rearrange the list by swapping the contents of any two positions (they do not need to be adjacent). Unfortunately, you cannot read those contents directly. You can access information about the list contents by querying the minimum of a range. The minimum query gives you the position of the minimum value over a range of consecutive positions. For example, in the list $$$[51, 33, 100, 11]$$$, the minimum over the range between positions $$$2$$$ and $$$4$$$, inclusive ($$$1$$$-based), is at position $$$4$$$ and the minimum between positions $$$1$$$ and $$$3$$$ is at position $$$2$$$.
Queries about the minimum within a range are limited by a coin budget per test case. Larger ranges are cheaper: asking about the position of the minimum between positions $$$i$$$ and $$$j$$$ (for $$$i \lt j$$$) costs $$$\lceil 10^8 / (j - i + 1) \rceil$$$ coins, where $$$\lceil x \rceil$$$ is the smallest integer greater than or equal to $$$x$$$ (that is, $$$x$$$ rounded up). Swap operations, on the other hand, do not cost any coins.
Write a program that sorts lists of integers using any number of swaps and at most $$$6 \times 10^8$$$ coins per test case distributed among any number of minimum queries.
Input and output
This is an interactive problem. You should make sure you have read the information in the Interactive Problems section of our FAQ.
Initially, the judge will send you a single line containing two integers $$$\mathbf{T}$$$ and $$$\mathbf{N}$$$: the number of test cases and the number of elements to sort within each test case, respectively. The judge has the initial lists preset before it gets any input from your program, and the only changes done to them during the exchanges with your program are the swaps that you request.
Then, you must process $$$\mathbf{T}$$$ test cases. Each test case consists of a series of exchanges plus an additional line indicating you are done. Each exchange consists of you printing one line and the judge printing one line in response. Your program must print a single line containing one of these options:
- An uppercase
Mand two integers $$$i$$$ and $$$j$$$ with $$$i \lt j$$$ representing a minimum query. The judge responds with a single integer representing the position of the minimum value in the list within 1-based positions $$$i$$$ and $$$j$$$, inclusive. - An uppercase
Sand two integers $$$i$$$ and $$$j$$$ with $$$i \lt j$$$ representing a swap operation. The judge swaps the two elements at 1-based positions $$$i$$$ and $$$j$$$ and responds with1. - An uppercase
Drepresenting that you are done sorting the list. The judge checks the list. It responds with1if the list is sorted in strictly increasing order and-1if it is not.
After the judge responds 1 to a D, it will finish
if it was the last test case or it will immediately start waiting for your first
command for the next test case. After receiving the judge's response for the
$$$\mathbf{T}$$$-th case, your program must finish in order to not receive a Time Limit Exceeded
error.
If the judge receives an invalidly formatted line or invalid values from your
program at any moment, including a minimum operation whose cost would exceed
your remaining budget for the test case, the judge will print a single number -1.
After the judge prints -1 for any of the reasons explained above,
it will not print any further output. If your program continues to wait for the judge after
receiving a -1, your program will time out, resulting in a Time Limit
Exceeded error. Notice that it is your responsibility to have your program
exit in time to receive a Wrong Answer judgment instead of a Time Limit
Exceeded error. As usual, if the memory limit is exceeded, or your program
gets a runtime error, you will receive the appropriate judgment.
Limits
Time limit: 60 seconds.
Memory limit: 1 GB.
Test Set 1 (Visible Verdict)
$$$\mathbf{T} = 100$$$.
$$$\mathbf{N} = 100$$$.
2 4
List: $$$[51, 33, 100, 11]$$$
M 2 4
This operation cost $$$\lceil 10^8 / 3 \rceil = 33333334$$$ coins
4
M 1 3
This operation cost $$$\lceil 10^8 / 3 \rceil = 33333334$$$ coins
2
S 1 4
1
M 3 4
This operation cost $$$\lceil 10^8 / 2 \rceil = 50000000$$$ coins
4
S 3 4
1
D
The solution spent a total of $$$116666668$$$ coins
1
List: $$$[30, 20, 10, 40]$$$
M 1 4
This operation cost $$$\lceil 10^8 / 4 \rceil = 25000000$$$ coins
3
S 1 3
1
M 3 4
This operation cost $$$\lceil 10^8 / 2 \rceil = 50000000$$$ coins
3
M 2 4
This operation cost $$$\lceil 10^8 / 3 \rceil = 33333334$$$ coins
2
D
The solution spent a total of $$$108333334$$$ coins
1
Testing Tool
You can use this testing tool to test locally or on our platform. To test locally, you will need to run the tool in parallel with your code; you can use our interactive runner for that. For more information, read the instructions in comments in that file, and also check out the Interactive Problems section of the FAQ.
Instructions for the testing tool are included in comments within the tool. We encourage you to add your own test cases. Please be advised that although the testing tool is intended to simulate the judging system, it is NOT the real judging system and might behave differently. If your code passes the testing tool but fails the real judge, please check the Coding section of the FAQ to make sure that you are using the same compiler as us.
B. Matrygons
Problem
A matryoshka is a type of doll that originated in Russia over a century ago. Their defining characteristic is that they consist of a set of dolls, all of a different size, with smaller dolls fitting nicely inside larger dolls.
In this problem, we work with matrygons, which are sets of regular convex polygons that follow a similar nesting pattern. A matrygon consists of a set of regular convex polygons with positive area $$$p_1, p_2, \dots, p_k$$$ such that, for all $$$i$$$, the vertices of $$$p_{i+1}$$$ overlap with a proper subset of the vertices of $$$p_i$$$ ($$$p_{i+1}$$$ has strictly less vertices than $$$p_i$$$).
For example, the following pictures illustrates two matrygons. The first one contains $$$3$$$ regular convex polygons: a regular icositetragon ($$$24$$$ sides), a regular hexagon ($$$6$$$ sides), and an equilateral triangle ($$$3$$$ sides). The second one contains $$$2$$$ regular convex polygons: a regular icosidigon ($$$22$$$ sides) and a regular hendecagon ($$$11$$$ sides). Each of these matrygons has $$$33$$$ total sides among all polygons in it.
Given a fixed total number of sides $$$\mathbf{N}$$$, calculate the largest number of polygons that can be part of a matrygon such that the total number of sides among all polygons in it is exactly $$$\mathbf{N}$$$.
Input
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ lines follow. Each line represents a test case and contains a single integer $$$\mathbf{N}$$$, the target total number of sides.
Output
For each test case, output one line containing Case #$$$x$$$: $$$y$$$,
where $$$x$$$ is the test case number (starting from 1) and $$$y$$$ is the maximum
number of polygons in a matrygon such that the total number of sides among
all polygons in it is exactly $$$\mathbf{N}$$$.
Limits
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
Test Set 1 (Visible Verdict)
Time limit: 20 seconds.
$$$3 \le \mathbf{N} \le 1000$$$.
Test Set 2 (Visible Verdict)
Time limit: 40 seconds.
$$$3 \le \mathbf{N} \le 10^6$$$.
Sample
3 33 15 41
Case #1: 3 Case #2: 2 Case #3: 1
The first matrygon pictured in the problem statement is an optimal solution for Sample Case #1.
In Sample Case #2, we can get to two polygons by fitting a regular pentagon ($$$5$$$ sides) inside a regular decagon ($$$10$$$ sides).
In Sample Case #3, there is no way to create a matrygon with multiple regular polygons, so our only option is to use a single regular tetracontahenagon ($$$41$$$ sides).
C. Hidden Pancakes
Problem
We are cooking $$$\mathbf{N}$$$ pancakes in total. We cook one pancake with a $$$1$$$ centimeter (cm) radius, one with a $$$2$$$ cm radius, one with a $$$3$$$ cm radius, ..., and one with an $$$\mathbf{N}$$$ cm radius, not necessarily in that order. After we cook the first pancake, we just lay it on a plate. After we cook each subsequent pancake, we lay it on top of the previously made pancake, with their centers coinciding. In this way, a pancake is visible from the top of the stack when we first add it. A pancake only becomes hidden if we later cook another pancake with a larger radius.
For example, say we cook $$$4$$$ pancakes. We first cook the pancake with radius $$$3$$$ cm, and it is visible. Then, we cook the pancake with radius $$$1$$$ cm, lay it on top of the first one and both are visible. Third, we cook the pancake with radius $$$2$$$ cm, and now that covers the previous pancake, but not the first one, so $$$2$$$ pancakes remain visible in total. Finally, we cook the pancake with radius $$$4$$$ cm which covers the other pancakes leaving only $$$1$$$ visible pancake. The picture below illustrates the state of the stack after each pancake is cooked. Within each stack, the fully colored pancakes are visible and the semi-transparent pancakes are not visible.
Let $$$\mathbf{V_i}$$$ be the number of visible pancakes when the stack contains exactly $$$i$$$ pancakes. In the example above, $$$\mathbf{V_1} = 1$$$, $$$\mathbf{V_2} = 2$$$, $$$\mathbf{V_3} = 2$$$, and $$$\mathbf{V_4} = 1$$$.
Given the list $$$\mathbf{V_1}, \mathbf{V_2}, \dots, \mathbf{V_N}$$$, how many of the $$$\mathbf{N}!$$$ possible cooking orders yield those values? Since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime $$$10^9+7$$$ ($$$1000000007$$$).
Input
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow, each described with two lines. The first line of a test case contains a single integer $$$\mathbf{N}$$$, the number of pancakes we cook. The second line of a test case contains $$$\mathbf{N}$$$ integers $$$\mathbf{V_1}$$$, $$$\mathbf{V_2}$$$, ..., $$$\mathbf{V_N}$$$, representing the number of visible pancakes after we cook $$$1$$$, $$$2$$$, ..., $$$\mathbf{N}$$$ pancakes, respectively.
Output
For each test case, output one line containing Case #$$$x$$$: $$$y$$$,
where $$$x$$$ is the test case number (starting from 1) and $$$y$$$
is the number of cooking orders of $$$\mathbf{N}$$$ pancakes that yield the given numbers of visible pancakes
after each step, modulo the prime $$$10^9+7$$$ ($$$1000000007$$$).
Limits
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$1 \le \mathbf{V_i} \le i$$$, for all $$$i$$$.
Test Set 1 (Visible Verdict)
Time limit: 30 seconds.
$$$2 \le \mathbf{N} \le 13$$$.
Test Set 2 (Hidden Verdict)
Time limit: 40 seconds.
$$$2 \le \mathbf{N} \le 10^5$$$.
Sample
Note: there are additional samples that are not run on submissions down below.3 4 1 2 2 1 3 1 1 2 3 1 1 3
Case #1: 1 Case #2: 2 Case #3: 0
Sample Case #1 is explained in the problem statement. The order $$$3, 1, 2, 4$$$ is the only one that yields the given $$$\mathbf{V_i}$$$s.
In Sample Case #2, both the order $$$1, 3, 2$$$ and the order $$$2, 3, 1$$$ yield the intended $$$\mathbf{V_i}$$$s. The pictures below illustrate both options.
In Sample Case #3, only $$$1$$$ pancake is visible after the second is made, so there is no way to have more than $$$2$$$ visible pancakes by only adding a third.
Additional Sample - Test Set 2
The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.1 24 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2
Case #1: 234141013
In the Sample Case for Test Set 2, there are $$$316234143225$$$ cooking orders that yield the given $$$\mathbf{V_i}$$$s. Modulo $$$10^9+7$$$, this value is $$$234141013$$$.
D. Retiling
Problem
Cody-Jamal's latest artistic installment is a tiled kitchen floor that can be retiled to different patterns. The floor consists of a matrix of $$$\mathbf{R}$$$ rows and $$$\mathbf{C}$$$ columns of square tiles. Each tile is reversible, one side is magenta and the other one is green.
To retile the kitchen, there are two allowed operations:
- flip a tile, changing its visible color from magenta to green, or vice versa, and
- swap two adjacent tiles (horizontally or vertically, but not diagonally), without flipping either.
Viewing Cody-Jamal's artistic floor is free, but interacting with it is not. Performing a single flip operation costs $$$\mathbf{F}$$$ coins, and performing a single swap operation costs $$$\mathbf{S}$$$ coins.
You can see the current state of the floor and want to turn it into a particular pattern. What is the minimum amount of coins you need to spend to achieve your goal?
Input
The first line of the input gives the number of test cases, $$$\mathbf{T}$$$. $$$\mathbf{T}$$$ test cases follow.
The first line of a test case contains 4 integers: $$$\mathbf{R}$$$, $$$\mathbf{C}$$$, $$$\mathbf{F}$$$ and $$$\mathbf{S}$$$, the number of rows
and columns of the floor, the cost in coins of flipping and the cost in coins of swapping,
respectively. Then, $$$2 \cdot \mathbf{R}$$$ lines follow. The first $$$\mathbf{R}$$$ lines contain $$$\mathbf{C}$$$ characters
each. The $$$j$$$-th character of the $$$i$$$-th of these lines represents the current state
of the tile in the $$$i$$$-th row and $$$j$$$-th column. The character is M
if the currently visible side is magenta and G otherwise.
The last $$$\mathbf{R}$$$ lines also contain $$$\mathbf{C}$$$ characters each.
The $$$j$$$-th character of the $$$i$$$-th of these lines represents the color you want
for the tile in the $$$i$$$-th row and $$$j$$$-th column, using the same character code
as for the current state.
Output
For each test case, output one line containing Case #$$$x$$$: $$$y$$$,
where $$$x$$$ is the test case number (starting from 1) and $$$y$$$
is the minimum amount of coins you need to spend to perform operations that allow you to
change the tile colors from their current state to your intended one.
Limits
Time limit: 40 seconds.
Memory limit: 1 GB.
$$$1 \le \mathbf{T} \le 100$$$.
$$$1 \le \mathbf{R} \le 10$$$.
$$$1 \le \mathbf{C} \le 10$$$.
Test Set 1 (Visible Verdict)
$$$\mathbf{F} = 1$$$.
$$$\mathbf{S} = 1$$$.
Test Set 2 (Hidden Verdict)
$$$1 \le \mathbf{F} \le 10^6$$$.
$$$1 \le \mathbf{S} \le 10^6$$$.
Sample
Note: there are additional samples that are not run on submissions down below.2 2 4 1 1 MGMG MMMG GMGM MMMM 3 3 1 1 MGG GMG MMM MMM MGM MMG
Case #1: 3 Case #2: 4
In Sample Case #1, there are $$$5$$$ tiles that have a different color between the current and the desired states of the floor. Since each operation can change at most $$$2$$$ tiles, at least $$$3$$$ operations, costing $$$3$$$ coins, are needed. One way to do it with exactly $$$3$$$ coins is:
- Swap the leftmost two tiles in the top row.
- Swap the rightmost two tiles in the top row.
- Flip the bottom right corner tile.
The picture below illustrates the states the floor goes through. The highlighted tile or tiles in each state are the ones being changed by the operation.
In Sample Case #2, there are $$$6$$$ tiles that need changing. However, since only swaps can change two tiles at a time, solving it with $$$3$$$ operations would require all of them to be swaps. There is no way to involve all $$$6$$$ tiles in a single swap each, so we need at least $$$4$$$ operations. One way to use exactly $$$4$$$ operations is:
- Swap the topmost two tiles in the middle column.
- Flip the top right corner tile.
- Swap the bottommost two tiles in the rightmost column.
- Flip the middle tile of the leftmost column.
The picture below illustrates the states the floor goes through.
Additional Sample - Test Set 2
The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.1 1 5 1000 1 MGGGG GGGMM
Case #1: 1003
In the Sample Case for Test Set 2, flips are so expensive that we want to avoid them at all costs. We need at least one since our desired floor state has more magenta tiles than the current one, and swaps do not change that amount. We can do it optimally with just one flip like this:
- Swap the leftmost two tiles.
- Flip the rightmost tile.
- Swap the second and third tiles from the left.
- Swap the third and fourth tiles from the left.
The picture below illustrates all the states the floor goes through.
Analysis — A. Minimum Sort
In this problem, we are given only one tool to get information about our input: the minimum query. Moreover, the query becomes cheaper when done over long distances. This means a sorting algorithm that normally spends running time finding minimums would align well with our needs. One well known such algorithm is Selection sort.
In Selection sort, we search for the minimum of the full list, put that in its correct position (the beginning), and continue solving recursively searching for the minimum of a suffix of the list, and moving that minimum to the beginning. This can be implemented with $$$N-1$$$ pairs of the minimum query and (possibly) a swap operation as follows:
for i := 1 to N-1
j = minimum_index_of(i, i+1, ..., N)
if i != j:
swap(i, j)
The minimum queries above are over ranges of sizes $$$N, N-1, ..., 2$$$. This means the total cost is exactly $$$$\sum_{i=2}^{\mathbf{N}} \left\lceil \frac{10^8}{i} \right\rceil.$$$$ For $$$\mathbf{N}=100$$$, this is $$$418737795$$$, which is less than the limit of $$$6 \times 10^8$$$.
Analysis — B. Matrygons
Test Set 1
The statement of this problem requires calculating a function from integers to integers. After we select a polygon to use, the remainder of the work is similar to the overall: select more polygons. This almost screams: write a recursive solution!
One way of doing that is with a top-down approach: start by picking the largest polygon, and then pick the rest. For all polygons except the largest, there is the additional restriction of "fitting" into the previous polygon. That is, the number of sides of the new polygon must be a proper divisor of the number of sides of the last one.
We can code that into a simple function that takes a number of sides left $$$t$$$ and the size of the last polygon used $$$p$$$: $$$f(t, p) = 1 + \max_{q : q | p} f(t - q, q)$$$ (one plus the maximum $$$f(t - q, q)$$$ over all $$$q$$$s that are divisors of $$$p$$$) adding $$$f(0, p) = 0$$$ as base case, and appropriate conditions that $$$q$$$ is indeed a polygon. The answer is then $$$\max_p f(\mathbf{N}, p)$$$. This recursion is fast enough for the small bounds of Test Set 1 even if we iterate all possible $$$3 \le q \le \min(p - 1, t)$$$. Of course, we can avoid that and find the divisors faster by iterating only up to $$$\sqrt{p}$$$ and checking both $$$q$$$ and $$$p / q$$$, but the optimization is not necessary for Test Set 1, and not sufficient for Test Set 2.
Test Set 2
While memoization is the first instinct to speed up a recursive function, the function described has too large of a domain for that. A bottom-up approach, on the other hand, is much more suitable.
Consider starting from the smallest polygon. This can be done by using a function that is described by a similar expression, but swapping which of $$$p$$$ and $$$q$$$ is a parameter and which is iterated over: $$$f(t, q) = 1 + \max_{p : q | p} f(t - p, p)$$$. This switch allows for a significant speed up: when checking all possible $$$p$$$ we can simply jump by $$$q$$$, dividing the total size of the iteration by $$$q$$$. This is enough to pass Test Set 2 if implemented carefully, but it may be hard to be confident that it is.
We can do better and improve our confidence with the following observation: once we pick a polygon of size $$$q$$$, all future polygons will have sizes multiples of $$$q$$$. Therefore, we can divide the whole problem by $$$q$$$ (and allow pseudo-polygons of size $$$2$$$) by setting $$$f(t, q) = f(t / q, 1)$$$. If we are careful about not allowing size $$$2$$$ for the very first polygon, this leaves us having to calculate only $$$g(t) = f(t, 1)$$$, which has a domain of memoizable size. If we add memoization, we have a faster solution, and more importantly, one for which we can pre-compute the entire recursive function and be sure about the running time irrespective of the input.
Analysis — C. Hidden Pancakes
Test Set 1
For Test Set 1, the number of pancakes is small enough to do something exponential. One possible way would be to go through every possible order of pancakes. That would be too slow, but we can identify some repetition: any hidden pancakes at any point could be hidden in multiple ways, and that does not affect how we continue the process. Removing the cost of calculating these overlapping cases leads to a dynamic programming solution.
We can formalize the idea above as follows: instead of remembering exactly the current stack of pancakes as the current state, we can store one of $$$3$$$ states for each pancake: unused, visible, or hidden. The visible pancakes are always stacked in decreasing order of radius, and the position in the stack of hidden pancakes, as argued above, does not affect the process. Thus, we can define a function $$$f$$$ recursively that takes a state description and returns the number of valid ways to finish a pancake stack from that state. Applying $$$f$$$ to the state in which all pancakes are visible gives the answer of the problem.
Let's define $$$f(s)$$$ recursively, where $$$s$$$ is a state. If no pancakes are unused in $$$s$$$, then the number of ways to finish it is simply $$$1$$$. This is our base case. If there are unused pancakes, we can go through all of them to choose which is the next pancake that should be cooked. If $$$s_i$$$ is the state that results from cooking the pancake of radius $$$i$$$ centimeters when the state was $$$s$$$, then $$$f(s) = \sum_i f(s_i)$$$ where the summation is over pancakes that are unused in $$$s$$$.
Since each pancake can independently be in one of $$$3$$$ states, the domain of $$$f$$$ has $$$3^{\mathbf{N}}$$$ overall states. The non-recursive cost of computing $$$f$$$ is a low-degree polynomial on $$$\mathbf{N}$$$. The exact degree depends on the implementation, but it is not too hard to do it in linear time, yielding an overall algorithm that runs in $$$O(3^{\mathbf{N}} \cdot \mathbf{N})$$$.
We can also use backtracking to solve the problem. We start building the permutations one element at a time, checking that the $$$\mathbf{V_i}$$$s for this partitial permutation match the ones needed for this test case. It can be proven that the complexity of such a solution is bounded by $$$O(2^\mathbf{N} \mathbf{N}^3)$$$, which is significantly better than $$$O(\mathbf{N}!)$$$ of the simplest brute force algorithm, and is enough to solve this test set.
Test Set 2
From the input, we can keep track of the current list of visible pancakes. To make things easier, when a pancake gets covered up in the stack, we will view this as the pancake being "removed" from the list of visible pancakes. We can create a list of inequalities relating the sizes of the pancakes. Let $$$P_i$$$ be the radius of the $$$i$$$-th pancake added.
First, it's worth noting that each time we add a pancake to the stack, the size of the list of visible pancakes will either increase by $$$1$$$, stay the same, or decrease. If the size of the list ever increases by more than one, then this case is impossible so our answer is $$$0$$$.
Let's consider the possible scenarios when we are adding the $$$i$$$-th When the size of the list increases by $$$1$$$ ($$$\mathbf{V_i} = \mathbf{V_{i-1}} + 1$$$), we know that the new pancake is smaller than all of the pancakes in our list. We can add the inequality $$$P_x \gt P_i$$$ where $$$x$$$ is the pancake that was previously at the end of the list.
If the size of the list stays the same or decreases ($$$\mathbf{V_i} \le \mathbf{V_{i-1}}$$$), then we know that the new pancake is larger than the last $$$\mathbf{V_i} - \mathbf{V_{i-1}} + 1$$$ pancakes on the list and each of these pancakes gets removed from our list. We can add the inequality $$$P_i \gt P_x$$$ where $$$x$$$ is the last pancake we removed from the list. Also, if $$$\mathbf{V_i} \gt 1$$$, then the new pancake is strictly smaller than the rest of the pancakes in the list. In this case, we can add the inequality $$$P_y \gt P_i$$$ where $$$y$$$ is the first pancake we did not "remove".
Note that in the latter case, we would already have added an inequality saying that $$$P_y \gt P_x$$$. But, this inequality is redundant now that we have the extra inequalities $$$P_y \gt P_i$$$ and $$$P_i \gt P_x$$$. Therefore, we can remove the inequality $$$P_y \gt P_x$$$ to prevent us from having any redundant inequalities that can cause us issues later.
After removing the redundant edges, each pancake is on the right side of at most one inequality in the form of $$$A \gt B$$$. Because of this, the inequalities can be modeled as a tree where we have an edge from $$$A$$$ to $$$B$$$ if $$$A \gt B$$$. We can then solve for the number of valid cooking orders of $$$\mathbf{N}$$$ pancakes recursively starting at the root of the tree which is the largest pancake. Note: the largest pancake is whichever pancake was at the beginning of our list at the end.
Let $$$s(i)$$$ be the number of pancakes in the subtree rooted at $$$i$$$. Also, let $$$f(i)$$$ be equal to the number of valid permutations of the pancake sizes (ranging from $$$1$$$ to $$$s(i)$$$) in the subtree starting at $$$i$$$.
To solve for $$$f(i)$$$ we need to count the number of ways we can assign pancake sizes to the subtrees belonging to our direct children. Then, each child subtree can permute itself in $$$f(j)$$$ ways (where $$$j$$$ is a direct child of $$$i$$$). So, $$$f(i)$$$ is the product of all $$$f(j)$$$'s and the number of ways we can assign pancake sizes to our subtrees.
Since $$$i$$$ is the largest pancake in our subtree, it must be given the largest size. The other $$$s(i) - 1$$$ pancake sizes for our subtree can be assigned to any subtree. The number of ways to do this can be counted using Multinomial Coefficients.
If we precompute the factorials and inverse factorials (to allow for division under mod), we can count the number of valid cooking orders in $$$O(\mathbf{N})$$$. Building the tree of inequalities also can be done in linear time. This gives us a final time complexity of $$$O(\mathbf{N})$$$ (assuming we precompute factorials and inverse factorials in linear time).
An alternate solution
There is a different solution to the problem that requires two observations: (1) the largest pancake (the one with a radius of $$$\mathbf{N}$$$ cm) can only be placed at position $$$k$$$, where $$$k$$$ is the largest integer such that $$$\mathbf{V_k} = 1$$$ and (2) since the pancake with a radius of $$$\mathbf{N}$$$ covers all other pancakes, the order of the pancakes before the largest pancake does not impact the $$$\mathbf{V_i}$$$s for the pancakes after the largest pancake. This allows us to split the problem into two independent parts. We solve the left part and the right part separately. For the right part, the largest pancake will always be visible, so we subtract $$$1$$$ from all $$$\mathbf{V_i}$$$ in the right part to account for it (note we do not actually do the subtraction, because that would be too slow, but we just implicitly do it). We must also choose which pancakes were in the left and right parts (there are $$$\binom{\mathbf{N}-1}{k-1}$$$ ways of doing this where the largest pancake was at index $$$k$$$). As base cases: If the range is empty, then there is $$$1$$$ valid ordering, and if there is no $$$\mathbf{V_i} = 1$$$, then there are $$$0$$$ valid orderings. Otherwise, the product of the left part's answer, the right part's answer, and the binomial coefficient is the total number of orderings.
Analysis — D. Retiling
The first simple observation we need to solve this problem is that we never swap two tiles that are showing the same color.
The main not-that-simple observation is that any given tile should either be flipped or swapped (or neither), but never both, regardless of costs. This can be proved by considering all operations that affect tile $$$a$$$: if there is a swap of $$$a$$$ and $$$b$$$ followed by a flip of $$$a$$$ or vice versa, the same effect can be achieved for less cost by simply flipping $$$b$$$ (which may have moved by its own swaps in between).
A small addition to the above is that we never want to flip the same tile more than once. Since each tile is only affected by one type of operation, we can assume that all swaps happen before all flips. Thus, after all swaps are done, the flips are fixed: any tile that has a different color than the target state must be flipped, and the other tiles must not.
Test Set 1
In Test Set 1, we can make the additional observation that no tile is to be swapped twice. Since we should not swap tiles when they are showing the same color, swapping $$$a$$$ and $$$b$$$ and then $$$b$$$ and $$$c$$$ is equivalent to flipping $$$a$$$ and $$$c$$$, which costs the same. Because we swap each tile only once, we must only swap two tiles if the swap fixes both of their colors (the samples already hint at this fact). Since swaps fix colors for two tiles and flips for one tile, we want to do as many swaps as we can within this restrictions, and then flip the rest.
At this point, the problem becomes a classic one: some cells of the matrix need to be changed, and we want to match as many of those as possible with an adjacent cell that also needs to be changed, but to the other color. Since the graph of cells and adjacencies is bipartite, this can be solved with a maximum matching algorithm on a bipartite graph. The solution is then the number of cells that need to change minus the size of such a maximum matching.
Test Set 2
As the additional sample shows, in Test Set 2 it is very possible that we need to swap the same tile multiple times. Luckily, we can generalize the solution explained for Test Set 1 for this scenario.
When a tile participates in multiple swaps, it effectively executes a swap with another
tile that is not necessarily adjacent.
While the other tiles are displaced by these operations, they are all of the same color,
so that displacement has no effect. To put it in a different way, we can look at a swap as moving
an M to an adjacent cell, and consecutive swaps are just consecutive moves.
Assume without loss of generality that the number of Ms increases between the
starting state and the target state (otherwise, use Gs instead).
Since we said we do all swaps first, that means that we move some of the Ms
that need to switch to Gs to positions that have Gs that need to be
Ms. We can do that by matching those two types of cell (regardless of adjacency).
Any unmatched G into M position needs to be flipped (the number of these
is fixed by the input).
For each matched pair, the cost of fixing both positions is either the minimum orthogonal distance between the two positions multiplied by $$$\mathbf{S}$$$ or $$$2 \mathbf{F}$$$, since we can also do two flips.
The reasoning above basically built a weighted bipartite matching between cells that start
at M and need to be turned into G and cells that start at G
and need to be turned into M. The total cost is the cost of the maximum matching
of minimum weight plus $$$\mathbf{F}$$$ times the number of unmatched cells. We can apply any
minimum cost maximum matching algorithm for bipartite graphs like the
Hungarian algorithm.