STUDCOMP
Author: sigma_g
Tester: multiple, see announcement
Editorialist: sigma_g
DIFFICULTY:
EASY
PREREQUISITES:
Sets
PROBLEM
Determine - for each j - whether a set of indices exists such that all elements in it have m_i lower than that of m_j, but their sum of a_i is larger than that of a_j.
Buggy code plain text
QUICK EXPLANATION
Spoiler
The code uses set whereas it should be using multiset, for the appreciation values.
EXPLANATION
Step 1
Note that there are other possible decoy bugs in this problem. For example, you might think the complexity of the inner loop (for (auto x : apps) ) is linear in n , and consider this problem a candidate for TLE. However, the inner if condition will break within 20 iterations (as 20 >= a[i] >= 1 , so there is no TLE in this problem.
Step 2
Note that there might be duplicates in the appreciation values a . Is there a bug in the code related to this?
Step 3
The set<int> apps has to be a multiset<int> . Any careful testcase with repeating values of a will exploit this, for example:
3
2 3 4
4 4 7
But not all repeating values will work, for example, something simpler like:
2
2 3
4 4
doesn’t hack the buggy solution.
Setter’s solution
Text
5
1 1 1 1 10
5 5 5 5 20