Baltic OI '15 P6 - Tug of War

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.0s
Java 2.0s
Memory limit: 256M

Problem type
Baltic Olympiad in Informatics: 2015 Day 2, Problem 3

Tug of war is a very popular sport in Byteland. The rules are easy: two teams pull a rope in opposite directions. The annual Byteland tug of war charity is taking place, and a lot of contestants have signed up. As the fair play commissioner, your job is to divide the contestants into two teams, such that the game can go on for a long time.

Since a total of 2n contestants have signed up, each team will consist of n contestants. The rope has n spots on the left side and n spots on the right side. The tug of war elite of Byteland are a picky bunch: each contestant has exactly one spot on the left side of the rope and one spot on the right side that he or she wants to use. Furthermore, you know the strength of each contestant.

The organizer has now asked you the following: Given an integer k, is it possible to create two teams, such that each team has n contestants, each contestant uses a spot that he or she wants to use (of course no two contestants share a spot), and the sums of strengths of the two teams differ by at most k?

Input Specification

The first line of input contains a positive integer n, specifying the number of spots on each side of the rope, and an integer k \le 20n, specifying the maximum difference of teams' strengths. For simplicity, we number the contestants from 1 to 2n. Each of the following 2n lines describes one contestant: the i-th of these lines contains three positive integers l_i, r_i and s_i (1 \le l_i, r_i \le n, 1 \le s_i \le 20), which specify that contestant i has strength s_i and wants to use either spot l_i on the left side of the rope or spot r_i on the right side of the rope.

Output Specification

In the first and only line of output your program should write either YES or NO, depending on whether it is possible to create two teams satisfying the requirements stated above.


SubtaskConditions (in each test case)Points
1n \le 1018
2n \le 200030
3n \le 30\,000, s_i = 123
4n \le 30\,00029

Sample Input 1

4 1
1 1 1
2 1 2
2 2 8
1 2 2
3 3 5
3 3 2
4 4 1
4 4 2

Sample Output 1


Explanation for Sample 1

In the first example we can assign contestants 1, 3, 6 and 7 to the left side (which results in a team of strength 1 + 8 + 2 + 1 = 12) and contestants 2, 4, 5 and 8 to the right side (which results in a team of strength 2 + 2 + 5 + 2 = 11). The difference of strengths between teams is 1.

Sample Input 2

2 5
1 1 1
1 2 4
2 2 1
2 1 4

Sample Output 2


Explanation for Sample 2

In the second example both players of strength 4 have to be in the same team, thus the minimal difference of strengths between teams is 6.


There are no comments at the moment.