You are not logged in. Please login at www.codechef.com to post your questions!

×

# ALICE - Editorial

Author: Alei Reyes
Editorialist: Praveen Dhinwa

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.

# Tester's Solutions:

This question is marked "community wiki".

asked 21 Aug '16, 17:18 2.5k53137170
accept rate: 20% 19.8k350498541

 8 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 7★xellos0 5.9k●5●43●93 accept rate: 10%
 0 Hi! I have used a different approach. Can I get to know what testcases wouldnt pass for my solution- Solution link- link text Thanks a lot ! answered 22 Aug '16, 17:05 11●2 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,722
×321
×202
×29

question asked: 21 Aug '16, 17:18

question was seen: 5,180 times

last updated: 22 Aug '16, 19:29