ko_osaga's blog

DP Optimization Challenge from Korean OI
By ko_osaga, history, 9 years ago, In English

I got a nice problem from Korean OI : https://www.acmicpc.net/problem/2300 .

Since deriving recurrence is not the point of this topic, I will give you the formula :

  • N <= 10000

  • 0 <= Xi <= X(i+1) <= 10^9, (1 <= i < N), 0 <= Yi <= 10^9 (1 <= i <= N)

  • DP[i] = Min(DP[j] + Cost(j+1, i))for all j < i. when Cost(s, e) = Max(X[e] — X[s], Max(Y[s], Y[s+1] ... Y[e]))

The goal is to calculate DP[N] — and O(N^2) solution is quite straightforward.

However, I heard that there is a subquardatic solution to this problem! I tried various strategies to solve it, but failed.

Does anyone have a hint / idea to the subquadratic solution?

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

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

Seems too easy, maybe you missed some constraint. For sure we can say that lower bound on DP[N] is X[N]-X[1] because of the cost function. Now we have two cases, let Ym = max(Y1, Y2, .., YN): Ym <= X[N]-X[1] -> then we can achieve the lower bound by saying DP[N] = DP[0] + cost(1, N) = X[N]-X[1]. Ym > X[N]-X[1] -> now that also means Ym > X[j]-X[i], for every i,j pair. So at least one of the cost functions on our path from 0 to N will be equal to Ym. That means lower bound on DP[N] is Ym. But again we can achieve that by DP[N] = DP[0] + cost(1, N) = Ym.

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

    I think I've just read the problem, and, if I uderstood right, in the formula of Cost (s, e) should be the minimum length of a square containing those points, so Cost (s, e) = max (X[e] — X[s], max (Y[s], Y[s + 1], ..., Y[e]) — min (Y[s], Y[s + 1], ..., Y[e]))

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

      We don't have to subtract minimum since every square's center should be fixed at x-axis. With slight modification we can get the above recurrences.

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

    Thanks for replying!

    However, the lower bound of DP[N] is not X[n] — X[1]. since the formula is DP[j] + Cost(j+1, i) — not DP[j] + Cost(j, i). for example, if Ym = 0, then the answer is zero.

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

      You're right, I saw cost(j, i) in the dp recurrence. But even then, is it the cost function geniucos wrote or the one in the blog post?

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

        No, the cost function is same as the blog post. (it doesn't subtract minimum)

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

          Sorry for misunderstanding. Still, none of the recurrences I've tried returned the right answer on the sample. Is dp[0] = 0? Is it really maximum of y or of |y| ? I implemented your reccurence and I'm getting the answer 4...

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

            dp[0] is zero.

            since we will cover the points with rectangle [X, X+P] x [Y-P/2, Y+P/2], it is the maximum of 2|y|.

            Accepted code at acmicpc.net : http://ideone.com/w7ERW0

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

              Thanks. I've just got AC(I hope I'm not that sure because it is in korean, but it is some green writing :)) ). Are you sure there exist a subqudratic solution? It seems interesting, but in this case, why didn't they put some bigger constraints?

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

                I guess it's a green writing with "맞았습니다!!" ( = Accepted.). No other green writing will appear as a verdict :)

                This problem appeared as an "easiest" problem to KOI (specifically, high school division) at that time. So probably they had lower the constraint to match the difficulties (and propose another problem at "hardest" level.)

                I'm not 100% sure that subquadratic solutions exist, but AFAIK this problem had appeared in an old IOI Korean team selection test. I remember that I heard it in a Slack chatgroup of Korean problem solvers.

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

    The problem is that you really can't say that lower bound is x[N] — x[1]. You cand choose the partition (1, 2) (3, 4) and, if y = 0 for all, it gives you a cost lower with x[3] — x[2] than X[N] — X[1]

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Seems that I could solve it in O(n log^2 n). Main idea that problem for Cost(s, e) = X[e] — X[s], could be solved easily by keeping DP[j]-X[j+1], for Cost(s, e) = Max(Y[s], Y[s+1] ... Y[e]) by segment tree with maximum on DP[j]+Max(Y[j+1], ... Y[i]) and multi-addition operation (when maximums on current suffixes of Y increases you should add difference on suffix of suffixes. Invariant is that if two maximums became same they became same forever and all future adds could be done as multi-adds). So we need separate cases where X[e] — X[s] < Max(Y[s], Y[s+1] ... Y[e]. It could be done by two-dimentional segment tree in the similar manner as described above for case Cost(s, e) = Max(Y[s], Y[s+1] ... Y[e]).

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

    Thanks for sharing your ideas! btw I have some questions for your algorithm.

    If we can separate every value into X[e] — X[s] <= Max(Y[s] .. Y[e]), we can solve this problem. However, I think some value will "oscillate" for O(N) times — like, X[e] — X[s] <= Max(Y[s] .. Y[e]) but X[e+1] — X[s] >= Max(Y[s] .. Y[e]) and so on.. this will require O(N^2) updates.

    If we don't separate every value into X[e] — X[s] <= Max(Y[s] .. Y[e]), It's not clear how can we solve this problem.

    Also, I don't get why 2d segment tree is needed for such operation. Can you tell me what am I missing?

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

Disclaimer that it's 4am here, so my idea may make sense or not:

Let's write max(Yj, Yj + 1, ..., Yi) = Y(j, i). When we are processing i, for every j we want to know if Y(j, i) >  = Xi - Xj, or Y(j, i) - Xj ≥ Xi. So we can use two trees: one stores min value of dp[j] + Xj - Xi for every interval of Y(j, i) - Xj, the other one stores min value of dp[j] + Y(j, i) for every interval of Y(j, i) - Xj, and then finding the optimal value of dp[j] can be reduced to simply querying both trees (you can do it in a single tree of course, but I'm saying two for simplicity).

Of course, Y(j, i) can change when we change i. We can fix this by updating our trees, removing j from both trees, calculating the new value of Y(j, i) - Xj, and adding it again. But wait, every Y(j, i) can change n times, so this is even worse than if you simply do the loop.

So let's exploit one property of Y(j, i) mentioned by zeliboba -- namely that once two maximums become equal they become equal forever. Every time Y(j, i) changes, group of k with Y(k, i) = Y(j, i) necessarily increases size. If this group becomes larger than , let's create separate trees specifically for this group, remove all j inside group from the global trees and add all j in group to these group trees.

Now we have interesting property: whenever Y(j, i) changes for one element in the group, it changes for all other elements of the group, so the order in the group tree remains the same. That means that group tree will never need to be updated again (unless a new j enters the group, in which case it should be added to the group tree). Whenever you're querying for the best j for a certain i, you now need to check the generic tree and all group trees for the optimal value.

Complexity analysis: Because each change increases group size, each element j changes Y(j, i) at most times before it enters a group of more than elements. When querying for the minimum value, we will need to query at most trees (general trees and group trees). So we can see both queries and updates are bound by .

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

    Cool solution, it is easier to implement, than what I've suggested.

    → Reply