### cip999's blog

By cip999, history, 2 months ago,

Hello Codeforces!

Thanks for taking part in the SWERC 2021-2022 mirror. We hope you enjoyed thinking about the problems.

The contest was intended for a wide range of participants. As such, there were "very easy" to "easy" problems (A, M, H) as well as extremely challenging ones (B and J, neither of which appeared in the official contest, together with C). Some problems demanded the knowledge of specific techniques, algorithms or data structures (e.g. E, G, K, J), while others were purely based on insight and deduction (B, D, N).

But without further ado, let's present the editorial!

## Solutions

Solution of Problem A

Statement by dario2994, preparation by dario2994

Solution of Problem B

Statement by Giove, preparation by Giove

Solution of Problem C

Statement by gangsterveggies, preparation by gangsterveggies

Solution of Problem D

Statement by tap_tapii, preparation by tap_tapii

Solution of Problem E

Statement by Petr, preparation by Petr

Solution of Problem F

Statement by Simon, preparation by majk

Solution of Problem G

Statement by cescmentation_folch, preparation by cescmentation_folch

Solution of Problem H

Statement by majk, preparation by majk

Solution of Problem I

Statement by tap_tapii, preparation by gangsterveggies

Solution of Problem J

Statement by Simon, preparation by Simon

Solution of Problem K

Statement by gog.gerard, preparation by gog.gerard

Solution of Problem L

Statement by gog.gerard, preparation by gog.gerard

Solution of Problem M

Statement by cip999, preparation by cip999

Solution of Problem N

Statement by cip999, preparation by Delfad0r

Solution of Problem O

Statement by Simon, preparation by Simon

• +150

 » 2 months ago, # |   0 Auto comment: topic has been updated by cip999 (previous revision, new revision, compare).
 » 2 months ago, # |   +13 Thanks for the cool problemset!In problem B we did the following: SpoilerBuild a tripartite graph where $i$-th part consists of $l_i$ vertices, and connect every pair of vertices corresponding to equal letters in different strings. Let $m = \min(\text{max matching}, l_1, l_2, l_3)$. Then we will use $m$ cards, each covering a letter from each word, and then $\max\left(l_1 - m, l_2 - m, l_3 - m, \left\lceil\frac{l_1 + l_2 + l_3 - 3m}{2}\right\rceil\right)$ more cards to cover all other letters. It is kinda easy to show that this is kind of optimal.It is worse in terms of complexity, but still ok.
•  » » 2 months ago, # ^ |   +8 Very clean solution.By the way, the matching on the tripartite graph can be computed in O(1) since all connected components are complete tripartite graph. Hence also the complexity of your solution is very good.
 » 2 months ago, # | ← Rev. 2 →   0 I solved problem F in n * sqrt n and it didn't work :(. Edit: my bad, it worked.
 » 2 months ago, # |   +18 There is a solution to F that uses a persistent segment tree and graphs with a total of $\le 8 n \log n$ edges (probably much fewer) and does a 0-1 BFS on it (time and space complexity were both $O(n \log n)$). Was the tight memory limit intended to cut off this solution? We weren't able to implement a memory-efficient solution during the mirror. We had the idea to implement a custom-bitset solution with packed bits in order to implement a Chinese adjacency list, or an edge list, which could bring the memory usage down to 50 bits per edge, rather than 64 and 25 bits per node, rather than 32, so it could pass somewhat better. However, this is super-annoying to implement.
•  » » 2 months ago, # ^ |   0 The time limit and the memory limit were set so that the nlogn official solution and the nlog^2 official solution get accepted without any issue.In a problem such as this one, there is a continuous spectrum of solutions going from the clean nlogn to the naive quadratic (going through your solution and the solution O(nsqrt(n)) mentioned by 1BeeNY1). There will always be one such solution which is just barely not fitting the TL or the ML and whoever comes up with such solution will struggle during the contest.p.s. I just discovered what a Chinese adjacent list is.
•  » » » 2 months ago, # ^ |   +5 Thanks for the reply. I just finished reading the official solution, and I like it more than the solution we came up with. It's really nice that there are so many different ways of solving the problem and implementing the solution. I tend to like problems where you can use multiple ideas in order to make implementation much smoother, since that's a part of constant optimization. Great problem overall!
 » 2 months ago, # |   0 Btw, G and L have appeared before.L: https://codeforces.com/problemset/problem/76/F (but I guess L was meant to be a classical problem so its fine)
•  » » 2 months ago, # ^ |   0 Thanks for letting us know. We knew about L and we decided that it was ok.On the other hand we discovered only after the contest about G.I would really like to have a "Google search" for problems over all platforms so that one can search if a problem appeared before. E.g., one searches for "centroid bitset" and gets the links you mentioned.
•  » » » 2 months ago, # ^ |   +3 Nitpicking, but I don’t think the previous problems required bitset, they just had the same tree setup.
 » 2 months ago, # |   0 Thanks for the excellent statement
 » 2 months ago, # | ← Rev. 3 →   +41 I think there is a solution to problem K with complexity O(log_eps),because by doing some transformation the main part is to get a point which minimize the maximum of the distance from the point to a point and the sum of the distance from the point to two points and the answer point must on a line,which can be solved using a ternary search on the line.This is my solution:154909851
•  » » 2 months ago, # ^ |   +8 We had a similar solution in contest (our approach is explained here). A cleaned up implementation of our idea can be found here.
 » 2 months ago, # | ← Rev. 3 →   0 In C, is the last matrix mul formula wrong? I mean that the mul isn't fit the prev recursion formula. Edit:My bad,no problem.