Thornhill Computer Club 2024 - April Contest - Problem 7

The Thornhill Science Society have created a revolutionary new piece of magnetic technology: The Hyper Magnet. The Hyper Magnet operates within a unique framework: it can dynamically change its polarity to positive, negative, or neutral, depending on if the number of polar pairs between surrounding objects. A polar pair exists between two objects ~i~ and ~j~ if the sum of their polarity is less than or equal to the magnet strength ~S~ ~(p[i] + p[j] \le S)~. All polar pairs are pairwise distinct. This means that the pair of objects ~(i, j)~ is equivalent to the pair of objects ~(j, i)~. If the total number of polar pairs is greater than ~T~, the polarity of the magnet becomes positive. If the total number of polar pairs is less than ~T~, the polarity of the magnet becomes negative. Otherwise the polarity of the magnet becomes neutral.

For this magnet to truly be useful, it must be able to switch polarity from positive to negative, negative to positive, or to neutral. This can be done by simply changing the polarity of any number of objects surrounding the magnet, each to any non-negative integer ~(p[i] = v,~ ~v \ge 0)~.

Given the initial polarity of the ~N~ objects surrounding the hyper magnet , the strength of the magnet ~S~, and the polarity threshold ~T~, determine the minimum number of objects that need to have their polarity changed to reverse the polarity of the hyper magnet or set its polarity to neutral. If it is impossible to change the polarity of the magnet, output -1.

Input Specifications

The first line will contain three integers, ~N~, ~S~, and ~T~.
The next line will contain ~N~ space-separated integers representing the initial polarity of the ~i~th object surrounding the magnet.

Output Specification

Output the minimum number of objects that need to have their polarity changed to reverse the polarity of the magnet or set its polarity to neutral. If it is impossible to do so, output -1.

Subtasks

For all subtasks:

• ~1 \le N \le 10^5~
• ~0 \le S \le 2 \times 10^6~
• ~0 \le T \le 10^{11}~
• ~0 \le p[i] \le 10^7~

Subtask 1 [2/15]:

• ~N \le 10~
• ~S \le 200~
• ~T, p[i] \le 100~

Subtask 2 [2/15]:

• ~N \le 100~
• ~S, p[i] \le 1~
• ~T \le 10^4~

Subtask 3 [3/15]:

• ~N \le 4000~
• ~p[i], S \le 2 \times 10^4~
• ~T \le 2 \times 10^7~

Subtask 4 [8/15]:
No further constraints.

Sample Input 1

3 12 2
6 1 4

Sample Output 1

1

Explanation for Sample Output 1

Initially, the polarity of the magnet is positive. This is because there are a total of 3 polar pairs between surrounding objects, pairs [(6 + 1), (1 + 4), (4 + 6)], which is greater than the threshold of 2.

To flip the polarity or set the polarity of the magnet to neutral, the polarity of the objects can be set to 9 1 4, requiring exactly 1 change. The resulting magnet will have a negative polarity since the number of polar pairs between objects will be less than 2, pair [(1 + 4)].

Sample Input 2

7 10 21
1 3 6 7 2 4 5

Sample Output 2

2

Explanation for Sample Output 2

Initially, the polarity of the magnet is negative as there are exactly 17 polar pairs, which is less than the threshold of 21. To flip the polarity or set the polarity of the magnet to neutral, the polarity of the objects can be set to 1 3 5 5 2 4 5, requiring exactly 2 changes. This will make the new number of polar pairs exactly 21 which is equal to the magnet's threshold.

Sample Input 3

5 6 12
7 3 4 1 3

Sample Output 3

-1

Explanation for Sample Output 3

No matter how many objects have their polarity changed, it is impossible for the polarity of the hyper magnet to become positive or neutral.

Sample Input 4

15 30 60
4 2 19 10 7 3 1 15 11 17 16 6 12 14 18

Sample Output 4

3