Gyanpapi's blog

Send help

By Gyanpapi, history, 4 months ago, In English

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.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

This was my submission ->

My submission

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 3   Vote: I like it +2 Vote: I do not like it

    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

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

      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?

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

        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 :(

        → Reply
»
4 months ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

finally solved ,thank you to all for helping (https://atcoder.jp/contests/abc364/submissions/56107986)

→ Reply