Funny or Scary?
Contest: European Championship 2024 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2600
Tags: constructive algorithms

You are designing a new video game. It has $$$n$$$ scenarios, which the player may play in any order, but each scenario must be played exactly once. When a player switches from a scenario to another scenario, the game shows a specially crafted transition video to make it all feel part of one big story. This video is specific to a pair of scenarios, but not to their order, in other words, the video playing when switching from scenario $$$a$$$ to scenario $$$b$$$ is the same as the video playing when switching from scenario $$$b$$$ to scenario $$$a$$$. Therefore, you need to create $$$\frac{n(n-1)}{2}$$$ different transition videos, one for each possible pair of different scenarios.

Each transition video can be either funny or scary. It is boring to see too many funny videos or too many scary videos in a row. Therefore, your goal is to create the videos in such a way that no matter in which order does the player approach the scenarios, they will never see more than $$$\lceil \frac{3n}{4} \rceil$$$ transition videos of the same type in a row.

You have already come up with ideas for at most $$$\lfloor \frac{n}{2} \rfloor$$$ of the transition videos, and therefore already know if those will be funny or scary. Now you need to choose funny or scary for all other transition videos in such a way that the above requirement is satisfied.

Input format:
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 24$$$) — the number of scenarios in the game.

The next $$$n$$$ lines describe the partial transition video plan. Each of those lines contains $$$n$$$ characters. The $$$j$$$-th character of the $$$i$$$-th line corresponds to the transition video between the $$$i$$$-th and the $$$j$$$-th scenarios. It will be F if the corresponding transition video will be funny, S if the corresponding transition video will be scary, ? if the corresponding transition video is still undecided, or . if $$$i=j$$$.

It is guaranteed that the $$$i$$$-th character of the $$$j$$$-th line and the $$$j$$$-th character of the $$$i$$$-th line will be the same for all $$$i$$$ and $$$j$$$. It is guaranteed that at most $$$\lfloor \frac{n}{2} \rfloor$$$ ($$$n$$$ divided by 2, rounded down) transition videos will already be decided, in other words, that at most $$$2\lfloor \frac{n}{2} \rfloor$$$ characters in the input will be F or S.

Output format:
Print $$$n$$$ lines describing the full transition video plan in the same format as the input. Each of those lines must contain $$$n$$$ characters. The $$$j$$$-th character of the $$$i$$$-th line must be F if the corresponding transition video is funny, S if the corresponding transition video is scary, or . if $$$i=j$$$.

Each ? character from the input must be replaced with either F or S, and all other characters from the input must remain unchanged. It must still hold that the $$$i$$$-th character of the $$$j$$$-th line and the $$$j$$$-th character of the $$$i$$$-th line are the same for all $$$i$$$ and $$$j$$$.

For each permutation of the $$$n$$$ scenarios, it must hold that the transition videos corresponding to playing the scenarios in this order do not have more than $$$\lceil \frac{3n}{4} \rceil$$$ ($$$3n$$$ divided by 4, rounded up) videos of the same type consecutively.

If there are multiple solutions, print any of them. It can be proven that for all inputs satisfying the constraints of this problem a solution always exists.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample: We are allowed $$$\lceil \frac{3\cdot 5}{4} \rceil=4$$$ transition videos of the same type in a row, but for any permutation of the 5 scenarios the player will see only 4 transition videos in total, therefore we can choose funny or scary freely. We must still respect the already chosen types.

In the second sample: One of the 479001600 possible permutations of scenarios is 1, 7, 4, 12, 9, 8, 2, 6, 10, 3, 11, 5. The player will get the following sequence of transition videos for this permutation: SSSSSSSSSFS. Even though this sequence has 10 scary transition videos in total, it has only 9 scary transition videos in a row, which is the maximum allowed amount ($$$\lceil \frac{3\cdot 12}{4} \rceil=9$$$).

Example input:
5
.?F??
?.???
F?.S?
??S.?
????.

Example output:
.FFFF
F.FFF
FF.SF
FFS.F
FFFF.

Example input:
12
.???????????
?.??????????
??.?????????
???.????????
????.???????
?????.??????
??????.?????
???????.????
????????.???
?????????.??
??????????.?
???????????.

