November Long Challenge 2019: Winning Ways

,
1

I had no problem scoring 40 points on this problem:

  1. Calculate each number’s amount of divisors. Pollard Rho is an efficient way to do this but brute prime factorization was enough.
  2. Notice that finding out the game was a losing state could be obtained by getting the binary representation of each heap, and making sure the independent sum of each bit was divisible by 3.
  3. Handle lists of frequencies with all possible states, which could be trivially multiplied in O((3^{log(p)})^2), where p is the maximum number of divisors a number could have.
  4. Having defined this list multiplication, apply binary exponentiation and you have a O((3^{log(p)})^2log(k)) solution.

Where I struggled was on the original constraints (100 points). I figured some kind of transform was needed to multiply faster, but since the exponent operation was weird, it wasn’t as simple as copy-pasting a classic FFT or WHT implementation. It was necessary to dig into the theory.

So I did. After looking this up, I thought a WHT (Walsh-Hadamard Transform) with a matrix of size 3 x 3 could do the trick, the only thing left was to find the transformation matrix. Here is where I started to struggle. I tried to write down and solve the equation

T(a) \cdot T(b) = T(a \$ b)

(where \$ is the list multiplication operand, \cdot is the dot product, T is the transformation matrix, and a and b are the two lists).
But it got very tedious, and the equation wasn’t so friendly. So I created a bruteforce solution that created all possible transformation matrices and tested them on random vectors, and made sure an invertible matrix was found. The possible values on the matrices were \{1,-1\}. So I got nothing. After reading some more, I thought maybe more roots of unity were needed, so I tried with \{1, -1, i, -i\}. Nothing either. So I basically gave up and closed my laptop (it was Saturday night, I needed beer).

This morning I open AC’ed 100 solutions, and saw that I had figured out everything right, I was just missing the transformation matrix. Turns out it’s some weird shit that isn’t even conformed by roots of unity (value (-1 -i) is used!).

So yeah, theory killed me in this problem, I’m not a strong enough mathematician. Attacking this problem left me with a huge amount of questions. If someone could help me understand them I’d really appreciate it!.

Why do non-roots of unity work in this problem? If I find a matrix that fits with the transform operation I’m working on and is invertible, can I use it in WHT with no extra conditions at all?
Additionally, I find it fascinating how WHT works for transformations on several dimensions. In this problem, all dimensions had the same operation (sum modulo 3). Is it possible to have different operations across these dimensions? (assuming each has a valid invertible transformation matrix, of course). Or even further, applying different operations with matrices of different sizes?.
Finally, what is a good approach to understanding the proof of correctness of WHT? It is a major blackbox to me right now and I’d really like to get how it works.

Please help :stuck_out_tongue:

2 Likes
2

great people with great doubt:smile:

3

Actually the transformation is given by a matrix with roots of unity. Take w such that w^3=1 (w != 1)
and the WHT for this problem is given by the 3x3 matrix [{1 1 1}, {1 w w^2}, {1 w^2 w}]. The inverse looks almost the same [{1 1 1}, {1 w^2 w}, {1 w w^2}]. This should be normalized dividing by 1/3.

I don’t think that you can get different transformations on several dimensions.

1 Like
4

This “(-1 - i)” you see is actually a root of unity, at least if you’re looking at my solution.

The person above is correct that the transformation matrix will look like this:

\begin{pmatrix} 1 & 1 & 1 \\ 1 & \omega & \omega^2 \\ 1 & \omega^2 & \omega \end{pmatrix}.

Here \omega^3 = 1, \omega \ne 1. The problem? No such element exists modulo 10^9 + 7. The only cube root of unity is 1. We don’t want to go to complex numbers either, the values will get really huge and/or we have to awkwardly take many transforms and inverses.

So what’s the idea here? We will use some finite field theory to extend the field of numbers mod 10^9 + 7 to have such an \omega. This is somewhat awkward to explain but basically, we can use the field \mathbb{F}_{10^9 + 7}[x] / (x^2 + x + 1) (polynomials modulo x^2 + x + 1). Each element has two “coordinates”, both coordinates are modulo 10^9 + 7. Addition is pointwise, multiplication has some slightly awkward rule.

2 Likes
5

My solution was rather inefficient, I was considering the field \mathbb{F}_{10^9 + 7}[x] / (x^3 + 1), so each element had 3 coordinates a + b w + c w^2. Adition is pointwise and when you multiply two polynomials you must remember that w^3= 1. It is much more efficient to do as thuustalu proposed and work with polynomials modulo the irreducible polynomial x^2+x+1.

6

I just directly calculated it in complex numbers, but taking both real and imaginary part mod 1e9 + 7. My solution takes only 2.16s, and the majority comes from prime factorization which took about 1.92 for the max test.

1 Like