Because of the relative speed/limit of the judge, there are some problems on CSES that are difficult to solve in Java just because Java is a little slower. For most problems the test cases are available on the submission site so you can try to download them test your program locally.

"Tourist knows the Nim value of any chess position." is extra funny since chess isn't even an impartial game

Thanks!

Use FFT/DC to get $$$(x - a_1)(x - a_2) \cdots (x - a_{n - 1})$$$ and then multi-point evaluation on $$$1, 2, \dots, n$$$ to find which one is non-zero.

Would you consider this article to be rigorous enough?

They refer to the same thing. GCC stands for GNU Compiler Collection.

I think the fastest way is O(N^3) using the Hungarian Algorithm unless the array has some other special property

Same reason (in most cultures) we write top to bottom

There is a stupid systematic way in $$$O(N \log^3 N)$$$. Assume without loss of generality that there is at least one positive element.

Let $$$a_i = \frac 1{x_i}$$$ and $$$p_i$$$ be $$$\sum_{j = 1}^i a_j$$$ (prefix sum array of $$$a_i$$$).

We wish to pick two endpoints $$$l$$$ and $$$r$$$ such that $$$\frac{r - l + 1}{\sum_{i=l}^r \frac 1{x_i}}$$$ is maximized.

Let $$$l_0 = l - 1$$$,

We wish to maximize this value. We note for later that $$$p_r - p_{l_0}$$$ must be positive. We binary search on $$$k$$$ to find how many $$$0 \leq l_0 \leq r \leq N$$$ satisfy

Let $$$b_i = i - p_ik$$$, then we want to check how many pairs $$$0 \leq l_0 \leq r \leq N$$$ satisfy $$$b_r \geq b_l$$$ AND $$$p_r \gt p_{l_0}$$$. This is a 3D partial order problem which can be solved using CDQ in $$$O(N \log^2 N)$$$. (Tutorial)

For each iteration of the binary search, if no pairs $$$l_0, r$$$ are found, then $$$k$$$ is too high, otherwise, it's at least that value of $$$k$$$.

Floating point accuracy is likely a big issue. The case where all elements are negative can be handled in a similar way.

Simon Tatham's Games are somewhat popular in this community.

rpeng has an answer here

No you are correct, because modulo should be prime or at least coprime to base, unless you want to generate random prime

Thank you, I finally understand now.

The problem is, we have to increment each element on the interval by a multiple of the sum of b_i across all ancestors, not a single value across all elements, so lazy propagation doesn't work.

For Problem G, is a lazy segment tree possible instead of sqrt decomp? Is sqrt just to make implementation easier?