HCI '16 - Serial Killer

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 32M

Authors:
Problem type

The Serial Killer kidnaps N people. These people were given a box each. Each box has different sizes. You can say they were measured in X and Y cm. The Serial Criminal is very demanding. He wants the victims to stack their boxes such that each box fits into another. Since the box may not necessarily fit into one another, the Serial Criminal wants the victims to maximise the number of boxes put in such a manner. However, as the Serial Killer takes out his gun, he declares that he will give the victims only a few minutes to figure out how, if not he will shoot a person in the crowd. The victims depend on you as you can devise a program to do this quickly.

Note that for one box to be fitted into another box, X and Y of that box must be strictly smaller than the other box's X and Y value.

Input Specification

Line 1: N

Line 2 to N+1: X and Y for each box, separated with a space

Output Specification

Line 1: The maximum number of boxes fitted in this manner possible. Answers are guaranteed to be less than 10\,000.

Constraints

Subtask 1 [5%]

1 \le X, Y \le 20

1 \le N \le 50

Subtask 2 [10%]

1 \le X, Y \le 100

1 \le N \le 250

Subtask 3 [20%]

1 \le X, Y \le 200

1 \le N \le 1000

Subtask 4 [25%]

1 \le X, Y, N \le 10\,000

Subtask 5 [40%]

1 \le X, Y, N \le 100\,000

Subtask 6 [0%]

Sample test cases.

Sample Input 1

4
2 3
3 4
4 5
2 2

Sample Output 1

3

Sample Input 2

10
9 6
8 3
7 1
7 6
2 10
2 1
1 8
10 4
5 3
8 7

Sample Output 2

4

Explanation for Sample Output 2

Boxes of 8 7, 7 6, 5 3, 2 1 can be fitted.


Comments


  • 0
    maxcruickshanks  commented on Feb. 20, 2023, 1:49 a.m.

    Since the original data were formatted incorrectly, the test case was updated, and all submissions were rejudged.