kalimm's blog

IX Zhautykov Olympiad : [Problem G] Round Words
By kalimm, history, 9 years ago, In English

What is the lenght of largest common subsequence of two round words? In a round word there is no difference from which symbol the word starts and in which direction it is read.

lcs("algorithm", "grammar") = "grma"

1≤N≤2000

http://izho.kz/uploads/izho_2013_en_inform.pdf

Do you have any solutions? Thanks for help.

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

»
9 years ago, # |
← Rev. 15   Vote: I like it -17 Vote: I do not like it 
substr(firstPost, len)
x[i][j] = lcm(a.substr(0, i), b.substr(0, j)) // can be built by easy n * n DP
y[i][j] = lcm(a.substr(n - i, i), b.substr(n - j, j)) 
ans = min(ans, x[i][j] + y[n - i][n - j]) for each i, j; 0 <= i, j <= n

Second table Y can be found by the same DP like first one, but for reversed strings a and b.
UPD: "Beware of bugs in the above code; I have only proved it correct, not tried it". Donald Knuth(c)
there are at least two bugs: lcm — lcs, min — max.

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

    Nice LCS implementation bro

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

    as i understood it just calculates lcs(n, m)

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

    BTW it's max bro

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

    It's simply calculate the lcs of two strings. Nice prove bro, nice prove

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

      Idea of my solution was wrong? Thanks for your ribbing and -16 for my help.

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

        It's simply calculate the lcs :(

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

Maybe this could help you :D

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

    Thanks, I didn't think to Google it :D

    → Reply