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

Автор Mukit09, 11 лет назад, По-английски

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

Теги dp
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

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

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.

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

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

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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;

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

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

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

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

    why you reverse strings?

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

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

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

        my comment is adressed to this comment

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

          Ow... Sorry ... :)

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

          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

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

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