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

# | User | Rating |
---|---|---|

1 | tourist | 3821 |

2 | Benq | 3744 |

3 | ksun48 | 3559 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3531 |

6 | Um_nik | 3488 |

7 | maroonrk | 3423 |

8 | Petr | 3379 |

9 | sunset | 3337 |

10 | ecnerwala | 3335 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 206 |

2 | Errichto | 181 |

2 | awoo | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 173 |

8 | tourist | 172 |

9 | SecondThread | 171 |

10 | rng_58 | 166 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/27/2021 16:20:48 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Have you solved the problem by now? If not, here is a hint.

Hint 1Let'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.

Hint 2Knowing 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]])$$$.

My implementationI wrote a blog about that problem months ago: https://codeforces.com/blog/entry/82625

Hope it helps ;)