I was trying to solve jelly from last year(and this year) practice contest. First 4 subtasks are very easy but i don't have any idea about the last 2 subtasks. Can anyone share their solution.
Thank you in advance.
Current Progress: (if it matters)
I was trying to solve jelly from last year(and this year) practice contest. First 4 subtasks are very easy but i don't have any idea about the last 2 subtasks. Can anyone share their solution.
Thank you in advance.
I was hoping that there's a greedy for the full solution since constraints seemed too big for dp. But looking at submissions from oj.uz there seems to be a dp solution. On greedy, i tried to always use the shop with highest money and failed.
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
2 | adamant | 164 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Name |
---|
Have you solved the problem by now? If not, here is a hint.
Let's sort the jelly flavors such that their $$$a$$$ values are non-decreasing. We will call a particular way of buying the flavors at stores A and B a solution (each flavor is either bought at store A, store B, or not bought at all). A maximal solution is a solution for which the number of bought flavors is maximal. For a particular solution, let $$$j$$$ be the largest index of all flavors that were bought at store A.
You can now prove the following statement: There always exists a maximal solution such that all flavors with an index $$$<j$$$ are bought at one of the two stores.
Proof: Consider any maximal solution $$$S$$$. If it satisfies the said property, we are done. If it doesn't, we will construct a new maximal solution $$$T$$$ that satisfies the property:
- We buy all flavors that are bought at store B in solution $$$S$$$ also at store B.
- We buy the first $$$u$$$ flavors with the smallest indices (that are not already bought at store B) at store A, where $$$u$$$ is the amount of flavor bought at store $$$A$$$ in solution $$$S$$$. Because all flavors bought at store A have the smallest indices available, there will be no flavor with index $$$<j$$$ that is not bought. Since the flavors are sorted such that their $$$a$$$ values are non-decreasing, solution $$$T$$$ will spend not more money at store A than solution $$$S$$$ does, and therefore $$$T$$$ is a valid solution. The amount of flavors bought is the same for $$$S$$$ and $$$T$$$ and thus $$$T$$$ is also a maximal solution.
$$$T$$$ therefore satisfies the desired property.
Knowing that a maximal solution with this property always exists, we can design a DP-algorithm for solving the problem. Using DP, we can calculate two arrays of values:
- $$$DP_1[i][a]$$$: The minimal amount of dollars $$$b$$$ for which you can buy all flavors with an index $$$<i$$$ using at most $$$a$$$ dollars at store A and at most $$$b$$$ dollars at store B
- $$$DP_2[i][b]$$$: The maximal amount of distinct flavors with an index $$$\geq i$$$ that you can buy using at most $$$b$$$ dollars at store B The recursive formula for these values should be easy to derive. Finally, the answer will be $$$\max\limits_{0\leq i\leq n}\max\limits_{0\leq a\leq x}(i + DP_2[i][y - DP_1[i][a]])$$$.
I wrote a blog about that problem months ago: https://codeforces.com/blog/entry/82625
Hope it helps ;)