An Animal Contest 1 P6 - Alpaca Distancing

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 0.5s
Java 1.5s
Python 1.5s
Memory limit: 256M

Problem types

William the Alpaca is arranging a socially-distanced party with N potential invitees. He would like to invite all of them, but alpacas are picky and they each have their own requirements. First, each alpaca demands to stand at a position a_i, occupying a point on a straight line. On top of that, due to the rise of a nasty disease, ALPACAVID-19, each alpaca has a range of b_i, meaning they won't tolerate another alpaca being strictly less than b_i units from their position. William wants to invite as many alpacas as possible, such that each invited alpaca satisfies the range requirement of every other invited alpaca. Help William find the maximum number of alpacas he can invite!


1 \leq N \leq 10^5

1 \leq a_i, b_i \leq 10^9

Subtask 1 [10%]

1 \leq N \leq 8

1 \leq a_i, b_i \leq 20

Subtask 2 [10%]

1 \leq N \leq 2\cdot10^3

1 \leq a_i, b_i \leq 10^6

Subtask 3 [50%]

1 \leq a_i, b_i \leq 10^6

Subtask 4 [30%]

No additional constraints.

Input Specification

The first line contains one integer N.

The next N lines contain a_i and b_i for the i^{th} alpaca.

Output Specification

Output one integer, representing the maximum amount of friends William will be able to invite.

Sample Input 1

4 2
14 4
7 5
3 3
13 1

Sample Output 1


Explanation for Sample 1

Alpaca 1 and alpaca 5 can be chosen. Alpaca 1's range reaches 4 + 2 = 6 and alpaca 5's range reaches 13-1=12, so they are out of each other's ranges. Hence, this is valid, and it can be shown that this is one of the optimal arrangements.

Sample Input 2

19 3
4 8
6 5
20 13
14 4
13 7
1 4

Sample Output 2


Explanation for Sample 2

The optimal alpacas to keep are Alpacas 1, 3, 5, and 7.


There are no comments at the moment.