memset123's blog

By memset123, 3 years ago, In English,

Recently, in order the celebrate the new year :), I was looking at some codeforces problems. I found one specific data structure problem (here) to be very interesting. I found a blog where much of this problem was explained (as there is no editorial..) but I was wondering if anyone could elaborate on how the blog writer used segment tree to solve this problem.. I could not figure that part out.

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any ideas?

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

I've used a segment tree to handle following queries:
1. modify (l, r, x) : for each l <= i < r, a[i] = x
2. get (i) : return a[i]
Look at my code : 7839071
Tell me, if you didn't understand some part of it!

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

    I see that, somehow, you are greedily pushing numbers into the answer vector, once you arrive at the indice i. Why is that optimal?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      You can prove this using induction on n.
      Consider any optimal sequence b1, b2, ..., b4k.
      If my output is m1, m2, ..., m4k', obviously if k ≥ 1, then k' ≥ 1 (Because I'll find b1, b2, b3, b4 greedily!)
      Induction step: My solution has guaranteed that positionm4 ≤ positionb4. By induction hypothesis, my solution will find an answer with length equal to 4k - 4 for the rest of the array (apositionm4 + 1, apositionm4 + 2, ..., an) and by adding them after m1, m2, m3, m4, we have an answer of length equal to 4k!
      (Sorry for my bad English ... Tell me if it's unclear!)

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Ok, this is clear now. Can you explain how you are using the "modify" and "get" commands to match numbers between the indice i and the next occurrence of i. To elaborate on this question:

        Say you have numbers:

        1 2 1 3 2, and we are at indice 1, and obviously next[arr[i]] is indice 3. How do you match the middle 2, at indice 2, to the outer 2 at indice 5?

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          We'll have another array s.
          When we're at indice 1, we won't do anything because it's the first occurrence of 1.
          (Also indice 2 is the same)
          When we're at the indice 3, we modify s[2] = 1 (We modify the segment between last occurrence of a[i] and i to a[i])
          So when we're at the indice 5, we'll have a look at the last occurrence of a[i]! In this case, s[last[a[5]] = 1. So we know the last 2 is surrounded by two '1's and we found 1 2 1 2.

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

            Ahhh I finally got it :). Thank you so much. May I ask, what was the motivation behind that solution?

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

              I'm glad that it helped. :)
              First of all I tried to find some subsequence of the input (Not the largest one) that satisfies the given conditions. During that process, the greedy solution comes in my mind and then the the only problem was "how to find the first abab fast?". After that I used some kind of dfs to find the idea and it just worked well!

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        "My solution has guaranteed that positionm4 ≤ positionb4" could you explain this part more clearly? I mean, I understood the line before this, that is if k>= 1, then k' ≥ 1-but don't get how this leads to the conclusion that position of m4 <= position of b4