UChicago Practice Contest 2018-04-28


2018-04-28 09:00 AKDT

UChicago Practice Contest 2018-04-28


2018-04-28 14:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -948 days 23:15:20

Time elapsed


Time remaining


Problem E

Consider a square grid with lamps in fixed locations. Each lamp can either illuminate its row or its column, but not both. The illumination of each lamp extends over a limited distance.

Any square in the grid should only be illuminated by at most one lamp in its row and by at most one lamp in its column (one of each is acceptable, as is just the row, just the column, or neither). Determine if it is possible for all lamps to be lit while satisfying these constraints.


Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains three positive integers, $n$, $r$ and $k$ ($1 \le n, r, k \le 1\, 000, k \le n^2$), where $n$ is the size of one side of the square grid, $r$ is the maximum reach of a lamp, and $k$ is the number of lamps. The next $k$ lines will each contain two positive integers $i$ and $j$ ($1 \le i, j \le n$), indicating that there is a lamp in the grid at row $i$, column $j$.

Each lamp can illuminate squares at most $r$ units away, and can also illuminate its own square, so the maximum number of squares it can illuminate is $2 r + 1$. All lamps will be in distinct locations.


Output a single integer, $1$ if it is possible to light all of the lamps and $0$ if it is not possible.

Sample Input 1 Sample Output 1
3 2 5
1 1
1 3
3 1
3 3
2 2
Sample Input 2 Sample Output 2
3 2 6
1 1
1 2
1 3
3 1
3 2
3 3