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

Правка en15, от CristianoPenaldo, 2023-08-27 05:53:48

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 get a recurrence using the BM algorithm, and construct a recurrence matrix using that recurrent, for example $$$a_r = a_{r+1} + a_{r+2}$$$, then

[ \begin{bmatrix} x_{11} & x_{12} & x_{13} & \dots & x_{1n} \ x_{21} & x_{22} & x_{23} & \dots & x_{2n} \ \hdotsfor{5} \ x_{d1} & x_{d2} & x_{d3} & \dots & x_{dn} \end{bmatrix} ]

Code:

Spoiler
Теги berlekamp-massey, turtle

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)