Example output:
.SSSFFSSSSFS
S.SFFSFSFFFS
SS.SFFFSSSFS
SFS.FFSSSSFS
FFFF.FFFFFSF
FSFFF.SFFSFF
SFFSFS.SSSFS
SSSSFFS.SSFS
SFSSFFSS.SFS
SFSSFSSSS.FS
FFFFSFFFFF.F
SSSSFFSSSSF.

Editorial:
In graph terms, this problem can be formulated as follows: you are given a complete undirected graph on $$$n$$$ vertices. Some of the edges of the graph are already colored with two colors. You need to color all remaining edges with two colors in such a way that the graph does not have long monochromatic simple paths.
First of all, what happens when no edges are already colored? It turns out this exact question is well-studied in mathematics, and the definitive answer was given 57 years ago in the following paper: L. Gerencsér, A. Gyárfás, On Ramsey-type problems, Ann. Univ. Sci. Budapest Eötvös Sect. Math. 10 (1967), pp. 167-170. They prove that for any such graph on $$$n$$$ vertices there always exists a monochromatic path with at least $$$\lfloor \frac{2n}{3} \rfloor$$$ edges, and provide an example of such a graph where the longest monochromatic path has exactly $$$\lfloor \frac{2n}{3} \rfloor$$$ edges.
What does their example look like? The key idea is to use a bipartite graph with unbalanced parts. More specifically, we split all vertices into two groups, the first one of size roughly $$$\frac{n}3$$$, and the second one of size roughly $$$\frac{2n}3$$$. We color the edges between the two groups red, and the edges within each group blue. Now each blue path will have to stay within one of the groups, and therefore will not be longer than $$$\frac{2n}3$$$. The red edges form a bipartite graph, so each red path will have to alternate groups, which means that it will have to go to the smaller group every second step, and since the smaller group has only $$$\frac{n}3$$$ vertices, the path also cannot be longer than $$$\frac{2n}3$$$.
Sadly, not everyone will have read this seminal paper from 1967, so how can one come up with this construction during the contest? Since every edge in the complete graph will have one of the two colors, at least one of the colors will be used by a lot of edges. So we need to come up with examples of graphs with lots of edges, but no long paths. Disconnected graphs are a natural way to achieve this, and then we can consider what edges the complement of a disconnected graph must have, and arrive at the above construction. One other thing one can do when stuck is experimentation: try generating random complete graphs colored with two colors until you find some examples with no long monochromatic paths, for example where there is no monochromatic path with $$$n-1$$$ edges, and then try to generalize their structure. In fact, the answer to the second sample was generated in exactly this fashion: we repeatedly tried to color each edge randomly and independenty until we got a graph with 12 vertices and no monochromatic path with 10 edges. It actually took a few hours to find just one such graph. Studying this answer could be another way to discover the above construction, as the funny edges do form an almost-bipartite structure with nodes 5 and 11 in one part, and the rest in the other part (for example row 5 of the matrix is $$$\texttt{FFFF.FFFFFSF}$$$).
We still need to deal with edges that are already colored, but we also still have some reserves: our paths do not exceed $$$\lfloor \frac{2n}{3} \rfloor$$$, while this problem allows paths up to $$$\lceil \frac{3n}{4} \rceil$$$.
How bad is a wrongly colored edge to the above construction? If an edge that is supposed to be red is actually blue, it is very bad: now the two blue groups are connected, and therefore it is easy to create a blue path through all vertices. However, if an edge that is supposed to be blue is actually red, it is not so bad: even when this edge is used in a red path, all "originally" red edges still have to have one of their endpoints in the smaller group, and therefore the number of originally red edges in a red path still does not exceed two times the size of the smaller group, so changing one blue edge to red increases the boundary on the red path length by at most 1.
We have the freedom to choose which vertex belongs to which group, so we need to use this freedom to make sure that all edges that are already blue connect vertices within one group, as even one incorrectly blue edge is bad. This means that we need to find the connected components using the preexisting blue edges, and then take some of those components to the bigger group and the rest to the smaller group.
The edges that are already colored red can each increase the boundary on the red path length by 1. If all $$$\lfloor \frac{n}{2} \rfloor$$$ already colored edges are red, this would increase the path length by $$$\lfloor \frac{n}{2} \rfloor$$$, which is a lot. However, we also have the freedom to decide which one out of funny and scary corresponds to red. Let us choose one that has fewer edges, and therefore the number of already colored red edges will not exceed $$$\lfloor \frac{n}{4} \rfloor$$$.
Because the length of the red path can be increased by $$$\lfloor \frac{n}{4} \rfloor$$$ through the already colored edges, we need to make the smaller group even smaller: since the red path must not exceed $$$\lceil \frac{3n}{4} \rceil$$$, we can have at most $$$\lfloor\frac{\lceil \frac{3n}{4} \rceil - \lfloor \frac{n}{4} \rfloor}{2}\rfloor$$$ vertices in the smaller group, which is roughly $$$\frac{n}{4}$$$, and more precisely it is $$$\ge \lfloor \frac{n}{4} \rfloor$$$.
If the smaller group has $$$\lfloor \frac{n}{4} \rfloor$$$ vertices, the bigger group has $$$n-\lfloor \frac{n}{4} \rfloor=\lceil \frac{3n}{4} \rceil$$$ vertices, which means that blue paths have at most $$$\lceil \frac{3n}{4} \rceil-1$$$ edges. Notice how all pieces of the puzzle come together now: this is good enough for this problem, but only barely, by 1 edge. So we can allow the smaller group to have either $$$\lfloor \frac{n}{4} \rfloor$$$ or $$$\lfloor \frac{n}{4} \rfloor - 1$$$ vertices.
The only remaining question is: since we add vertices to groups not one by one, but an entire preexisting blue edge component at a time, can we actually achieve the required size of the smaller group? It turns out that we can, using the following simple approach: sort the components in increasing order of size, and take them in this order to the smaller group until the size of the smaller group is $$$\lfloor \frac{n}{4} \rfloor - 1$$$ or $$$\lfloor \frac{n}{4} \rfloor$$$.
The only way this could fail is if we jump from at most $$$\lfloor \frac{n}{4} \rfloor - 2$$$ to at least $$$\lfloor \frac{n}{4} \rfloor + 1$$$, meaning that the component we have added has at least 3 vertices. But since we add components in increasing order of size, it means that the remaining components also all have at least 3 vertices, which means that components with at least 3 vertices cover at least $$$n-(\lfloor \frac{n}{4} \rfloor - 2)=\lceil \frac{3n}{4} \rceil+2$$$ vertices of the graph. Since we need 2 edges for a component with 3 vertices, and with bigger components we still need at least $$$\frac{2k}{3}$$$ edges for a component with $$$k$$$ vertices, we need at least $$$\frac{2(\lceil \frac{3n}{4} \rceil+2)}{3}$$$ edges to get into this situation, and $$$\frac{2(\lceil \frac{3n}{4} \rceil+2)}{3} \ge \frac{\frac{3n}{2}+4}{3} > \frac{\frac{3n}{2}}{3} = \frac{n}{2}$$$. So we need more than $$$\frac{n}{2}$$$ edges to get into this situation, which is impossible under the constraints of the problem, therefore the greedy approach of taking already blue components in increasing order of size always works.
The solution is complete now, and it runs in time linear in the input size, in other words $$$O(n^2)$$$. Why does the problem have the very low limit of $$$n \le 24$$$ in this case? The reason is that we also need to implement the checker that will read your output and check if there are no long monochromatic paths. For that we use a relatively standard dynamic programming approach that runs in $$$O(n^2\cdot 2^n)$$$, sped up using bitmasks to do only $$$O(n\cdot 2^n)$$$ operations with integers. It takes a few seconds for $$$n=24$$$ so we could not go much higher. We have explored using various heuristic approaches to find the longest monochromatic paths for larger values of $$$n$$$, but it turns out that even though those heuristic approaches work quite well on random graphs, they actually cannot find the longest path reliably in the type of graph output by the solution above, namely an unbalanced bipartite graph with a few additional edges.
The low value of $$$n$$$ allows to simplify the implementation of the above solution in the following manner: we can skip finding connected components of preexisting blue edges, instead just iterating over all $$$2^n$$$ subsets of vertices as candidates for the smaller group, and then checking if the size of the smaller group is appropriate and that there are no preexisting blue edges going from the smaller group to its complement.