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.
Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official.
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | -is-this-fft- | 148 |
| 5 | SecondThread | 148 |
| 5 | atcoder_official | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 9 | TheScrasse | 144 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2024 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: Jul/22/2024 07:27:15 (g1).
Desktop version, switch to mobile version.
Supported by
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
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?
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.
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?
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.