Deemo's blog

Fibonacci Strings problem
By Deemo, history, 9 years ago, In English

Can anyone tell me how to solve this problem?

http://codeforces.net/contest/177/problem/G2

Thanks in advance!

  • Vote: I like it
  • +36
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is enhanced version of one problem in ICPC WF 2012: https://icpc.kattis.com/problems/fibonacci

Short editorial for WF 2012: http://www.csc.kth.se/~austrin/icpc/finals2012solutions.pdf

I "guess" matrix exponentiation will do the trick for enhanced version (unproven for now, I didn't have time to analyse further).

→ Reply
»
9 years ago, # |
← Rev. 5   Vote: I like it +13 Vote: I do not like it

Let's calculate for each prefix s[1..i] the minimum fibonacci index minind[i] such that s[1..i] is a suffix of fib[i] and s[i + 1..n] is a prefix of fib[i + 1].

Because the relation

fib[i] = fib[i - 1]fib[i - 2]

can be written equivalently as:

fib[i] = fib[i - 2]fib[i - 3]fib[i - 2]

it follows that $min_ind[i]$ is either ∞ or less than n (because fib[i] has all the prefixes of fib[i - 2]). After that, it is essentially a linear reccurence of type

DP[i] = DP[i - 1] + DP[i - 2] + occurences_less_than_inf

for all $\i \geq n$ (or n + 2 or smth.).

You basically have to compute DP[n] and DP[n + 1] and occurences_less_than_inf, and then do matrix exp. I think that should work :).

→ Reply