72VanVector_SevNTU's blog

CODECHEF. October Long contest
By 72VanVector_SevNTU, 13 years ago, In English

Hi to all. I want to discuss some problems from the last contest on codechef, which had just been over. There are given some tasks and ten days to solve them.

I,m interested in Prob E. Sine Partition Function especially. Tried to solve it using combinatorics and DP but recieved TLE (as I expected). I didn't use trigonometrical identities and I must mention that the precision of the output is rather weak, that could be useful, I guess. Will be glad to see your ideas.

Also it would be interesting to get some hints to  Prob F. Repeated String. I've got AC with very dummy algo as time limit make it possible. I've seen other solutions verdicts, they were rather fast.

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

13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Repeated String: Try to build suffix array and calculate least common prefixes of adjacent elements of the array.
→ Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Repeated string - let F(x) be the biggest count of equal substrings of length x in initial string. It can be easily proved that  F(x) ≥ F(x + 1), so we can use dichotomy with bounds left = L, right = H.
F(x) can be calculated in time using hashes and balanced tree or in O(n) time using hashes and hash-table.
So, the whole complexity will be or .
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I've got "Accepted" with method you described. It works 6 s, the other's sols worked 0.6 s. 
    → Reply