Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

danhnguyen0902's blog

[SPOJ] LQDNUMS
By danhnguyen0902, 13 years ago, In English

Does anyone know how to solve this problem?

http://www.spoj.com/problems/LQDNUMS/

Or at least please give me the references for it. Thanks a lot in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
13 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I have some ideas to solve it in polynomial time, but it's too slow.
Let F(N) be the length of the result string. We have to find N, such that F(N) == M.
Use binary search to find N. F(N) can be calculated using DP and fast matrix exponentiation. I know how to do it with about 18-36 matrices of size K x K, K ~ 18 * 10 * 2.

→ Reply
  • »
    »
    13 years ago, hide # ^ |
    ← Rev. 4  
    Vote: I like it 0 Vote: I do not like it

    No, i was wrong with matrix exponentiation. I think there is kind of dp, we have to divide iterval [1..N] into several ones with the same prefix. for example for N = 1234 ther will be
    [1..999] for all numbers with length < length(N)
    [1000..1199] — 1 234
    [1200..1229] — 12 34
    [1230..1234] — 123 4

    for each of these intervals we have to use this dp recursively.

    → Reply