Блог пользователя Los_Angelos_Laycurse

brute_force Accepted 100543 G(Virus synthesis), I definetly don't know what is the time comlexity,seems to be O(n^2)
Автор Los_Angelos_Laycurse, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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...

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить