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

Revision en9, by CristianoPenaldo, 2023-08-27 05:40: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 $$$[\lceil \frac{n+scale-1}{scale} \rceil, \lceil \frac{n+scale/2-1}{scale/2} \rceil -1]$$$. In other words, $$$S(scale)$$$ is $$$\{x | x * scale \geq n &amp;&amp; x * scale/2 < n\}$$$.

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)