RomeoFantastik's blog

COCI Contest 7 Last problem
By RomeoFantastik, history, 9 years ago, In English

Hello guys! Can anyone provide me please the solution for the last problem of the 7th round of COCI 2015/2016? :D

Link to the problem is here : http://hsin.hr/coci/contest7_tasks.pdf

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

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

Let's suppose first element of magic subarray is always smaller than the last. We can take care of the other case by reversing the array and running the same algorithm.

Therefore, to say [L,R] is magic, we have:

  1. a[L] is the minimum element of a[L..R]
  2. a[R] is the maximum element of a[L..R]

Let's maintain a segment tree that says for each index i <= R, what is the length of the biggest magic subarray that starts in i and ends in a position up to R.

Assuming the tree is in a correct state, when we increase R by 1, we only need to consider subarrays that end in new index R. Let's figure out which starting indices i are so that a[i..R] is magic:

Condition 1: For every index i, let Mi be the smallest index such that Mi > i and a[i] > a[Mi]. We have that condition 1 is satisfied for a[i..R] iff R < Mi. Note that whenever R passes Mi, i will never be a valid starting index anymore.

Condition 2: Let m be the largest index such that m < R and a[m] > a[R]. Clearly no subarray that starts before m and ends in R is magic, and also every subarray that starts after m satisfies condition 2, so for this condition R is only a valid ending point for m < i <= R.

For every i that satisfies both conditions, we should update tree[i] = R — i + 1. If we erase i from consideration when R = Mi, we can do this by lazy propagation in the interval m < i <= R. (If it is not obvious how to support the erasing operation, keep a value min_valid_start in the tree. Initially min_valid_start[i] = i for every i, and when i is erased, min_valid_start[i] = infinity.)

Having this tree, it should be simple to get answer to all queries after sorting them in order of increasing R.

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

    Awesome! Thanks a lot!

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

    I also have a question. When you want to make lazy propagation, you have some R values which for some segments should be updated, but these R values are others that our current R, so the min_valid_start in those nodes are others than they were for that R values, and we can't update the node with our current values, we need the old ones. How do you solve this? Do we need a persistent tree or something?

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

      This will not happen, actually. When you erase a certain i, you will also visit every node that had its min_valid_start changed, so all updates that remain have no changes to min_valid_start.

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

        Yes, min_valid_start are also ok, but I was talking about the solution for every node, this soluiton we process by lazy update, but when we have to propagate it, we will eventually modify it by some R1 — min_valid_start + 1 , but this min_valid_start is not the one we have for the current R, is the one for R1 and we no more have that value.

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

          That's the question I answered. Read the answer again.

          Edit: Specifically, "min_valid_start is not the one we have for the current R" is impossible to happen.

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

            We always have the min_valid_start for our current R, right?

            We may when we propagate the answer to need this information for older R's.

            → Reply