Detailed Editorial for problem "The Struggle" from XXII Opencup, Grand Prix of XiAn

Правка en1, от nocriz, 2021-11-01 16:57:29

Hello, Codeforces!

It has come to my mind that a problem I authored, "The Struggle", despite having appeared in the HDU Multiuniversity Training (where there are ~1000 3 people teams), the Ptz Summer Camp and the Open Cup, I know of few (possibly no more than 5) people who have learned and independently implemented the solution.

The problem is pretty much fun and the solution is quite easy to implement (actual implementation < 2kb). In order to make a new advertisement for the problem and to spread the trick of the problem, I think it will be a good idea for me to written a good tutorial for the problem. So here it is!

The problem

The algorithm complexity of this question is $$$O(n \log n)$$$, where $$$n = \max_{(x,y) \in E} \max(x,y)$$$. Consider using the FWT algorithm for calculation. We consider xor convolution which can only process one at a time a$[x\times2^n,x\times2^n+2^n-1] \times [y\times2^n,y\times2^n+2 ^n-1]$ square. We first process all the largest squares that are all inside the ellipse, and then process the next largest squares, and so on...

But the complexity of this algorithm is $$$O(n \log^2 n)$$$, which is not fast enough. Consider optimizing this algorithm. The method is to perform FWT from the bottom up, and calculate the squares that need to be calculated at each layer. After calculating the inner product of FWT array, we should not calculate the inverse FWT, but should "accumulate" it on the result array. (See author's solution for better understanding)

One issue in the complexity analysis of this question is to prove that the sum of the side lengths of all squares is $$$O(n \log n)$$$. This fact can be proved on the condition that the border function is a monotone function, and the boundary of the ellipse can be split into four monotone functions. The idea of the proof is to see that the y-intervals corresponding to each x-interval must be a constant plus some "extra" intervals, and for x-coordinate intervals of the same size, the total length of the "extra y-intervals" cannot exceed $$$n$$$. Since there is only $$$\log n$$$ sizes for x-intervals, the proof is done.

Теги #struggle, opencup, editorial, tutorial

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en23 Английский nocriz 2021-11-02 02:33:56 0 (published)
en22 Английский nocriz 2021-11-02 02:32:38 1088
en21 Английский nocriz 2021-11-01 18:01:53 419
en20 Английский nocriz 2021-11-01 17:57:36 892
en19 Английский nocriz 2021-11-01 17:51:00 61
en18 Английский nocriz 2021-11-01 17:49:52 3
en17 Английский nocriz 2021-11-01 17:49:28 834
en16 Английский nocriz 2021-11-01 17:47:04 4243
en15 Английский nocriz 2021-11-01 17:45:33 220
en14 Английский nocriz 2021-11-01 17:41:48 55
en13 Английский nocriz 2021-11-01 17:40:49 105
en12 Английский nocriz 2021-11-01 17:39:31 5892
en11 Английский nocriz 2021-11-01 17:37:18 529
en10 Английский nocriz 2021-11-01 17:29:32 56
en9 Английский nocriz 2021-11-01 17:28:52 18
en8 Английский nocriz 2021-11-01 17:28:10 715
en7 Английский nocriz 2021-11-01 17:20:37 2 Tiny change: '^n-1} c_i^33$ and this' -> '^n-1} c_i^{33}$ and this'
en6 Английский nocriz 2021-11-01 17:20:07 409 Tiny change: 't a time a$[x\times2' -> 't a time a $[x\times2'
en5 Английский nocriz 2021-11-01 17:14:34 227
en4 Английский nocriz 2021-11-01 17:10:04 200
en3 Английский nocriz 2021-11-01 17:06:32 304
en2 Английский nocriz 2021-11-01 17:01:48 389
en1 Английский nocriz 2021-11-01 16:57:29 2205 Initial revision (saved to drafts)