PROBLEM LINK:Author: Alei Reyes 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.
Now,
Now,
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. Tester's Solutions:
This question is marked "community wiki".
asked 21 Aug '16, 17:18

Lol magic. The same argument as in TWEED applies for why it's quite hard: the right approach isn't obvious at all. Also, it's hard to use imagination here. answered 22 Aug '16, 00:31
