The Hard Work of Paparazzi
Contest: Codeforces Global Round 11
Difficulty rating: 2000
Tags: dp

You are a paparazzi working in Manhattan.

Manhattan has $$$r$$$ south-to-north streets, denoted by numbers $$$1, 2,\ldots, r$$$ in order from west to east, and $$$r$$$ west-to-east streets, denoted by numbers $$$1,2,\ldots,r$$$ in order from south to north. Each of the $$$r$$$ south-to-north streets intersects each of the $$$r$$$ west-to-east streets; the intersection between the $$$x$$$-th south-to-north street and the $$$y$$$-th west-to-east street is denoted by $$$(x, y)$$$. In order to move from the intersection $$$(x,y)$$$ to the intersection $$$(x', y')$$$ you need $$$|x-x'|+|y-y'|$$$ minutes.

You know about the presence of $$$n$$$ celebrities in the city and you want to take photos of as many of them as possible. More precisely, for each $$$i=1,\dots, n$$$, you know that the $$$i$$$-th celebrity will be at the intersection $$$(x_i, y_i)$$$ in exactly $$$t_i$$$ minutes from now (and he will stay there for a very short time, so you may take a photo of him only if at the $$$t_i$$$-th minute from now you are at the intersection $$$(x_i, y_i)$$$). You are very good at your job, so you are able to take photos instantaneously. You know that $$$t_i < t_{i+1}$$$ for any $$$i=1,2,\ldots, n-1$$$.

Currently you are at your office, which is located at the intersection $$$(1, 1)$$$. If you plan your working day optimally, what is the maximum number of celebrities you can take a photo of?

Input format:
The first line of the input contains two positive integers $$$r, n$$$ ($$$1\le r\le 500$$$, $$$1\le n\le 100,000$$$) – the number of south-to-north/west-to-east streets and the number of celebrities.

Then $$$n$$$ lines follow, each describing the appearance of a celebrity. The $$$i$$$-th of these lines contains $$$3$$$ positive integers $$$t_i, x_i, y_i$$$ ($$$1\le t_i\le 1,000,000$$$, $$$1\le x_i, y_i\le r$$$)  — denoting that the $$$i$$$-th celebrity will appear at the intersection $$$(x_i, y_i)$$$ in $$$t_i$$$ minutes from now.

It is guaranteed that $$$t_i<t_{i+1}$$$ for any $$$i=1,2,\ldots, n-1$$$.

Output format:
Print a single integer, the maximum number of celebrities you can take a photo of.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
Explanation of the first testcase: There is only one celebrity in the city, and he will be at intersection $$$(6,8)$$$ exactly $$$11$$$ minutes after the beginning of the working day. Since you are initially at $$$(1,1)$$$ and you need $$$|1-6|+|1-8|=5+7=12$$$ minutes to reach $$$(6,8)$$$ you cannot take a photo of the celebrity. Thus you cannot get any photo and the answer is $$$0$$$.

Explanation of the second testcase: One way to take $$$4$$$ photos (which is the maximum possible) is to take photos of celebrities with indexes $$$3, 5, 7, 9$$$ (see the image for a visualization of the strategy):

- To move from the office at $$$(1,1)$$$ to the intersection $$$(5,5)$$$ you need $$$|1-5|+|1-5|=4+4=8$$$ minutes, so you arrive at minute $$$8$$$ and you are just in time to take a photo of celebrity $$$3$$$.
- Then, just after you have taken a photo of celebrity $$$3$$$, you move toward the intersection $$$(4,4)$$$. You need $$$|5-4|+|5-4|=1+1=2$$$ minutes to go there, so you arrive at minute $$$8+2=10$$$ and you wait until minute $$$12$$$, when celebrity $$$5$$$ appears.
- Then, just after you have taken a photo of celebrity $$$5$$$, you go to the intersection $$$(6,6)$$$. You need $$$|4-6|+|4-6|=2+2=4$$$ minutes to go there, so you arrive at minute $$$12+4=16$$$ and you wait until minute $$$17$$$, when celebrity $$$7$$$ appears.
- Then, just after you have taken a photo of celebrity $$$7$$$, you go to the intersection $$$(5,4)$$$. You need $$$|6-5|+|6-4|=1+2=3$$$ minutes to go there, so you arrive at minute $$$17+3=20$$$ and you wait until minute $$$21$$$ to take a photo of celebrity $$$9$$$.

