NAQ 2016&2017 hard problems (UBC)


2017-10-12 00:00 UTC

NAQ 2016&2017 hard problems (UBC)


2017-10-19 00:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -586 days 14:49:17

Time elapsed


Time remaining


Problem K
Umbral Decoding

You are planning a clever attack against a new encryption algorithm. To succeed, you need to find the key, which is a pair of integers $(p, q)$. We can think of the key as a point on a two-dimensional integer lattice whose location is unknown. However, you know that $(p, q)$ lies in the square spanned by the lattice points $(0, 0)$ and $(n, n)$ for a given $n$, i.e. $0\leq p,q\leq n$.

Your attack has three stages:

  1. Identify safe points and their bounds.

  2. Eliminate as key candidates those points that lie in the “umbra” of any safe point.

  3. Test the remaining points to see which one is the key.

Stage 1 has already been performed and you are given several safe points of the form $(x, y, b)$ as input.

In Stage 2 you eliminate a point $(p, q)$ if it lies in the umbra of any safe point. Point $(p, q)$ is in the umbra of safe point $(x, y, b)$ if and only if

\[ |x-p|^3 + |y-q|^3 \leq b. \]

Your task in this problem is to count how many points will be left for testing in Stage 3 so that we have an estimate of the amount of work left to complete the attack.

\includegraphics[width=0.3\textwidth ]{sample1b.png} \includegraphics[width=0.3\textwidth ]{sample1a.png}
Figure 1: Sample input safe points and umbra (red) and remaining points (blue).


Input begins with two integers $n, k$ on a single line, separated by a space, with $2 \leq n \leq 100\, 000\, 000$, and $0 \leq k \leq 100$. Following that are $k$ lines each containing three integers $x, y, b$ separated by spaces, representing the safe points. The values of $x$ and $y$ are both in the range $[0,n]$. The bound $b$ lies in the range $[0, n]$.


Output the number of points $(p, q)$, with $0 \leq p,q \leq n$, that do not lie in the umbra of any safe point.

Sample Input 1 Sample Output 1
4 1
2 2 2
Sample Input 2 Sample Output 2
30 2
20 20 30
25 22 30