Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

### CristianoPenaldo's blog

By CristianoPenaldo, history, 8 months ago,

I was using the Berlekamp-Massey (BM) algo for yesterday's H, but my sol worked too slow. Here is my idea:

(1) Divide $[1, n]$ into scales. Let $S(scale)$ be the scale $scale$, which is $S(scale)$ is $\{x | x \times scale \geq n, x \times scale/2 < n\}$. For example, if $n=7$, scale $1$ is $[7, 7]$, scale $2$ is $[4, 6]$, scale $4$ is $[2, 3]$, scale $8$ is $[1, 1]$. It is guaranteed that $scale$ is a power of $2$ in my sol.

(2)Fetch $O(log scale)$ consecutive items for each scale using the matrix fast power algorithm. The matrix is constructed in step (3) from the last scale.

(3)Using the BM algorithm to build a recurrence of length $O(log\,scale)$ and a recurrence matrix $M \in \mathbb{Z}/p\mathbb{Z}^{O(log\,scale) \times O(log\,scale)}$.

I mean for each scale we fetch some items $I$, get a recurrence using the BM algorithm, and construct a recurrence matrix $M$ using that recurrence, for example $a_r = a_{r+1} + a_{r+2}$, then

The matrix $M$ and the items $I$, and the fast matrix power algorithm, are used to fetching items for the next scale. This is a coarse-to-fine algorithm. The problem is that, for each scale, I need to fetch $O(log\,scale)$ items and each item costs $O(log\,scale^3log\,n)$ using a fast matrix power algorithm (matrix multiplication is $O(log\,scale^3)$, and there are up to $O(n)$ elements for each scale. Therefore the complexity for each scale is $O(log\,scale ^ 4 log\,n)$ and the overall complexity is $\sum\limits_{scale} O(log\,scale ^ 4 log\,n) = O((logn)^6)$ for each test case which is too slow. Any idea to speed up?

Code:

Spoiler
• -3