cip999's blog

Editorial of SWERC 2021-2022 Online Mirror
By cip999, history, 3 years ago, In English

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

  • Vote: I like it
  • +150
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by cip999 (previous revision, new revision, compare).

→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks for the cool problemset!

In problem B we did the following:

Spoiler
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved problem F in n * sqrt n and it didn't work :(. Edit: my bad, it worked.

→ Reply
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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!

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Btw, G and L have appeared before.

G: https://dmoj.ca/problem/cco19p3 or https://szkopul.edu.pl/problemset/problem/3bBT-3VuSu78UsxTQSwaJzVo/site/?key=statement

L: https://codeforces.net/problemset/problem/76/F (but I guess L was meant to be a classical problem so its fine)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Nitpicking, but I don’t think the previous problems required bitset, they just had the same tree setup.

      → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +41 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    We had a similar solution in contest (our approach is explained here). A cleaned up implementation of our idea can be found here.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i'm wondering under what conditions we can think of a problem as a group theory problem like D. magic.

→ Reply