samurai123's blog

Doubt in problem "Google Code Jam" 277D
By samurai123, 6 years ago, In English

Happy new year all. I was solving this Problem which uses idea of dp+sorting. I saw it's editorial and somewhat understood. In editorial it is mentioned that we will calculate answer by knapsack dp. Other fact mentioned in editorial is that we will always use every small items before any large items to minimize penalty. But, I have doubt that in knapsack dp,we are not considering this fact.How can we be sure that the order we took by dp will minimize penalty as we are taking some large items before some small items in dp without violating constraints? Thanks in advance.

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

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

In traditional Knapsack, you have two choices: Take the object or leave the object.

In this problem, you have three choices: Do not solve small, solve only small or solve small as well as large. So you have to consider all 3 recurrences. Note here that my one "knapsack object" in this problem is NOT "small" or "large" individually, but the complete problem ("small"+"large"). This is how the order of small and large is ensured.

Accepted solution: 46427733

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

    But in editorial,it is mentioned that it is always optimal to take all small first before large i.e. if we have to take A1(small),A1(large),B1(small),B1(large) optimal ordering will be to take both small first before any small large. How that fact is covered? In the dp you mentioned,we can take some small and large and again take small of some other problem. Won't it always be optimal to take every small before any large?

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

      That part will be covered in the recurrence. While processing a problem, you'll consider the small part to be solved in the beginning and large part at the end.

      You may prefer this submission instead: 46427462

      It is not as precise but logically, it's the same.

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

        Looking to your submissions and some other, I think I have misunderstood something. I think that if we will never take any large before small. That means that all our order will be S,S,S,S,...,L,L,L, S=Small L=Large and S,L,S,S,L, or other(Large before small) will not be optimal. Is this correct?

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

          Yes, it is (almost) correct. S,L,S,S,L may be optimal but not better than S,S,S,L,L. That's the gist of exchange argument (sorting+dp). There might be other order which is as optimal as your order, but it can't be more optimal. So, yes, our solutions will be of the form S,S...S,L,L...L.

          → Reply