Explanation of the third testcase: The only way to take $$$1$$$ photo (which is the maximum possible) is to take a photo of the celebrity with index $$$1$$$ (since $$$|2-1|+|1-1|=1$$$, you can be at intersection $$$(2,1)$$$ after exactly one minute, hence you are just in time to take a photo of celebrity $$$1$$$).

Explanation of the fourth testcase: One way to take $$$3$$$ photos (which is the maximum possible) is to take photos of celebrities with indexes $$$3, 8, 10$$$:

- To move from the office at $$$(1,1)$$$ to the intersection $$$(101,145)$$$ you need $$$|1-101|+|1-145|=100+144=244$$$ minutes, so you can manage to be there when the celebrity $$$3$$$ appears (at minute $$$341$$$).
- Then, just after you have taken a photo of celebrity $$$3$$$, you move toward the intersection $$$(149,379)$$$. You need $$$|101-149|+|145-379|=282$$$ minutes to go there, so you arrive at minute $$$341+282=623$$$ and you wait until minute $$$682$$$, when celebrity $$$8$$$ appears.
- Then, just after you have taken a photo of celebrity $$$8$$$, you go to the intersection $$$(157,386)$$$. You need $$$|149-157|+|379-386|=8+7=15$$$ minutes to go there, so you arrive at minute $$$682+15=697$$$ and you wait until minute $$$855$$$ to take a photo of celebrity $$$10$$$.

Example input:
10 1
11 6 8

Example output:
0

Example input:
6 9
1 2 6
7 5 1
8 5 5
10 3 1
12 4 4
13 6 2
17 6 6
20 1 4
21 5 4

Example output:
4

Editorial:
This is a classical dynamic-programming task with a twist. For the solution to work it is fundamental that the city has a small diameter (i.e., $$$r$$$ shall not be large) and that there are not simultaneous appearances.
We say that two celebrities $$$i<j$$$ are compatible if it is possible to take a photo of both, that is $$$$$$|x_i-x_j| + |y_i-y_j| \le t_j-t_i\,.$$$$$$
Let $$$ans_k$$$ be the maximum number of photos we can take of the first $$$k$$$ celebrities assuming that we take a photo of celebrity $$$k$$$ (if we cannot take a photo of celebrity $$$k$$$, then $$$ans_k:=-\infty$$$). It holds (assuming that we can take a photo of celebrity $$$k$$$) $$$$$$ans_k = 1 + \max\Big(0, \max_{\substack{1\le i < k,\\ \text{$i$ is compatible with $k$}}} ans_i\Big)\,.$$$$$$ This formula produces immediately a solution with complexity $$$O(n^2)$$$: we compute $$$ans_k$$$ for $$$k$$$ that goes from $$$1$$$ to $$$n$$$; for each $$$k$$$ we need just to compute the maximum of $$$O(k)$$$ values.
How can we speed up this algorithm? The idea is that if $$$|k-i|$$$ is big, then $$$i$$$ and $$$k$$$ are always compatible. More precisely, if $$$k - i \ge 2r$$$ then $$$t_k-t_i \ge 2r$$$ (because there are no simultaneous appearances) and therefore $$$$$$|x_i-x_k| + |y_i-y_k| \le 2r \le t_k-t_i\,,$$$$$$ so $$$i$$$ is compatible with $$$k$$$. Applying this additional observation, we deduce $$$$$$ans_k = 1 + \max\Big(0, \max_{1\le i \le k-2r} ans_i, \max_{\substack{k-2r< i < k,\\ \text{$i$ is_compatible_with $k$}}} ans_i\Big)\,.$$$$$$ Hence, if we bookkeep the maximum of $$$ans_i$$$ on prefixes, we can compute $$$ans_k$$$ in $$$O(r)$$$ and the overall complexity becomes $$$O(nr)$$$.
Alternative optimization It is also true that any optimal solution does not skip more than $$$4r$$$ consecutive celebrities (we leave the proof to the reader). Hence another possible optimization of the naïve formula is to take the maximum only over $$$k-4r\le i < k$$$.