Mukit09's blog

Lightoj 1110 (An Easy LCS) >> To Find Out Lexicographically Smallest LCS String .... Help Please !!!
By Mukit09, 11 years ago, In English

Two string will be given. I've to find out lexicographically smallest LCS string. I have coded one, but it is giving me WA... I tried with some cases, but failed to find out the problem. Would anyone help please ???

I just need the case for which case my code is failed... Please help ... :(

My code is here

Problem Link is here

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

Comments Comments (12)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have no idea why you use so many pointers and char arrays and moreover why you pass it to one of your functions (I'm sure if you pass the test you have WA currently u'll get TLE due to many strcpys).

I would just reverse strings and make DP[][] and B[][] matrices (see CLRS for details) and if s1[i]!=s2[j] and DP[i-1][j] is equal to DP[i][j-1] choose lexicographically smaller.

Lastly, using B[][] determine the answer and reverse it.

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

    As there can be at most 100 character in a string, I thought that would not be a problem... :(

    And if I don't do wrong calculation, my code's complexity is O(n^3)... Will it give TLE for n=100 in online judge like lightoj ??? It's sure if it is spoj, I'll never like to do so... :)

    If I do any wrong, please show me... :(

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      it's wrong to copy all string when you are at some level of recursion. use string DP(int i1, int i2); if (res.size() < t.size() || res.size() == t.size() && res > t) res = t;

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

        Actually I tried with return type string too...

        But when I return a string to a level, the level I want to send, receive a null string always...

        So I was compelled to do so.. :(

        May be my implementation can be wrong... :/

        Anyway, would you tell me please, what is the problem when I copy a string in different level of a recursion... Is it problem too, if I use pointer ???

        Please, let me known... :(

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          beacause there can be bad remembered prefix of optimal answer. for example LCS length is 5 at some step of recursion you have prefix "ba" and remeber for this i1 = 42 and i2 = 66 dpc[i1][i2] = "ba???" then at some step you have prefix "ab", but when you step in remembered state i1 = 42 and i2 = 66 you rewrite all the answer with bad prefix "ba". it is bad because "ab" is better.

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

          code

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

    why you reverse strings?

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

      I've not reversed any string...

      If you tell about 92 & 93 number line what I've done is,

      when ch1[i]==ch2[j], I've firstly stored this character in st1[0], then kept all characters of res string in st1.

      That's all... :)

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

        my comment is adressed to this comment

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

          Ow... Sorry ... :)

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

          Well, because I don't want to compare whole strings (current answers), so I greedily compare only last characters of them. In other words it means I put more importance on last characters which is obviously incorrect, but it should work for reversed strings because there I do want that initial characters be more important.

          But interestingly enough this idea (or I hope implementation of it) is getting WA too :D :D

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

            I tried this approach too.but this approach fails cases when immediate matched character is same and better solution can be found in depth.

            → Reply