I was solving a Codeforces problem yesterday. The problem’s URL is this
I will just explain the question in short below.
Given a binary string, divide it into a minimum number of subsequences
in such a way that each character of the string belongs to exactly one
subsequence and each subsequence looks like “010101 …” or “101010
…” (i.e. the subsequence should not contain two adjacent zeros or
ones).
Now, for this problem, I had submitted a solution yesterday during the contest. This is the solution. It got accepted temporarily and on final test cases got a Time limit exceeded status.
So today, I again submitted another solution and this passed all the cases.
In the first solution, I used HashSet and in the 2nd one I used LinkedHashSet. I want to know, why didn’t HashSet clear all the cases? Does this mean I should use LinkedHashSet whenever I need a Set implementation? I saw this article and found HashSet performs better than LinkedHashSet. But why my code doesn’t work here?
Advertisement
Answer
This question would probably get more replies on Codeforces, but I’ll answer it here anyways.
After a contest ends, Codeforces allows other users to “hack” solutions by writing custom inputs to run on other users’ programs. If the defending user’s program runs slowly on the custom input, the status of their code submission will change from “Accepted” to “Time Limit Exceeded”.
The reason why your code, specifically, changed from “Accepted” to “Time Limit Exceeded” is that somebody created an “anti-hash test” (a test on which your hash function results in many collisions) on which your program ran slower than usual. If you’re interested in how such tests are generated, you can find several posts on Codeforces, like this one: https://codeforces.com/blog/entry/60442.
As linked by @Photon, there’s a post on Codeforces explaining why you should avoid using Java.HashSet and Java.HashMap: https://codeforces.com/blog/entry/4876, which is essentially due to anti-hash tests. In some instances, adding the extra log(n) factor from a balanced BST may not be so bad (by using TreeSet or TreeMap). In many cases, an extra log(n) factor won’t make your code time out, and it gives you protection from anti-hash tests.
How do you determine whether your algorithm is fast enough to add the log(n) factor? I guess this comes with some experience, but most people suggest performing some sort of calculation. Most online judges (including Codeforces) show the time that your program is allowed to run on a particular problem (usually somewhere between one and four seconds), and you can use 10^9 constant-time operations per second as a rule of thumb when performing calculations.