Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

CristianoPenaldo's blog

By CristianoPenaldo, history, 16 months ago, In English

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×scalen,x×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(logscale) 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(logscale) and a recurrence matrix MZ/pZO(logscale)×O(logscale).

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 ar=ar+1+ar+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(logscale) items and each item costs O(logscale3logn) using a fast matrix power algorithm (matrix multiplication is O(logscale3), and there are up to O(n) elements for each scale. Therefore the complexity for each scale is O(logscale4logn) and the overall complexity is scaleO(logscale4logn)=O((logn)6) for each test case which is too slow. Any idea to speed up?

Code:

Spoiler
  • Vote: I like it
  • -3
  • Vote: I do not like it