Need An improvement for my solution [H. Asterism Stream, Berlekamp-Massey]

Revision en28, by CristianoPenaldo, 2023-08-29 06:39:15

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

#### History

Revisions

Rev. Lang. By When Δ Comment
en28 CristianoPenaldo 2023-08-29 06:39:15 4
en27 CristianoPenaldo 2023-08-27 06:12:24 0 (published)
en26 CristianoPenaldo 2023-08-27 06:10:17 49 (saved to drafts)
en25 CristianoPenaldo 2023-08-27 06:09:56 5
en24 CristianoPenaldo 2023-08-27 06:09:43 0 (published)
en23 CristianoPenaldo 2023-08-27 06:09:21 4
en22 CristianoPenaldo 2023-08-27 06:08:39 220
en21 CristianoPenaldo 2023-08-27 06:07:05 509
en20 CristianoPenaldo 2023-08-27 05:57:41 5 Tiny change: '\n\n$\nx\\\\ny\n$\n\' -> '\n\n$\nx\n\ny\n$\n\'
en19 CristianoPenaldo 2023-08-27 05:57:32 1 Tiny change: '\n$\nx\\\ny\n$\' -> '\n$\nx\\\\ny\n$\'
en18 CristianoPenaldo 2023-08-27 05:57:24 332
en17 CristianoPenaldo 2023-08-27 05:55:08 292
en16 CristianoPenaldo 2023-08-27 05:54:32 63
en15 CristianoPenaldo 2023-08-27 05:53:48 512
en14 CristianoPenaldo 2023-08-27 05:49:22 441
en13 CristianoPenaldo 2023-08-27 05:45:37 22 Tiny change: 'ale \geq n\\}$. \n' -> 'ale \geq n, x \times scale/2 < n\\}$. \n'
en12 CristianoPenaldo 2023-08-27 05:45:01 21 Tiny change: 's $\\{x | \\}$. \n\n' -> 's $\\{x | x \times scale \geq n\\}$. \n\n'
en11 CristianoPenaldo 2023-08-27 05:42:33 2 Tiny change: ' is $\\{x \\}$. \n\' -> ' is $\\{x | \\}$. \n\'
en10 CristianoPenaldo 2023-08-27 05:42:15 39
en9 CristianoPenaldo 2023-08-27 05:40:17 8
en8 CristianoPenaldo 2023-08-27 05:39:57 5 Tiny change: ' is $\\{x \mid x * scale' -> ' is$\\{x | x * scale'
en7 CristianoPenaldo 2023-08-27 05:39:48 4
en6 CristianoPenaldo 2023-08-27 05:39:22 2
en5 CristianoPenaldo 2023-08-27 05:38:56 96
en4 CristianoPenaldo 2023-08-27 05:37:19 25
en3 CristianoPenaldo 2023-08-27 05:36:35 2
en2 CristianoPenaldo 2023-08-27 05:32:04 310
en1 CristianoPenaldo 2023-08-27 05:28:42 31032 Initial revision (saved to drafts)