notsoawesome's blog

Please help, want to know error in my code.
By notsoawesome, history, 6 weeks ago, In English

Hi there, apologies for a newbie post. I wanted to know error (possibly corner case) in my code. It would be really heplful.

Actually I want to get back in to competitive programming. Most of the time, I was able to find the corner cases to my error prone code, but since I lost the habit of doing competitive, I am having trouble with this simple thing.

Here is the problem: https://codeforces.com/contest/1935/problem/C

And here is my code: https://codeforces.com/contest/1935/submission/251937077

What I tried to do is simple. Sort in terms of b, and then finding the appropriate a's between two indexes and brute forcing it across the array to get the maximum.

In order to find a efficiently, I used multiset.

  • first optimizing as per the lowest possible a's and removing the largest
  • and then adding whatever we can

It would be really helpful. Thanks!

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

»
6 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

For a C++ multiset, if the parameter of .erase() is a value (i.e. integer, string, etc.) rather than an iterator, every instance of that value inside the multiset is erased. For instance, if a multiset a contains $$$[2, 3, 3, 5]$$$, after a.erase(3); is called, a would contain $$$[2, 5]$$$ only.

If you only want to erase one instance of a value (i.e. make a equal $$$[2, 3, 5]$$$), you need to call a.erase(a.find(3)). Inputting an iterator into the .erase method makes it erase one element only.

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

    Damn. Such a silly overlook. Thanks for your guidance man.

    If I may ask, recently I often get stuck incase my code fails at some large testcase. Not sure how to approach and solve it, in-case I am not able to find a corner case. Any tips to better tackle that problem?

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

      Write a random test generator, write a very slow but certainly correct solution (usually some exponential bruteforce), and then run an infinite loop of generating a test, solving it with both solutions, and comparing outputs. Whenever the output is different you save that test and terminate. Run this with small constraints on your generator and you have a corner case.

      Practice doing this every time you get stuck in debugging and you'll improve a lot.

      → Reply
      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        That's so helpful. I have seen the idea of stress testing things floating around, but never understood how they'd be be testing without "correct" answers. But now I get it, that we can write precise correct code. Thanks!

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

          Yes, exactly. It is a very useful skill to develop. Make sure you write the slow solution freshly — it is tempting to copy parts of the main one that you think are "surely correct", but it's not worth the risk.

          Also even if the slow solution isn't very easy and you have a bug in it, it's probably a different bug compared to your main solution, so you'll still get differences and will be able to investigate. There were many times in which I've made a mistake in my slow "correct" solution and had to fix that before being able to fix my main one. As long as you're getting differences on small tests — you can fix something.

          If you really do this often you'll start doing it so quickly that you'll be able to apply it on live rounds, too (or especially in longer onsite competitions).

          → Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

And for the negative voters, sorry if this is not welcomed. I already wasted so much time on this, so I thought of asking help.

→ Reply