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

Stuck on a problem (Matryoshka Dolls)
Автор cached, 10 лет назад, По-английски

Hello I cant solve this problem http://acm.student.cs.uwaterloo.ca//130928/D.html

seems to be a dynamic problem but I cant formulate it.

can anybody help me?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

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

Sort dolls by its overall storage capacity. Look, that dolls with lower capacity will be only inside in dolls with higher capacity. Why?

Let's assume that, in some optimal arrangement doll with H capacity is inside in doll with L capacity (H > L). Notice, that we can swap these dolls with any damage for our solution.

With that knowledge we can sort dolls and observe that they 'form' DAG, so it's solvable with DP

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

    But the states are too high to be in dp array dimension. What you are thinking about the dimentions(states) ?

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

      Iterate from dolls with lowest capacity to highest. Remember best result for each one from 1 to i. To get result for doll number i+1, find (cap[i+1]-weight[i+1) in sorted cap[] array. You can do it in O(logn). result[i+1] = result[j] + 1, j — found doll

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

        But for each nested doll the innermost doll weights are added. Where to keep this value ?

        Like if (A) is in (B) and (B) is in (C) then (A)+(B)<capacity(C).

        how to handle the current capacity/weight in dp state ?

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

          You don't have to keep it anywhere. This is dynamic part of solution :) Look, that A can be in B, if and only if cap(A) <= cap(B) — weight(B), in other words in B is enough place to store all capacity of A (and dolls inside it). So, for B, you look for A with the highest cap(A), which satisfy condition cap(A) <= cap(B) — weight(B) [my previous post].

          Why for the highest? Prove is in my first post :) if cap(A) >= cap(C) then result(A) >= result(C)

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

            Consider a case:

            7 12
6 13

            here capacity is sorted and according to cap(A) <= cap(B) — weight(B) the answer is 1. But we can get 2.

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

              Yes, you're right. After getting the result for i we should modify cap(i) to cap(j)+weight(i). In this case:

              7 12 (look for 5, not found)

              modify cap(0) to 7:

              7 7
6 13 (look for 7, found j=0)

              do not modify cap(1), because 6+7=13

              Good point.

              We modify cap(i), but it still will be in increasing order.

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

        This problem is slightly similar with spoj ROADS but the state is higher I think. I solved ROADS but ... not this time.

        → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      You're probably thinking of keeping states dolls[i][weight] that says how many dolls you can keep for every possible weight using only dolls from 0 to i.

      What if we think in reverse? Try keeping weight[i][d] instead (what is the least total weight I need to fit d dolls using only dolls from 0 to i?)

      → Ответить