# STUDCOMP

Author: `sigma_g`
Tester: multiple, see announcement
Editorialist: `sigma_g`

EASY

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.

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
``````