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://mirror.codeforces.com/contest/1935/problem/C
And here is my code: https://mirror.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!
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 multisetacontains $$$[2, 3, 3, 5]$$$, aftera.erase(3);is called,awould contain $$$[2, 5]$$$ only.If you only want to erase one instance of a value (i.e. make
aequal $$$[2, 3, 5]$$$), you need to calla.erase(a.find(3)). Inputting an iterator into the.erasemethod makes it erase one element only.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?
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.
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!
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).
Thanks man, was just able to do this for one of the recent blockers.
Well, I want to get back in the competitive scene and get a better color, but still I don't think I could've done it in live rounds, but I can see with enough practice, this can be improved.
Good job. It will take time to be comfortable enough to do it on live CF rounds (e.g. it usually takes me less than 10 minutes to get it running, I did this for 3 different problems in the last round I participated), but it's invaluable for debugging when practicing or for longer-format competitions (i.e. IOI format allows this a lot more than CF format)
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.