Los_Angelos_Laycurse's blog

brute_force Accepted 100543 G(Virus synthesis), I definetly don't know what is the time comlexity,seems to be O(n^2)
By Los_Angelos_Laycurse, 10 years ago, In English

http://codeforces.net/gym/100543 can't believe my eyes.....

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Time limit is 30 seconds. O(n2) with small constant can pass...

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    15s per case, but I don't how many test cases per test file.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      965 in second test
      218324 in third test
      43261 in fourth test

      But you should expect that there are not many large cases in test file.

      → Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you describe your solution please? Your code is too long to analyze it ^.^'

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    first for each position i,regard it as middle point of a Palindromic Substring then find longest palindromic substring with i is the middle point sg[i].l,sg[i].r, the brute force implement of this part is O(n^2),but there are optimazition,if we know the previous sg[i-1].l,sg[i-1].r

    for each point between [i,sg[i-1].r], it is Symmetric with [sg[i-1].l,i-1],so we can use the information [sg[i-1].l,i-1] to optimal [i,sg[i-1].r]. (but in fact for my implement of this optimizition I don't what is the compleixity,maybe it can be optimaled to O(n)),

    after we find every sg[i].l,sg[i].r then it is a brutefore dfs with memory search;

    just search(0,n-1), when search(left,right), first deal every point left<=i<=right,with its sg[i].l,sg[i].r,record them ,sort them with their decreasing length(sg[i].r-sg[i].l)

    then opt(left,right)=min(opt(sg[i].l,i)+1+sg[i].l-left+right-sg[i].r); there is some prunning: lower_bound of opt(left,right) is low[right-left]=log(right-left)+1, so if current_result<=low[i-sg[i].l]+sg[i].l-left+right-sg[i].r then break;

    idea is too simple,if you find O(n^2) testcase or even O(n^3) discuss it...

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With Manacher's algorithm you can find sg[i-1].l,sg[i-1].r in O(n).

      after we find every sg[i].l,sg[i].r then it is a brutefore dfs with memory search;

      This part works in O(magic), I don't know how to estimate this :)

      Anyway it is pretty interesting. Almost nobody tried to solve this problem (maybe everyone is scared of strings) but the testcases seem to be pretty weak, so any correct solution (or even sometimes not correct) with a little bit of optimizations should pass.

      → Reply