PROBLEM LINK:
Author: Alei Reyes
Tester: Hasan Jaddouh
Editorialist: Praveen Dhinwa
DIFFICULTY:
easy medium
PREREQUISITES:
constructive algorithms, gcd idea
PROBLEM:
You are given a grid of size n \times n. You have to find n + 1 lines in it each joining any two integer points on the perimeter of the boundary of the grid, such that each lattice cell of the grid is cut by some line. You also have to make sure that no two lines are parallel. You can print any possible set of lines, if there are multiple possible solutions.
See the image for one such example for n = 3.
EXPLANATION:
We want to make sure that no two lines should be parallel. If we can somehow have slope of our lines will be \frac{x - 1}{x} or \frac{x}{x - 1} for different values of x, then we can ensure that no two lines will be parallel. This is due to the fact that gcd(x, x - 1) = 1 for each positive x.
Let us draw the first line between (0, 0) to (n, n - 1). This line has slope of \frac{n}{n - 1}. It will cut 2 * n - 2 cells. This line will cut the grid into two disjoint parts. The below part can be cut by the lines connecting points (2 * k, 0) and (n, n - 1 - 2 * k). The above part can be cut by the lines by connecting points (0, 1 + 2 * k) and (n - 2 - 2 * k, n).
You can understand it as follows.
- Draw a line from (0, 0) to (n, n - 1).
Now,
- Now, draw a line from (2, 0), to (n, n - 3).
- Similarly, draw a line from (4, 0), to (n, n - 5).
- In general, draw a line from (2 * k, 0) to (n - 1 - 2 * k).
Now,
- Draw a line from (0, 1) to (n - 2, n).
- Draw a line from (0, 3) to (n - 4, n).
- In general, draw a line from (0, 2 * k + 1) to (n - 2 * k, n).
Till now, you have constructed total n - 1 lines. You can prove that these lines are sufficient to cut each cell which does not lie on the upper and right side border cells. You can cut these remaining two border cells by two more lines.
The first line can be from (n, 0) to (n - 1, n). This line will cut all the cells on the right border.
The second line can be from (0, n) and (n, n - 1). This line will cut all the cells on the top border.