Wesley's Anger Contest 3 Problem 5 - Triangle: The Root of All Evil

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 1.0s
Java 2.0s
Python 3.0s
Memory limit: 512M

Problem types

In a parallel universe, the least important data structure in computer science is the triangle. In fact, it is widely frowned upon to have a triangle in any way, shape, or form. As you are reading this the problem author is being locked up behind bars for mentioning the forbidden shape.

You were recently given a shipment of N rods for building structures. The i^{th} rod has an integer length of l_i and a value of v_i. To prevent a catastrophe, you need to remove some rods such that no triangles of positive area can be formed using any 3 of the remaining rods. Not wanting your money to go to waste, what is the minimum sum of values of the removed rods used to prevent a catastrophe?


For this question, Python users are recommended to use PyPy over CPython.

For this problem, you will NOT be required to pass all the samples in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N \le 5\,000
1 \le l_i \le 10^9
1 \le v_i \le 10^9

Subtask 1 [10%]

1 \le N \le 15

Subtask 2 [30%]

1 \le N \le 400

Subtask 3 [20%]

v_i = 1

Subtask 4 [40%]

No additional constraints.

Input Specification

The first line contains a single integer N, the number of building rods.

The next N lines describe the rods. The i^{th} line contains 2 integers, l_i and v_i, indicating that the i^{th} rod has a length of l_i and a value of v_i.

Output Specification

Output an integer, the minimum sum of values of the removed rods used to prevent a catastrophe.

Sample Input 1

7 9
1 1
3 5
9 2
5 3

Sample Output 1


Sample Explanation 1

While it is possible to remove rod 1 and fix the shipment with a cost of 9, it is cheaper to remove rods 4 and 5, making the optimal answer 2+3 = 5.

Sample Input 2

1 1
3 1
2 1
6 1
4 1

Sample Output 2


Sample Explanation 2

It is optimal to remove rod 5 for a cost of 1 in order to make it triangle-free.


There are no comments at the moment.