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

Revision en19, by nocriz, 2021-11-01 17:51:00

Hello, Codeforces!

"The Struggle" (Codeforces Gym 103329F) is a problem I authored which appeared in the HDU Multi-university Training, the Ptz Summer Camp and the Open Cup. Despite appearing in contests where there are a total of ~1300 three people teams, 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). hos_lyric said that this is a good problem! From this blog you will easily learn how the algorithm works and how to implement the solution effortlessly. There shall be no more mystery, and you will become able to solve this OpenCup problem that few people have solved right today!

The problem statement is very simple: Given an ellipse $$$E$$$ that is contained in $$$(0,4 \times 10^6) \times (0,4 \times 10^6)$$$, calculate the value $$$\sum_{(x, y) \in E}(x \oplus y)^{33} x^{-2} y^{-1} \mod 10^9+7$$$ over all integer points $$$(x,y)$$$. In this problem, $$$\oplus$$$ is the bitwise XOR operation.

While the solution does not seem to be obvious, we shall consider a easier case: how should we compute $$$\sum_{x = 0}^{2^n-1}\sum_{y = 0}^{2^n-1} (x \oplus y)^{33} x^{-2} y^{-1} \mod 10^9+7$$$? i.e. If the aria is a square $$$[0,2^n-1] \times [0,2^n-1]$$$, how to calculate the value? (For our purposes we shall consider $$$0^{-2} = 0^{-3} \equiv 0 \mod 10^9+7$$$.)

This is quite simple! This can be done in $$$O(n \log n)$$$ time, using an algorithm called "Fast Walsh Hadamard Transforms" or FWHT or FWT or fast xor convolution. The convolution basically calculates $$$c_i = \sum_{x = 0}^{2^n-1}\sum_{y = 0}^{2^n-1} [x \oplus y = i]a_xb_y$$$. If we set $$$a_i = i^{-2}$$$ and $$$b_i = i^{-3}$$$, we can calculate $$$\sum_{i = 0}^{2^n-1} c_i \times i^{33}$$$ and this will be the answer for our easier case.

We shall then consider: What if my square is different than $$$[0,2^n-1] \times [0,2^n-1]$$$? What if the square we want to calculate on is $$$[x\times2^n,x\times2^n+2^n-1] \times [y\times2^n,y\times2^n+2 ^n-1]$$$?

This case turns out to be just as simple! We can see that as all bits in the binary representation except the last $$$n$$$ bit changes, for $$$0 \le i,j < 2^n$$$ we have $$$(x\times 2^n+i) \oplus (y\times 2^n+j) = 2^n(x \oplus y)+i \oplus j$$$. Based on this observation we can simply set $$$a_i = (i+x\times 2^n)^{-2}, b_i = (i+y\times 2^n)^{-3}$$$ and calculate $$$c_i = \sum_{x = 0}^{2^n-1}\sum_{y = 0}^{2^n-1} [x \oplus y = i]a_xb_y$$$. $$$\sum_{i = 0}^{2^n-1} c_i \times (i+(x \oplus y)2^n)^{33}$$$ will be the answer. The complexity will be $$$O(n \log n)$$$.

After making the above observations, we can come up with a quite efficient algorithm already! The algorithm simply works as the following pseudocode:

int solve(square S = [x*2^n,x*2^n+2^n-1]*[y*2^n,y*2^n+2^n-1]){
    if(S is completely in the ellipse){
        return the value calculated by the above discussed FWHT method.
    }
    Let the four sub-squares be S1,S2,S3,S4;
    return solve(S1)+solve(S2)+solve(S3)+solve(S4);
}

What is the complexity of this algorithm? Unfortunately, the complexity is $$$O(n \log^2 n)$$$. The analysis is not simple, but I would assure you that I did the analysis for simpler cases where the range is like $$$|x-y|<c$$$ and there is two logs. The analysis is omitted here. The algorithm does not run fast enough.

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.

For implementation, please reference the author's solution.

Here is the author's solution for reference

During the HDU competition the problem was $$$\sum_{(x, y) \in E}(x \oplus y)^{3} x^{-2} y^{-1} \mod 10^9+7$$$. The team Inverted Cross wrote a data structures based solution which works on $$$O(3 n \log n)$$$ time (with large constant). The program was unfortunately, not fast enough.

Another solution written by Inverted Cross, but only works when 33 is substituted for 3
Tags #struggle, opencup, editorial, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en23 English nocriz 2021-11-02 02:33:56 0 (published)
en22 English nocriz 2021-11-02 02:32:38 1088
en21 English nocriz 2021-11-01 18:01:53 419
en20 English nocriz 2021-11-01 17:57:36 892
en19 English nocriz 2021-11-01 17:51:00 61
en18 English nocriz 2021-11-01 17:49:52 3
en17 English nocriz 2021-11-01 17:49:28 834
en16 English nocriz 2021-11-01 17:47:04 4243
en15 English nocriz 2021-11-01 17:45:33 220
en14 English nocriz 2021-11-01 17:41:48 55
en13 English nocriz 2021-11-01 17:40:49 105
en12 English nocriz 2021-11-01 17:39:31 5892
en11 English nocriz 2021-11-01 17:37:18 529
en10 English nocriz 2021-11-01 17:29:32 56
en9 English nocriz 2021-11-01 17:28:52 18
en8 English nocriz 2021-11-01 17:28:10 715
en7 English 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 English nocriz 2021-11-01 17:20:07 409 Tiny change: 't a time a$[x\times2' -> 't a time a $[x\times2'
en5 English nocriz 2021-11-01 17:14:34 227
en4 English nocriz 2021-11-01 17:10:04 200
en3 English nocriz 2021-11-01 17:06:32 304
en2 English nocriz 2021-11-01 17:01:48 389
en1 English nocriz 2021-11-01 16:57:29 2205 Initial revision (saved to drafts)