caioaao's blog

Help on problems "Binary Tree" (ACM ICPC SWERC 2013-14)
By caioaao, 10 years ago, In English

Hello, I'm trying to solve this question from SWERC: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4423

I tried to understand the editorial, but failed to do so. It is available here (under question H): http://users.dsic.upv.es/swerc/ProblemSet2013/solutions.pdf

I understood the recursion for the DP, but I can't understand why you can just go up when you bump into a "U" and use the same recursion. for me it'd recount some positions. An easy example is S="LL" and T="UL".

Could someone help me out?

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

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

If the last move on S was L and you use an U, your next move has to be R, otherwise you'll double-count as you mentioned. Similarly, when you use two Us, your next move has to be the opposite of whatever was the next-to-last move in S. The editorial just ignores most of the details.

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

    Thanks! I tried doing something like it, but I'm getting WA on test case 2. I tried checking the official test data, but my code fails only on big cases. I did it like this: save string S without "u"s (for each U found, I pop the last one), where S[0] is the root of the tree. Then, I save the nextL and nextR for the concatenated S+T (without U's), but when in S, nextL/nextR will point to end if the next letter is not L/R, respectively. Then, for each 'U' in T, I go up one character in S and point the letter that was missing to the nextX after U. I then run the simple DP: DP(id) = (DP(nextL) + DP(nextR)), if you are able to stop in "id", then DP++. You can stop in "id" if "id" is in T or if you can jump back up to "id" in "S".

    Here is my code: http://pastebin.com/jThJdznp

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

      I tried, but couldn't understand what you were doing there, sorry :(

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

        Let me see if I can explain it better:

        Let S="LLRLR" and T="RRLRRLR". If you concatenate both, you get X="0LLRLRRRLRRLR" (I add the "0" in the beginning to represent the root of the tree).

        Now, let nextL[id] be the next L which you can move directly to when you are on "id" on X. Same for nextR[id]. As we can skip steps when you are on T, you can go to any letter after id. The same is not true when id is inside the S part (except the last letter from S), as you can go only to the next letter. When there is no movement left, I say you go to the end of the sequence.

        So, for the example above, I get:

        id    = 0  1  2  3  4  5  6  7  8  9 10 11 12
X     = 0  L  L  R  L  R  R  R  L  R  R  L  R
nextL = {1, 2, end, 4, end, 8, 8, 8, 11, 11, 11, end, end}
nextR = {end, end, 3, end, 5, 6, 7, 9, 9, 10, 12, 12, end}

        Also, when you are on S, you can't stop some subset there (that affects the DP later), but you can stop the subset anywhere from the last character from S to the end of the string. So I save another array of bools to keep track of this, and call it "ok2s":

        ok2s = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1}

        Now, it's easy to run a DP to count the different final positions:

        DP(int id):
    if id == end: return 0;
    return DP(nextL[id]) + DP(nextR[id]) + ok2s[id];

        Answer would be DP(0)

        Now we have to handle the "U"s... It's simple in S: just pop back the last element if this is not the root. When U's show up in T is the tricky case. This is what I have come up with: "U"s will only affect the number of final positions if they're able to modify the constraints on the first string S (otherwise it'd be the same as ignoring the instruction in T). You can go back up 1 position in S for every U found in T. This is because you can just ignore the rest of the instructions between U and S. But now we have a whole lot of other R's and L's that were not achievable from that position in S, and we can even stop the sequence there. So we update the nextL, nextR and ok2s arrays. We can just get the min(nextX from id, nextX from U found). So if we modify the example I gave back there with an U before 8, this is the result:

        id    = 0  1  2  3  4  5  6  7  8  9  10 11 12
X     = 0  L  L  R  L  R  R  R  L  R  R  L  R 
nextL = {1, 2, end, 4, 8, 8, 8, 8, 11, 11, 11, end, end}
nextR = {end, end, 3, end, 5, 6, 7, 9, 9, 10, 12, 12, end}
ok2s = {0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1}

        nextL[4] is changed from "end" to "8" and ok2s[4] from 0 to 1, and we can call the same DP(0) to get the result for this.

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

          You have an off-by-one error in lines 88/89. Change S.size() - us[i] to S.size() - us[i] - 1.

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

            I can't believe it haha. I spent some hours checking those stuff out and couldn't see it. Got AC, thanks!

            → Reply