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

Revision en26, by CristianoPenaldo, 2023-08-27 06:10:17

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 $$$[3, 6]$$$, scale $$$4$$$ is $$$[2, 2]$$$, 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
Tags berlekamp-massey, turtle

History

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