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

Правка en13, от CristianoPenaldo, 2023-08-27 05:45:37

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 \times scale \geq n, x \times scale/2 < n\}$$$.

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)