All the division 2 problems were created by Agnimandur. 1548E - Грегор и два маляра was created by Benq. I hope that this hint-based editorial helps you, no matter what your rating is! Solution code is provided in both C++, Java, and Kotlin when available.
Solution Code Repository
1549A - Грегор и криптография
Fix $$$a$$$ into a convenient constant.
Since $$$P \ge 5$$$ and is also a prime number, we know that $$$P-1$$$ is an even composite number. A even composite number is guaranteed to have at least 2 unique divisors greater than 1. Let two of these divisors be $$$a$$$ and $$$b$$$. It is guaranteed that $$$P\mod{a} = P\mod{b} = 1$$$, and thus this selection is valid.
For example, we can simply pick $$$a=2$$$ and $$$b=P-1$$$, and we will get a correct solution.
The time complexity is $$$\mathcal{O}(Q)$$$.
1549B - Грегор и игра в пешки
Solution 1
There a very limited number of squares where each of Gregor's pawns could end up.
Identify a greedy strategy to maximize the answer.
The key insight is that due to the fact that there is only one row of enemy pawns, and those pawns never move, there are only $$$3$$$ possible columns where one of Gregor's pawns can end up in.
We can solve this problem greedily, going from column $$$1$$$ to column $$$N$$$. At the current column $$$j$$$, if Gregor has a pawn in this column, then we greedily consider 3 cases.
- If there is an uncaptured enemy pawn in column $$$j-1$$$, mark that pawn as captured and increment the answer. Column $$$j-1$$$ will never be looked at again, so this decision is optimal.
- If there is no pawn in column $$$j$$$, just move Gregor's pawn forward, and increment the answer.
- If there is an uncaptured enemy pawn in column $$$j+1$$$, mark that pawn as captured and increment the answer.
- Otherwise, this pawn will not reach the first row.
This greedy solution is guaranteed to produce the maximum possible answer.
The time complexity is $$$\mathcal{O}(N)$$$.
Solution 2
Write the problem as a graph problem.
Valid captures or valid forward moves represent edges in the graph.
We have two sets: Gregor's pawns, and destination squares. We also have some edges between these two sets.
Maximum Matching.
Each of Gregor's pawns can end up in one of 3 possible squares. If Gregor has a pawn in column $$$i$$$, it can end up in column $$$i-1$$$ or $$$i+1$$$ if there is an enemy pawn in those columns. Furthermore, it can remain in column $$$i$$$ if there is no enemy pawn in that column.
Let's build a graph $$$G$$$, where each edge connects one of Gregor's pawns to a valid destination cell. Since every edge goes from a cell in the bottom row to a cell in the top row, $$$G$$$ is clearly bipartite. It's now clear that moving as many pawns to the end is equivalent to finding a maximum matching in $$$G$$$.
The time complexity is $$$\mathcal{O}(N\sqrt{N})$$$ using the HKK algorithm for maximum matching. ($$$G$$$ has at most $$$2N$$$ vertices, and $$$6N$$$ edges)
1549C - Паутина лжи
For various graphs, try and simulate the process. Determine a rule to figure out whether a noble survives or not.
When you add or remove a single edge, how much can the answer change by? Try and recalculate the answer in $$$\mathcal{O}(1)$$$.
Due to the queries, actually simulating the process each time will be too expensive.
Proof that the Process will End: Assume after round $$$x$$$, $$$x_i$$$ nobles are killed. If $$$x_i=0$$$, then the state of the graph doesn't change, so the process will have ended. If $$$x_i > 0$$$, then the number of nobles decreases. Thus, the maximum number of rounds the process can last is $$$N$$$, so it must end.
$$$\textbf{Lemma 1:}$$$ At the end of the process, no two nobles will still be friends.
Proof by Contradiction: Assume that nobles $$$u$$$ and $$$v$$$ (assume WLOG that $$$u < v$$$) are still friends and the process is over. In order for $$$u$$$ to avoid being killed, there must be a noble $$$w$$$ weaker than $$$u$$$ that is also a friend of $$$u$$$. The same logic then applies to $$$w$$$, and we have an infinite descent argument. There are only a finite number of nobles weaker than $$$u$$$, so there will be a contradiction.
$$$\textbf{Lemma 2:}$$$ If all of a noble's friends are weaker than it, that noble cannot be killed.
Direct Proof: Since none of the noble's friends are stronger than it, it is impossible for $$$\textit{all}$$$ of them to be stronger at any point in the process.
$$$\textbf{Final Idea:}$$$ By combining Lemmas 1 and 2, we can prove that if ALL of a noble's friends are weaker than it, that noble survives, otherwise it will die. This leads to the solution.
Maintain in an array the number of nobles weaker than noble $$$i$$$. Since the updates guarantee that the edge being removed/added does/doesn't exist respectively, we only need to keep track of the number of edges of each noble. Essentially, a noble survives if and only if weaker[i]==edges[i]
. After linear precomputation, updates and queries take constant time.
The time complexity is $$$\mathcal{O}(N+M+Q)$$$.
1549D - У чисел есть друзья
Let's say the subarray $$$A_i \dots A_j$$$ is all congruent to $$$n\mod{m}$$$. What does that imply about the subarray?
What does the previous hint imply about the difference array generated by $$$D[i]=A[i+1]-A[i]$$$?
GCD
The key observation is to construct the difference array $$$D$$$ of size $$$N-1$$$, where $$$D[i]=abs(A[i+1]-A[i])$$$. If a given subarray is a friend group, then every difference is a multiple of some $$$m$$$. Since every element of $$$A$$$ is distinct, the case when $$$D[i]=0$$$ can be ignored.
We can now convert this into a GCD (greatest common divisor) problem. It follows that $$$A[i\dots j]$$$ is a friend group if and only if $$$\gcd{(D[i\dots j-1])} > 1$$$. Indeed, the value $$$m$$$ that we want is equal to this GCD.
To solve the problem, we can use a sparse table or a segment tree to find the largest possible subarray beginning at $$$i$$$, and then max over all subarray answers to get the final answer.
The time complexity is $$$\mathcal{O}(N\log{N}\log{10^{18}})$$$. The first log is for the sparse table, the second is for computing GCDs.
Note that the de facto time complexity may be closer to $$$\mathcal{O}(N\log{N}+N\log{10^{18}})$$$, due to the insights from this blog post.
1549E - Три поросенка
Solution 1
Convert the word problem into a combinatorics equation.
Write the equation for some $$$x$$$. Write the equation for $$$x+1$$$. How can we easily transition from the first to the second equation?
For a given $$$x$$$, we want to calculate every third term in the sequence $$$\binom{i}{x}$$$ for $$$i \in [1,3N]$$$. Think about how computing the entire summation $$$\sum_{i=1}^{3N}{\binom{i}{x}}$$$ will help.
For a given $$$x$$$, we want to compute $$$\sum_{i=1}^{N}{\binom{3i}{x}}$$$, which can be solved with a combinatorial dynamic programming.
Define the array dp[x][m]
(dimensions: $$$N+1\times 3$$$), which computes the sum $$$\sum_{i=0}^{N-1}{\binom{3i+m}{x}}$$$. Under this definition, $$$ans[x]=dp[x][0]+\binom{3N}{x}$$$, where ans
is what we want to find.
Under the definition of the dp, we can make the following mathematical observations.
$$$dp[x][0]+dp[x][1]+dp[x][2]=\sum_{i=0}^{3N-1}{\binom{i}{x}}$$$, since term $$$i$$$ belongs to the array with $$$m=i\mod{3}$$$. This summation can be condensed with the Hockey Stick Identity into $$$\binom{3N}{x+1}$$$.
By repeated uses of Pascal's Identity, we get equations (2) and (3), giving us a system of 3 equations with 3 new unknowns, which can easily be solved.
- $$$\sum_{m=0}^{2}{dp[x][m]}=\binom{3N}{x+1}$$$.
- $$$dp[x][1] = dp[x][0]+dp[x-1][0]$$$
- $$$dp[x][2] = dp[x][1]+dp[x-1][1]$$$
The base case is that $$$dp[0][0]=dp[0][1]=dp[0][2]=N$$$. Each query can now be answered trivially.
The time complexity is $$$\mathcal{O}(N+Q)$$$ with combinatorial precomputation.
Solution 2
Convert the word problem into a combinatorics equation.
How will the Binomial Theorem be helpful?
Try and construct a polynomial $$$P(k)$$$ such as the coefficient $$$k^x$$$ in that polynomial represents the number of attack plans if the wolf wants to eat $$$x$$$ pigs.
Notice that $$$P(k)$$$ is a geometric series, so FFT is unnecessary.
Define the polynomial $$$P(k)=(1+k)^3+(1+k)^6+\cdot + (1+k)^{3N}$$$.
The coefficient of $$$k^x$$$ in $$$P(k)$$$ is, by the Binomial theorem on each term of the polynomial, equal to $$$\binom{3}{x}+\binom{6}{x}+\dots + \binom{3N}{x}$$$. This is equal to ans[x]
from the previous solution.
The only thing left to do is quickly calculate $$$P(k)$$$. Due to the tight time limit, calculating the polynomial using FFT in $$$\mathcal{O}{(N\log{N})}$$$ is probably too slow.
Instead, we notice that $$$P(k)$$$ is a geometric series. Using the geometric series formula, we get that $$$P(k)=\frac{(1+k)^{3N+3}-(1+k)^3}{(1+k)^3-1}$$$.
The numerator and denominator of this fraction can be expanded in linear time. Then all we have to do is a polynomial long division. Once we have $$$P(k)$$$, we can answer all the queries trivially.
The time complexity is $$$\mathcal{O}(N)$$$ with combinatorial precomputation.
1549F1 - Грегор и нечетные коровы (простая версия)
"Enclosed cows" are just interior points. It's clear that Pick's Theorem will be useful.
Manipulate Pick's Theorem into a modular equation.
The number of boundary points between $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$\gcd{(x_1-x_2,y_1-y_2)}$$$.
Working with relevant formulas, find a simple condition between two points, such that they can be treated as equivalent.
Every set of 3 fenceposts forms a lattice triangle We want to find the number of such lattice triangles that have an odd number of interior points. Since all the coordinates are even, the area is automatically even as well. By Pick's Theorem, $$$area=I+\frac{B}{2}-1$$$, so $$$2\cdot area=2I+B-2$$$. $$$I$$$ is the number of interior points, and $$$B$$$ is the number of boundary points, for an arbitrary triangle formed by 3 fenceposts.
Let $$$A=2\cdot area$$$, so $$$A=2I+B-2$$$. Since $$$I$$$ is odd, taking both sides modulo 4 we get that $$$A \equiv B\mod{4}$$$. Since the area is an even integer, $$$A$$$ is a multiple of 4, so we get that $$$A\equiv B\equiv 0\mod{4}$$$.
Let's define the $$$\textbf{boundary count}$$$ of a segment to be the number of lattice points on it, minus 1. It can be proven that the boundary count of the segment connecting $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ is $$$\gcd{(|x_2-x_1|,|y_2-y_1|)}$$$.
In this problem, we only care about what the boundary count is modulo 4. Since all the coordinates are even, the GCD is guaranteed to be even, so the boundary count is either 0 or 2 mod 4. For the segment connecting $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ call its boundary count $$$b$$$.
- $$$b\equiv 0\mod{4}$$$ IFF $$$x_1\equiv x_2 \mod{4}$$$ AND $$$y_1\equiv y_2 \mod{4}$$$.
- $$$b\equiv 2\mod{4}$$$ in all other situations.
$$$\textbf{Key Idea:}$$$ Turn fence post $$$(x,y)$$$ into $$$(x\mod{4},y\mod{4})$$$.
Writing the area of a triangle via the shoelace formula, it becomes obvious that the area mod 4 won't change when the coordinates are modded by 4. Additionally, by our work above, $$$B$$$ (the sum of the boundary counts for the 3 sides of the triangle) is entirely dependent on the coordinates mod 4.
Let cnt[x][y]
be an array counting the number of points that fall into each category based on the key idea above. Since all coordinates are even, only 4 elements in the $$$cnt$$$ array will be nonzero. We can fix each point of the triangle into one of the categories, quickly calculuate $$$A$$$ and $$$B$$$, and solve the problem. Be careful not to overcount triangles.
The time complexity is $$$\mathcal{O}(N)$$$, with a small constant for the counting.
1549F2 - Грегор и нечетные коровы (сложная версия)
Solve the easy version of the problem.
Taking each coordinate modulo 4 no longer works. This is because if $$$\Delta{x}$$$ or $$$\Delta{y}$$$ are odd, there's no way to predict whether the boundary count (see editorial of the easy version) is 1 or 3 mod 4.
By playing with Pick's Theorem, you should find that $$$B$$$ (the total number of boundary points) has to be even. Let $$$b_1$$$, $$$b_2$$$, and $$$b_3$$$ be the boundary count of the three sides of a lattice triangle.
Lets count the answer. Fix a point. Fix the boundary count mod 4 of the two sides adjacent to that point. Fix more things.
In Hint 4, we fixed a point. It's critical that you fix the boundary count of the side opposite that point to be even.
First read (and understand!) the editorial for the easy version of the problem.
- Definition: The $$$\textbf{modularity}$$$ of a point
(x,y)
is(x%4,y%4)
. - Definition: The $$$\textbf{boundary count}$$$ of a segment is the number of lattice points on that segment, minus 1.
Lets precompute the array cnt[i][x][y][b]
(dimensions $$$N\times 4\times 4\times 4$$$), which equals the number of other points respective to points[i]
with modularity $$$(x,y)$$$ and with a boundary count mod 4 equal to $$$b$$$. This precomputation can be done in $$$\mathcal{O}(N^2 \log{10^7})$$$ time, by iterating over every pair of points. The boundary count of the segment $$$(x_1,y_1)$$$ to $$$(x_2,y_2)$$$ is $$$\gcd{(|x_2-x_1|,|y_2-y_1|)}$$$.
Consider the number of boundary points on the three sides of a triangle, and call them $$$b_1,b_2,b_3$$$. Clearly, $$$B=b_1+b_2+b_3$$$. The key idea is that since $$$B$$$ is even, wlog we can assume that $$$b_3$$$ is even, and that $$$b_1 \equiv b_2 \mod{2}$$$. The other key idea is that it is easy to figure out if the boundary count is congruent to 0 or 2 mod 4 based on the modularities of the coordinates alone, but it's impossible if the boundary count is odd.
Let's fix a point, and count the number of triangles that involve this point. Let's also iterate over all the relevant modularities of the other two points in the triangle, which range from $$$(0,0)$$$ up to $$$(3,3)$$$. Let's also make sure that there are an even number of boundary points on the side opposite the fixed point, which we know almost nothing about. It can be shown that $$$b_3 \equiv 0\mod{4}$$$ IFF $$$(x_1,y_1)=(x_2,y_2)$$$, and that $$$b_3 \equiv 2\mod{4}$$$ IFF $$$x_1,x_2$$$ have the same parity, and $$$y_1,y_2$$$ have the same parity, and the previous case doesn't apply. Finally, make sure that the parity of the boundary count of the two sides next to the fixed point are the same.
Using the precomputed array $$$cnt$$$ and the formula for $$$b_3$$$, we can quickly find $$$B$$$ in this case. Using the Shoelace Formula, we can quickly find what $$$A$$$ is modulo 4. If $$$A$$$ is even and equal to $$$B$$$, then we know that $$$I$$$ must be odd (in the easy version of the problem, we found that $$$A \equiv B \mod{4}$$$ IFF $$$I$$$ is odd), so all triangles in this class are interesting. Thus, we add to the answer a number roughly equal to $$$cnt[i][x_1][y_1][b_1]\cdot cnt[i][x_2][y_2][b_2]$$$ (it could be lower due to the potential overcount, if two points fall into the same bucket of the array).
Lastly, be sure not to overcount triangles! In my code, I count each of the EEE
triangles ($$$b_1,b_2,b_3$$$ all even) 3 times, and the OOE
triangles once.
The time complexity is $$$\mathcal{O}(N^2 \log{10^7})$$$ (the main part of the solution is approximately $$$\mathcal{O}(512N)$$$).
Implementation Note: The bottleneck of the algorithm is computing the GCDs. The simplest optimization that is sufficient for AC is to only calculate $$$\frac{N^2}{2}$$$ GCDs instead of all $$$N^2$$$ (since the GCD is commutative). Java requires additional optimizations, such as precomputing small GCDs.
1548E - Грегор и два маляра
Let's give each component a "representative" cell. Then our task is now to count the number of representatives.
Let the cell with the smallest amount of paint in a component be the representative. How can we find if a given cell $$$(i,j)$$$ is a representative or not?
This editorial was written by Benq, and inspired by 1392I - Кевин и сетка.
For simplicity let's assume that all $$$a_i$$$ are distinct (and similarly, all $$$b_j$$$). If this is not the case, we may break ties arbitrarily.
Say that two badly painted cells are directly reachable from each other if they are in the same row or column and all cells in between them are also badly painted. Also, define the value of the cell at $$$(i,j)$$$ to be $$$a_i+b_j$$$. Call a badly painted cell a $$$\textbf{representative}$$$ if no cell directly reachable from it has a smaller value than it.
$$$\textbf{Claim:}$$$ Every connected component of badly painted cells contains exactly one representative.
$$$\textbf{Proof:}$$$ Clearly every connected component contains at least one representative; consider the cell(s) with the minimum value contained within it. To show that every connected component contains \textit{exactly} one representative, suppose that we are given a representative $$$(i,j)$$$ that is directly reachable from $$$(i',j)$$$ for all $$$i_l\le i'\le i_r$$$ and $$$(i,j')$$$ for all $$$j_l\le j'\le j_r$$$, where $$$a_i=\min_{i_l\le i'\le i_r}(a_{i'})$$$ and $$$b_j=\min_{j_l\le j'\le j_r}(b_{j'})$$$. Then the connected component containing $$$(i,j)$$$ is completely contained within the rectangle $$$[i_l,i_r]\times [j_l,j_r]$$$, and $$$(i,j)$$$ is the unique cell with the minimum value within that rectangle. This implies that a representative is always the unique cell with the minimum value within its connected component.
It remains to count the number of representatives. For each $$$i$$$, let $$$lo_i$$$ be the maximum index less than $$$hi_i$$$ such that $$$a_{lo_i}<a_i$$$ and $$$hi_i$$$ be the minimum index greater than $$$i$$$ such that $$$a_{hi_i}<a_i$$$. Then define $$$na_i$$$ to be $$$\min(\max_{i'\in [lo_i,i]}a_{i'},\max_{i'\in [i,hi_i]}a_{i'})$$$. Any path from a cell in row $$$i$$$ to a cell in the same column with lower value must pass through a row with value at least $$$na_i$$$. Define $$$nb_j$$$ for each $$$j$$$ similarly. It can be shown that $$$(i,j)$$$ is a representative if and only if the following conditions hold:
- $$$a_i+b_j\le X$$$
- $$$na_i+b_j>X$$$
- $$$a_i+nb_j>X$$$
Computing $$$na$$$ and $$$nb$$$ can be done in $$$\mathcal{O}(N\log N+M\log M)$$$ with any data structure supporting range min/max queries (e.g. sparse tables), or in $$$O(N+M)$$$ with a stack.
It remains to count the number of pairs $$$(i,j)$$$ that satisfy these conditions given $$$a$$$, $$$na$$$, $$$b$$$, and $$$nb$$$. First initialize two binary indexed trees $$$T_a$$$ and $$$T_b$$$. Then sort the pairs $$$(na_i-a_i,a_i),(nb_j-b_j,b_j)$$$ in decreasing order. Now for every pair in the order, if it is of the form $$$(na_i-a_i,a_i)$$$, then add to the answer the number of elements of $$$T_b$$$ that are in the range $$$(X-na_i,X-a_i]$$$, and add $$$a_i$$$ to $$$T_a$$$. The reasoning for the case $$$(nb_j-b_j,b_j)$$$ is similar (query $$$T_a$$$, update $$$T_b$$$).
The time complexity is $$$\mathcal{O}(N\log{N}+M\log{M})$$$ for sorting the pairs and working with the two BITs.
Sorry about having to create a new editorial!
The old one passed some character limit built into Codeforces. Whenever I attempted to edit the old one, I was re-directed to the bug page, and the edit was not saved!
Thus, the editorial went offline for a while. Ultimately, a new and shorter editorial, was the only viable solution.
Could you post the old editorial page without the edits? There were several helpful (at least for me) discussions about GCD and solution of 1549D - У чисел есть друзья without segment tree and sparse table.
Sorry, it's already been deleted.
Ask the questions again and I will respond! .
Can anyone please point out what's wrong with my code for 2D? 125022309 Getting Runtime error on test 3
The iterator j should iterate in log(n). You're iterating it till n, this is trying to access out of bound memory. Thus the error.
Thanks for pointing that out. It worked
You're welcome.
Can anyone please help me debug my solution for div 2 problem D. I am getting WA on test case 5.
Basically what I am doing is implementing binary search on the answer and if I find that lets say answer k is possible then I am searching for answer > k, and if answer k is not possible then I am searching for < k.
WA Solution
If my logic is wrong you are most welcome to correct it :)
UPDATE: Got it friends, there was a little problem in binary search implementation. AC Solution
Can you explain your check function?
So the param that I am passing to the function is the answer that I want to check whether it is possible or not. For this I am forming 2 arrays where array pre will store GCD of all the elements from index i to index j and suf will store GCD of all the elements from index j to i+m-1.
And if you analyze it you can see that
if(__gcd(suf[i], pre[i+m-1])!=1)return true;
this piece of code will return true if GCD of m elements starting from i is > 1. If it is true then we can say that our array b has at least one subarray of size m who's GCD>1.(The main motive behind forming pre and suf arrays is to find GCD of any subarray of length m in O(1) time)
I think something is wrong with your binary search implementation.
I can't understand how getting the value of p(k) can help in 1549E? How to expand it? What is polynomial long division? How to get the sum of coefficients of k^x? Also, a implementation with sufficient comment for this type of editorial would be good for Pupil like me.
thanks for the editorial
Solution for D div2 (B div1) without segment trees, sparse table:
After building the difference array $$$D$$$, for each $$$r$$$ we will maintain a list of uniques gcds that we can get if we start at position $$$r$$$ going backwards, i.e. all the possible values of $$$gcd_{l \dots r}=gcd(D_l, D_{l+1}, \dots, D_r)$$$ for all $$$1 \leq l \leq r$$$. Also for each value $$$g$$$ of this list we will also keep the maximum $$$length$$$ such that $$$gcd_{r-lenght+1 \dots r}=g$$$ so that we can update the answer for the problem. We can simulate all this process with a map.
Key observation: The size of the list at each iteration (that is, the number of unique gcds) is $$$O(\log MX)$$$, where $$$MX$$$ is the maximum value of $$$D_i$$$. That's because $$$gcd_{i \dots r}$$$ is a divisor of $$$gcd_{i + 1 \dots r}$$$ for each $$$1 \leq i < r$$$. So if $$$gcd_{i \dots r}$$$ is different from $$$gcd_{i + 1 \dots r}$$$, then $$$gcd_{i \dots r} \leq gcd_{i + 1 \dots r} / 2$$$.
Based on that, total complexity will be $$$O(n \cdot \log^2 MX)$$$ (the second $$$log$$$ is for the $$$gcd$$$ complexity). But maybe using the analysis of this blog (also cited in the editorial) the complexity can go down to $$$O(n \cdot \log MX + \log^2 MX)$$$ or $$$O(n \cdot \log MX \cdot \log \log MX + \log^2 MX)$$$ if you take into account the map complexity.
Link to my submission
I have another approach to get around the log factor from segtree / sparse table.
I used a two pointer approach to find the subarray and represented the elements with a queue that always knows the gcd of contained elements. The technique is better known as a min-queue but same applies for gcd. It can be implemented with linked lists or like I did with two stacks.
Here is my submission.
Here is a solution without the segment tree, just using prefix and suffix array for problem D solution
Has anyone solved Div2D with Segment tree?. I am getting TLE with two pointers{ increase right pointer till gcd >1 in the difference array} and take the maximum size of all valid subarrays.
Here is my submission : 126619908
Is there any scope for improvement here?
can you explain your sol thoroughly? because i think two pointer will not work in this i guess.
other than these tips, i couldnt see any implementation errors (like infinite loops).
(ik this was 3 years ago, hope you see this)
F2:
After I got struggled for hours with why "B is always even", I found "the area of the fence is an integer" in the problem statement.
QwQ.
Hello in english
Regarding problem D. If i use binary search submission 218897364 it gives TLE. if i use two pointers submission 218907845 it gets Accepted.Can anyone please figure out why ?.
There exists a somewhat different solution (albeit with the same time complexity) for D1E if we consider rows as "representatives" instead of cells. It can be implemented in a somewhat simpler manner using dsu and sets: 252411144