nocriz's blog

By nocriz, history, 2 years ago, In English

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.

How shall we improve this algorithm? We shall look at the code for FWHT as follows, which is very simple:

for(int i=0;i<n;i++){
    for(int j=0;j<1<<(n-1);j++){
        if(j&(1<<i) != 0)continue;
        int l = a[c],r = a[c|1<<i];
        a[c] = l+r;a[c|1<<i] = l-r;
    }
}

There are two features of the algorithm which we will exploit.

  1. It is easy to see that we can "merge" two FWHT arrays of $$$[x\times 2^n,x\times 2^n+2^{n-1}-1]$$$ and $$$[x\times 2^n+2^{n-1},x\times 2^n+2^{n}-1]$$$ into the FWHT array of the interval $$$[x\times 2^n,x\times 2^n+2^{n}-1]$$$ in $$$O(n)$$$ time.
  2. Each element $$$b_i$$$ in a FWHT array is of an interval $$$[x\times 2^n,x\times 2^n+2^{n}-1]$$$ of array $$$a$$$ is a linear combination of elements in $$$a$$$. Namely, $$$b_i = \sum_{j = 0}^{2^n-1} a_j c_{ij}$$$, where coefficients $$$c$$$ are the same for any FWHT transform of the same length $$$2^n$$$.

Actually, the process of the FWHT algorithm is simply recursively merging arrays. The reason that this is not obvious is that the implementation is optimised to use loops.

Now, we can improve the $$$O(n \log^2 n)$$$ algorithm using these observations. We are going to calculate using the same squares the $$$O(n \log^2 n)$$$ algorithm would calculate, but for each square of edge length $$$m$$$, we will spend $$$O(m)$$$ instead of $$$O(m \log m)$$$ time.

We calculate the FWHT arrays bottom-up, each time merging intervals to intervals that are two time larger. After merging intervals, we will calculate all squares of that size which we were originally going to calculate. For each square $$$[x\times2^n,x\times2^n+2^n-1] \times [y\times2^n,y\times2^n+2 ^n-1]$$$, we can add the value from multiplying $$$a_{x2^n+i}$$$ and $$$b_{y2^n+i}$$$ to $$$sum_{(x\oplus y)2^n+i}$$$, as squares with same $$$x \oplus y$$$ are the same when inverting the FWHT arrays.

But how shall we invert the array $$$sum$$$? The answer is simple: Just as we can calculate the FWHT arrays bottom-up, we can also "merge" sum arrays! This may seem to not make sense, but if we merge sum array up and split it back down, the "contribution" of values at the $$$n$$$-th level will be the same. This is because all transforms are linear, and that the FWHT transform is invertible.

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

So there you have it, now you know how to solve "The Struggle"!

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

»
2 years ago, # |
Rev. 5   Vote: I like it -70 Vote: I do not like it

Thanks for your great idea and wonderful analysis! It is a great problem.

»
2 years ago, # |
  Vote: I like it -59 Vote: I do not like it

Too much of maths

»
2 years ago, # |
  Vote: I like it -110 Vote: I do not like it

how to activate windows 11? i dont have money!!!

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Does what you said have anything to do with the content of the blog?

»
2 years ago, # |
  Vote: I like it +65 Vote: I do not like it

It was insanity to put it in a contest, but I had fun upsolving it at 3 o'clock, so thanks!

»
2 years ago, # |
  Vote: I like it -51 Vote: I do not like it

مرحبا ، هل يمكن أن تعطيني بيانات الاختبار؟

أريد استخدام هذه المشكلة في بطولتنا

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -55 Vote: I do not like it

    sorry my translate computer dont live!!! can you give test data problem of to me? i like use problem on contest of me for school compute class your jumper is very good, great and math. can you give problem data at private later in mail. i want know problem data test!!!! 我为没有直接传输到我的电脑而道歉!!! 你能告诉我测试数据的问题吗? 我喜欢使用问卷调查有关学校计算机科学课程的问题 你的鸟非常好,善良和数学。 此信息可以通过个人电子邮件发送。 我想体验数据测试问题!!!!

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      I don't think it will be necessary, nobody will solve this in the contest

»
2 years ago, # |
  Vote: I like it +38 Vote: I do not like it

There's a different approach/viewpoint to the "merge sum arrays step". Let's use $$$a[i]$$$ to denote a sequence and $$$\hat{a}[i]$$$ to denote its FWT. Let's use $$$(f * g)$$$ to denote the convolution of two sequences $$$f$$$ and $$$g$$$. Consider a single block. Instead of trying to run inverse FWT to find each $$$c[i]$$$ and then taking $$$\sum c[i] (k2^n + i)^{33}$$$, we can directly write it as a linear combination of $$$\hat{c}[i]$$$ (since FWT is just a linear transformation anyways).

What are the coefficients of this linear combination? Well, if we set $$$d[i] = (k2^n + i)^{33}$$$, we can view $$$\sum c[i] (k2^n + i)^{33}$$$ as the 0th term of the convolution: $$$(c * d)[0]$$$. The 0th term is easy to compute: it equals the mean of the elements of the FWT: $$$\frac{1}{2^s} \sum_{i=0}^{2^s} \hat{(c*d)}[i] = \frac{1}{2^s} \sum_{i=0}^{2^s} \hat{c}[i] \hat{d}[i]$$$. We can compute the $$$\hat{d}[i]$$$ the same way we compute the $$$\hat{a}[i]$$$ and $$$\hat{b}[i]$$$ from the bottom up! This lets us compute the contribution of a block without running any IFWT.

(In fact, $$$\hat{c}[i] = \hat{a}[i] \hat{b}[i]$$$, so we're actually summing $$$\hat{a}[i] \hat{b}[i] \hat{d}[i]$$$. This makes sense if you view the original sum as $$$\sum_{x,y,z} [x \oplus y \oplus z = 0] z^{33} x^{-2} y^{-1}$$$.)

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

    I think I have seen your implementation and understood it, but a few months later I forgot seeing it...... Makes total sense!