Блог пользователя Gyanpapi

Send help

Автор Gyanpapi, история, 4 часа назад, По-английски

https://atcoder.jp/contests/abc364/tasks/abc364_e Recent at coder problem.

I really can't process this problem, may be because it is 3D, can anyone explain it? Or suggest me similar problems where we need to work with 3 variables.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 часа назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This was my submission ->

My submission

→ Ответить
  • »
    »
    3 часа назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    I have added some comments in the above submission to make it easier to understand.
    Basically, you first of all make the observation that n is 80. And that the standard dp knapsack approach won't work as the x and y range to 1e5, thereby giving MLE and Runtime error for 3D dp table.
    So what you do to tackle it is, instead of thinking of maximizing the number of dishes, you try to minimize the saltiness value for each sweetness value from 0 to x. Once you have done that, you can see that all you need to do is print the maximum number of dishes which has saltiness lesser than or equal to the given max tolerable value of saltiness

    → Ответить
    • »
      »
      »
      3 часа назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Your code is readable for me ,was searching for it,thanks a lot

      By the way ,do you know any similar problem? How you come up with this solution like swapping state?

      → Ответить
      • »
        »
        »
        »
        3 часа назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I was sadly not able to solve the question in contest, and had to read the editorial only to get the idea :(
        I myself am just beginner in dp, so I am not aware of many such problems :(

        → Ответить
»
2 часа назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

this is something i learned lately whenever u have a dp lets say for this problem its bool dp[ans][sweetness][saltiness] change the dp to int or anything that fits instead of bool and take away one of the states for example we can say dp[sweetness][salitness] max ans for these 2 but its not optimal for this problem as both sweetness and saltiness go up to 1e4 but the answer doesnt so instead remove one of the 1e4 states and add the answer which only takes 80 so now we have dp[i][j] minimum saltiness for the answer to be i and sweetness to be j same solution but its up to you on which state u take away also its not always the bigger states sometimes its helpful to take away a small one if taking away the bigger one makes the implementation harder although in some problems u need the smallest states also for this problem i think a sorting greedy idea works in making the dp linear

anyways here is my submission

https://atcoder.jp/contests/abc364/submissions/56097091

→ Ответить