cached's blog

Stuck on a problem (Matryoshka Dolls)
By cached, 10 years ago, In English

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?

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

»
10 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

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

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

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

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

      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

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

        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 ?

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

          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)

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

            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.

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

              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.

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

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

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

      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?)

      → Reply