The official editorial for E given here: https://codeforces.net/blog/entry/92739 has much less detail than the Chinese editorial ( https://www.cnblogs.com/invisible-eyes/p/15003033.html ). Can anyone graciously translate the Chinese editorial E solution into english?
(Or provide an English solution?). I could not find an understandable proof for E in the comments section of the editorial's blog post.
Thanks in advance.
I think google automatically translates chinese to english, doesn't it?
I've already tried that, and it wasn't that clear to understand.
I will talk about why the answer is $$$2^{choices}$$$, other parts were already discussed.
Let's add an edge between every pair of rows which share a common position. Call the resulting graph $$$G$$$. Then edges can be partitioned into $$$n$$$ disjoint perfect matchings. Also we assume graph is connected otherwise we take the product of connected components.
Answer is the number of maximum independent sets. Turns out there are only two of them.
Size of MIS is equal to $$$|G| / 2$$$ because it's guaranteed that Latin square exists. Denote the set of rows of a Latin square as $$$L$$$. Every edge must connect rows from $$$L$$$ and $$$G \setminus L$$$ otherwise it can't be a part of any perfect matching. $$$L$$$ and $$$G \setminus L$$$ make a bipartition of graph hence they are unique (easier proof, thanks to askd).
EDIT: now irrelevant
In the end we get smth like:
A\C <-> B\C
C <-> D
There must be a perfect matching which connects upper and lower parts. Because A and B are independent there's at least one edge connecting A\C and D (or B\C doesn't matter). But such perfect matching can't exist, one vertex from C will remain unmatched in any case.
Thank you for writing that explanation!
I'm too lazy to figure out the last paragraph, but I think I've found a possibly simpler proof that there are exactly two MIS's.
Suppose that there exists some Latin square $$$L \subset G$$$. Let $$$R = G \setminus L$$$. We've proven that $$$R$$$ must also be a valid Latin square.
Edit: way better proof: $$$L$$$ and $$$R$$$ obviously have to be the partite components of $$$G$$$ lol, otherwise there will either be two things in $$$L$$$ which are connected by an edge, or two things in $$$R$$$ which are connected by an edge.
Now consider some arbitrary spanning tree of $$$G$$$, let's root it arbitrarily at $$$x$$$. WLOG, suppose that $$$x \in L$$$. Now it must be true that all descendants of $$$x$$$ (all nodes at depth 1) are contained in $$$R$$$, otherwise $$$L$$$ wouldn't be an independent set. Similarly, all nodes at depth 2 must be contained in $$$L$$$, and so on.
In each case (either $$$x$$$ is in $$$L$$$ or $$$x$$$ is in $$$R$$$), both sets can be uniquely determined, hence there are only two solutions.
It's worth noting that this still doesn't prove the editorial solution I think (idk if I even understand it correctly)? But this does lead to a provable solution, since the partite sets of $$$G$$$ can be found.
Yeah, proof is overcomplicated but it works for any MIS size (EDIT: actually I'm wrong lol, |C| and |D| may be not equal). If you set MIS = $$$|G| / 2$$$ then it should be much easier. I can't quite understand your reasoning for $$$L$$$ and $$$R$$$ being the only MIS. There can be a lot of MIS in a tree.
Well, if you choose random row then you fix the IS in some connected component, that should prove author's solution from the editorial.
It's true that there can be many MIS's in a tree, but we can pick some arbitrary Latin square $$$L$$$ and it must be true that $$$R = G \setminus L$$$ is also a Latin square.
The condition on $$$L$$$ and $$$R$$$ is special, in that $$$L \cup R = G$$$ and both $$$L$$$ and $$$R$$$ are MIS's. As you proved, there cannot be any edge connecting two vertices in either $$$L$$$ or $$$R$$$. So by definition, $$$L$$$ and $$$R$$$ must form a bipartition on $$$G$$$, which for a connected graph we know there are only two of.
So this shows that to begin with, there were only two possible $$$L$$$.
And maybe I don't understand the author's solution, but I thought it just said "eliminate all invalid stuff, and then pick another random row"?
Take graph 1-2, 2-3, 3-4. $$$L$$$ = (1, 3), $$$R$$$ = (2, 4) but you can also choose (1, 4). Edges = union of perfect matchings is a necessary condition you can't just omit it.
Bipartitions have nothing to do with the Latin squares.
I don't think you understood my comment. $$$L$$$ can't be $$$(1, 4)$$$ because $$$G \setminus L = (2, 3)$$$ isn't a Latin square. You proved that for any Latin square $$$L$$$, $$$G \setminus L$$$ must also be a Latin square.
So this actually shows that that graph would be impossible to form.
(I also know that the Latin squares are the bipartitions because my submission got accepted lol)
Hahaha, got it, thx.
I meant to say that Latin squares has nothing to do with bipartitions because the problem statement forces it not the other way around.
I've posted a final proof below to summarize the conversation.
Auto comment: topic has been updated by kfqg (previous revision, new revision, compare).
I also noticed sometimes that there are lengthy editorials, but they are written in another language (usually in Japanese or Chinese).
It turns out google translate can translate some websites, see here for the details.
. (See below post instead.)
There's been a lot of discussion & revisions above, and I don't think that the disconnected G case has been fully discussed, so I thought I'd post a final proof here which summarizes the conversation.
Let's add an edge between every pair of rows which share a common position. Call the resulting graph $$$G$$$. Let's consider any component of $$$G$$$.
Let's prove the answer is $$$2^{#components in G}$$$.
Define Latin Rectangle as AxB array where no row & column has the same element twice. (A may be not equal to B).
Define Two-Latin Rectangle as (2A)xB array where no row has the same element twice, but every column has every element exactly twice (or zero times). (A may be not equal to B)
Let's look at any component C of G. C corresponds to a two-Latin rectangle. Suppose that L and R are two disjoint Latin Rectangles that C can be split into (How do we know it's possible to split C into two disjoint Latin rectangles? Well, we know from the problem statement that a Latin Square must exist. So let L be every row that was in the original Latin square. L is a Latin rectangle. Since C is a two-latin rectangle, R must also be a Latin rectangle.) Every edge in C must connect an element of L to an element of R. Therefore C is bipartite.
For any full nxn Latin Square (Here n refers to the full size of the final latin square; in other words, this is the same n as in the problem statement), we must pick |L| rows of C. (More is impossible, and if we pick less, we won't have enough rows for the full Latin square.)
So the question is how many ways are there to pick |L| rows of C. The answer is the number of MIS in C. Clearly L and R are two MIS. They must actually be the only two MIS. (Proof by contradiction: Suppose T is an MIS not equal to L or R. C \ T must also be an MIS since C is a two-latin square. T must have at least one vertex u in L. Let's look at the shortest path from u to any other vertex of T which is in R. The path must have length at least 3 (since C is bipartite, and since T is an MIS). So let the path be u --> a --> b --> v for example. This is impossible since a is connected to b, but a and b are in C \ T which must be an MIS.)
I definitely don't understand something. So based on the formula, the answer is at least two, because we always have at least one component? But it's not true, judging even from samples. I made a simple example, when the first 5 rows form a Latin square, but others 5 do not. Here we have one component in $$$G$$$, but the answer is 1. How do we get this exactly twice from the statement?
Or we look specifically for such components, and multiply by 2 only in this case?
Everything in my proof post should be applied after doing the preprocessing step mentioned in the editorial:
"Among all the arrays not be chosen, if an array have a number which appears exactly once at its column, that the array must belong to the n original arrays. So, we can choose the array and delete all arrays have at least one same bit with it.
If there not exists such an array described above, according to the Pigeonhole Principle, all numbers of the unchosen arrays must appear exactly twice on their columns."
In the example you posted, all rows are removed by the preprocessing, so $$$G$$$ is empty. (So G has 0 components, and the formula works since 2^0 is 1 which is the answer).