You won't necessarily get the spanning tree with largest depth, but the argument works for any tree you'll get that way. (it's possible that sometimes both CYCLES and PATH solutions exist but the argument guarantees that if your dfs tree has depth < n/k then the CYCLE solution works)

Yeah, sorry for that, I didn't think I will publish author solution.

To come up with this idea, you might think: "Everything we need is a ring with 10-th root of one. We know one similar ring, complex numbers (i is the 4-th root of one). So let's just make our own ring, where x is the 10-th root. Then each number in this ring has a form of a_0*x^0+a_1*x_1+...+a_9*x^9". It is actually polynomial ring, but it doesn't matter. Then you somehow (I did it after writing the solution) realise that you get the answer quite not as you was expecting and you should eliminate large powers of x (for example x^7=-x^2). You come up with identity x^4-x^3+x^2-x^1+x^0=0 and actually solve the problem.

(The followings are mostly equivalent to scanhex's explanation in some sense. I just want to share how I came up with the solution. Some details, such as why DFT is used, how to divide 10 in the final step, are skipped since they are exactly the same as scanhex's explanation.)

I used the ring modulo x⁵ - 1. It is more natural to me. Actually, no polynomial rings appeared in my mind before I attempted to proof my solution after getting AC.

According to Wikipedia, we need a principal root of unity in which has the exact same role with in . We can easily see that  - 1 is a principal root of unity. In order to convert this root from order 2 to order 10, I extended the ring to include ω₅ and thus  - ω₅ becomes a valid candidate. Then the ring is now extended to to preserve the closure of addition and multiplication. For implementation, we only need to store those a₀, a₁, ..., a₄. In fact, 1 + ω₅ + ... + ω₅⁴ = 0 (which is also required by the definition of principal root of unity). It is sufficient to store 4 of those coefficients but this increases the complexity of the DFT so I simply stored all of the 5 coefficients.

Originally, I thought the final answer is a₀ in each corresponding entry after the inverse DFT, which is incorrect. In the debugging process, I found that a₁ = a₂ = a₃ = a₄ after the inverse DFT. Then I used a₀ - a₁ as the final answer and got AC.

The last step is correct since 1 + ω₅ + ... + ω₅⁴ = 0 implies a₀ + a₁ω₅ + ... + a₄ω₅⁴ = (a₀ - a₁) + (a₂ - a₁)ω₅² + (a₃ - a₁)ω₅³ + (a₄ - a₁)ω₅⁴. ω₅ is a root of the polynomial , which is irreducible over . The degree of the polynomial is 4 so the above representation with 4 coefficients is unique. Then implies a₂ - a₁ = a₃ - a₁ = a₄ - a₁ = 0.

As a side note, the first idea in my mind is changing the input numbers to base 19 without changing the digits, i.e. . Then we can use 1D FFT with fast exponentiation and handle the modular operation on each digit ourselves between each FFT. However, the constant factor, 1.9⁵ is too large and the modular base 2⁵⁸ is not friendly.

Oh, I think I can answer your question. Forget about modulo for a moment and just think that we store real values. The solution will work, except precision issues as numbers will be large. Now, let's just calculate everything modulo 2^64 instead. We can always take any algorithm and do every operation modulo 2^64, result will remain correct (as long as we don't divide by zero).

Length of string in 14 Test Case is 999. So just add a Constraint to your code to see if it print answer of every index and if not then print the boolean array. Remember not to print required answer in case if length of string is 999 Cheers :P

If y and x both are ancestors of some vertex 'v' ; then y,x and v all form a chain. Draw this on a paper ( In order y , x , v ( As he says dis(y,v) > dis(x,v) ) ; and you will see how !