STUDCOMP - Editorial

STUDCOMP

Contest
Practice

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

Pastebin

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