ammar_hammoud's blog

Summer sell-off problem
By ammar_hammoud, history, 9 months ago, In English

Hello CF community, I'm trying to solve this problem 810B - Summer sell-off, and here's my submission 216849580, Although the code gives AC for the first $$$15$$$ test, it gives a WA on the $$$16$$$-th test, I'm not able to identify the issue, any ideas?. I don't want another solution, I just want to know what's wrong in my solution.

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
9 months ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Fixed your code!

You just need to maximize the profit that you can achieve after doubling the amount. No need to check for other conditions. So you can simply find the difference between the sale on ith day if you double and if you don't. Then sort the values in non increasing order and take the doubled values for the first f and the actual values for the rest.

Here is the link for the code : this

Also, I think the problem with your code is that you are not checking for f maximum profits, but for f maximum values (both are different). Hence you are getting a WA verdict.

Hope it helps!

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

    Thank you!
    $$$1$$$. I assumed that if a pair has products more than customers, there's no need to double.
    $$$2$$$. then I added the products I that could be sold (doubled and took the $$$min$$$).
    $$$3$$$. then I sorted these values for the $$$max$$$ to be first.
    $$$4$$$. iterate over the vector and took the first K (which are $$$max$$$).
    $$$5$$$. for the rest element of the vector I took the the $$$min$$$ because I cannot double anymore.
    Would you please specify in any point I'm wrong?, and would you please give me a test case with small input that demonstrate the mistake in my code, because I'm still thinking if this problem appeared while I'm in contest, this would be the very first way I think of. I tried to implement the solution exactly as the problem says. Another time thanks for helping

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

      The first assumption is correct because doubling in the first case gives no profit.

      The second point is also correct.

      The problem comes in the third step :

      Take this test case for example :

      2 1

      4 9

      6 9

      your code will give output 13 but the answer is 17 (check for yourself). The wrong answer is because you are checking for max value. Instead of this check for max profit you can receive -> for 4 it is 4 and for 6 is 3. So you will double 4 instead of 6, even if the latter gives more value when doubled (9 compared to 8).

      I hope this clears your doubt.

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

        For the first pair, there's no need to double. for the second you can double $$$4$$$ and get $$$min(2\cdot 4, 9) = 8$$$, for the last $$$min(2\cdot 6, 9) = 9$$$, giving total of $$$1+8+9=18$$$. (this for $$$k=3$$$).
        I've tried this test on both of our codes, for $$$k = 3, 2$$$ it gives the same result, but for $$$k = 1$$$ yours gives $$$15$$$, mine gives $$$14$$$. I may be stupid, but why are subtracting the min(f, s) from min(2*f, s)?, wouldn't the answer be just min(2*f, s) as we doubled already?

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

          Firstly in the above test case 2 1 represents n and f respectively

          I am subtracting min(f, s) to calculate the profit. It represents the difference between the cases when I am doubling on that day on compared to when I am not doubling it.

          That's why while adding to the answer I am again adding min(f, s). If we just keep v.first as min(2*f, s), it means we are sorting the days based on maximum value and not on maximum profit. That is the main cause of the wrong final answer. By keeping the v.first as min(2*f, s) — min(f, s), I am sorting the days based on highest profit.

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

            Oooh!, I see, what I'm missing is that how to calculate the profit, I've just calculated the number of products that could be sold.
            Thank you so much!

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

              Glad you understood!

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                13 days ago, # ^ |
                  Vote: I like it +3 Vote: I do not like it

                I was just practicing this problem and was so stuck, but your comments really helped AnikateKoul :)

                → Reply