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

×

ALICE - Editorial

PROBLEM LINK:

Practice
Contest

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.

Tester's Solutions:

Setter's solution
Tester's solution

This question is marked "community wiki".

asked 21 Aug '16, 17:18

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k53137170
accept rate: 20%

edited 22 Aug '16, 19:29

admin's gravatar image

0★admin ♦♦
19.8k350498541


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.

link

answered 22 Aug '16, 00:31

xellos0's gravatar image

7★xellos0
5.9k54393
accept rate: 10%

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 !

link

answered 22 Aug '16, 17:05

neeladree's gravatar image

3★neeladree
112
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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