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

×

PLANEDIV - Editorial

0
1

PROBLEM LINK:

Contest
Practice

Author: Maksym Bevza
Tester: Sergey Kulik
Editorialist: Kevin Atienza

PREREQUISITES:

Cartesian coordinates, parallel lines, sets, GCD, Euclidean algorithm, sorting

PROBLEM:

A set of lines is called perfect if there's no point that belongs to two distinct lines of the set.

Given a set of $N$ lines, each determined by three coefficients $(A,B,C)$ (representing the line $Ax + By + C = 0$), what is the size of the largest perfect subset?

QUICK EXPLANATION:

The answer is simply the largest set of distinct lines that are all parallel to one another. To get the answer, group the lines according to slope, being careful to not count coinciding lines twice. (e.g. $x + y + 1 = 0$ coincides with $2x + 2y + 2 = 0$ so should only be counted once.) The answer is the size of the largest group.

One way to group the lines is to add them to a set data structure. Another is to sort them according to slope, so that lines with the same slope are found consecutively.

EXPLANATION:

A set containing just one line is clearly perfect, so let's investigate perfect sets of size at least two. Let $a$ and $b$ be two lines in a perfect set. Since $a$ and $b$ must not intersect (and definitely must not coincide), then they must be parallel. In other words, they must have the same slope. Since this argument applies to any pair of lines in the perfect set, we can say that a perfect set is just a set of distinct lines all having a common slope.

Our goal now is to find the largest perfect set. Naturally, we want to group the lines according to slope, and take the largest group as the answer. In fact, this is basically the algorithm to solve this problem! However, there are at least two problems that might come up when implementing this:

  • First, we must be able to represent the slope exactly, and not just a floating point number, otherwise you risk getting wrong answer due to bad rounding. (Remember that many numbers cannot be represented exactly in floating point.)
  • Second, we must be able to detect whether two lines coincide, because we should only count coinciding lines once.

We'll deal with these problems one by one.

Representing the slope

First, note that it's actually possible to get accepted while using floating point slopes (especially if the data isn't strong enough or the bounds of the problem prevents rounding errors from being a problem), but it's still important to know an error-free way to represent slopes, in other words, a way that can be shown to always work. Also, representing a slope exactly has many applications even outside of this problem. So how do we represent the slope of a line exactly?

Representation 1

Well, one way to represent the slope exactly is to simply represent it as an exact fraction. For example, the slope of $Ax + By + C = 0$ is $-A / B$. But we must be able to detect the same fractions! (For example, $1 / 2 = 2 / 4 = 3 / 6$.) One way to do it is to reduce the fraction to lowest terms, by dividing the numerator and denominator by the greatest common divisor (gcd). This works because rational numbers have a unique representation in lowest terms.

We need to represent negative slopes as well! To make the "lowest term representation" unique, simply ensure that the denominator is always positive. Another problem that will arise is how to represent the slope of vertical lines. Their slope can't be represented by a rational number (because it's "infinite"). However, since there is a unique slope for vertical lines, we can simply use a unique object to represent the "vertical slope". (or just handle vertical lines separately)

Representation 2

There's actually a way to represent the slopes without needing any special handling for the vertical slope. Instead of representing the slope of the line as a rational number, we represent it as the vector pointing to the direction of the line. Remember that a vector is an ordered pair $\langle x, y \rangle$, which represents the direction pointing from $(0,0)$ towards $(x,y)$. (In a vector, the distance between these points are also important, but since we're only talking about the "direction" of the line, it doesn't matter for our purposes.)

What is the direction vector of the line $Ax + By + C = 0$? Suppose $(x_1,y_1)$ and $(x_2,y_2)$ are points on this line. Then $\langle x_d, y_d \rangle = \langle x_2-x_1, y_2-y_1\rangle$ is one possible direction vector. But these points satisfy the equation of the line, so: $$Ax_1 + By_1 + C = 0$$ $$Ax_2 + By_2 + C = 0$$ Subtracting these two, we get: $$A(x_2-x_1) + B(y_2-y_1) = 0$$ or $$Ax_d + By_d = 0$$ But one solution to this equation is simply $x_d = B$ and $y_d = -A$, thus $\langle B, -A \rangle$ is one direction vector for the line $Ax + By + C = 0$!

But in order to group our lines according to slope, we must again be able to detect vectors representing the same direction. Similarly to rational numbers, we must find some sort of "normal form" that we can reduce our direction vectors to. Note that we also consider opposing vectors as representing the same "direction", e.g. $\langle x, y \rangle$ and $\langle -x, -y \rangle$.

One way to define such a normal form is the following. Let's say a vector $\langle x, y \rangle$ with integer coordinates is in normal form if and only if $x$ and $y$ are relatively prime and the polar angle of $(x,y)$ is less than 180 degrees. The reader is invited to prove that every direction vector has a unique normal form.

Finally, to convert $\langle x, y \rangle$ to normal form, simply divide both coordinates by $\gcd(x,y)$, and then negate both if $y$ is negative, or $y = 0$ and $x$ is negative.

Using vectors instead of slopes, we don't have to worry about "infinite" slopes any more!

Detecting coinciding lines

Next, what about detecting coinciding lines? Note that coinciding lines necessarily have the same slope, so we can simply look at lines with the same slope, and find among those the lines that overlap.

Note that two lines overlap if and only if their equations are the same, up to a nonzero multiplicative constant. For example, the following lines all coincide with one another:
$$4x + 6y + 1 = 0$$ $$8x + 12y + 2 = 0$$ $$44x + 66y + 22 = 0$$ $$-44x - 66y - 22 = 0$$ However, these lines do not coincide with the line $4x + 6y + 2 = 0$ or $4x + 6y - 1 = 0$.

In this case, we can simply try to reduce the equations into some sort of "normal form" (as in the previous section), in such a way that each equation of a line has a unique normal form. Here's one way: Let's say the equation $Ax + By + C = 0$ is in normal form if $A$, $B$ and $C$ are relatively prime, and one of the following conditions hold:

  • $C > 0$
  • $C = 0$ and $B > 0$
  • $C = 0$, $B = 0$ and $A > 0$

The idea behind this is actually just an extension of our "normal form" of direction vectors in the previous section, because $\langle x, y \rangle$ is in normal form if $x$ and $y$ are relatively prime and one of the following conditions is satisfied:

  • $y > 0$
  • $y = 0$ and $x > 0$

Thus, we can just reduce all our equations to their normal forms, and this way, two lines coincide if and only if their equations are equal!

Solution

Armed with the above techniques, the solution is now easy. First, group the lines according to their slopes (or normal forms of their direction vectors). Then, for each group, compute the normal forms of their equations, and remove duplicates. Finally, the answer is simply the largest remaining group!

The following is a Python implementation which solves a single test case:

from fractions import gcd
from collections import defaultdict
s = defaultdict(set)
for i in xrange(input()):
    a, b, c = map(int, raw_input().strip().split())
    g = gcd(a, b)
    h = gcd(g, c)
    s[a/g, b/g].add((a/h, b/h, c/h))
print max(map(len, s.values()))

Since Python's $\text{gcd}(a,b)$ is guaranteed to have the same sign as $b$, dividing by the gcd will already guarantee normality (as we've defined it).

The time complexity of this algorithm is $O(N \log N)$ if one uses balanced tree sets.

Alternatively, you can just sort them according to their normal forms, so parallel lines and coinciding lines are found consecutively. This runs in $O(N \log N)$ time also.

Time Complexity:

$O(N \log N)$ or expected $O(N)$

AUTHOR'S AND TESTER'S SOLUTIONS:

Setter
Tester
Editorialist

This question is marked "community wiki".

asked 12 Dec '15, 23:19

kevinsogo's gravatar image

7★kevinsogo
1.7k586142
accept rate: 11%

edited 13 Jan '16, 18:18

admin's gravatar image

0★admin ♦♦
19.8k350498541


Author's Solution is giving wrong answer in all cases please fix your code @author :) Good editorial. Thanks

link

answered 06 Jan '16, 20:29

archit910's gravatar image

2★archit910
820212
accept rate: 3%

The problem is just to use a stable sort to sort according to the intercept after that with slope, removing duplicates and reporting the maximal set.

The case where b=0, can be taken separately (slope infinity)..

My simple solution using sort : https://www.codechef.com/viewsolution/8910675

link

answered 14 Dec '15, 15:35

xariniov9's gravatar image

6★xariniov9
1.1k18
accept rate: 10%

edited 15 Dec '15, 23:28

Easy implementation using a set or map can be done to remove the duplicates and using y = m*x + c form of line. Insert pairs of slope and intercept into the set and then count the pairs with same slope. Duplicates will be auto removed. Std Map Solution Link

link

answered 14 Dec '15, 15:44

apptica's gravatar image

5★apptica
949210
accept rate: 17%

let l1 : a1 x + b1 y + c1 = 0

l2 : a2 x + b2 y + c2 = 0

l1 and l2 are parallel if and only if a1/a2 = b1 /b2 != c1/c2 .

I just sorted the lines by coefficients a,b,c so that identical and parallel lines come successively.

if two lines are identical then a1 = a2 , b1 = b2 , c1 = c2

if two lines are parallel then a1 = a2 , b1 = b2 , c1! = c2

here's my java solution : https://www.codechef.com/viewsolution/8884085

link

answered 15 Dec '15, 14:53

code_hard123's gravatar image

6★code_hard123
7818
accept rate: 7%

edited 15 Dec '15, 14:58

@kevinsogo I can't access the setter and tester solutions. Its saying access denied

link

answered 14 Dec '15, 15:53

tihorsharma123's gravatar image

2★tihorsharma123
49918
accept rate: 15%

I tried this problem using calculating slope & intercept - using y = mx+c.
It still gives 1 WA in both subtasks.
https://www.codechef.com/viewsolution/8955195
Is this because of precision or is there any other issue ?
Providing testcase will be really helpful.

link

answered 14 Dec '15, 16:21

konfused's gravatar image

4★konfused
211
accept rate: 0%

Got it!!
Precision set to 10^-16
Here is correct solution -
https://www.codechef.com/viewsolution/8974725

(18 Dec '15, 12:43) konfused4★

I tried this problem with sorting line using comparison function...bt it gave WA in some test cases.. https://www.codechef.com/viewsolution/8945683

can u give me some test case where my code is giving error..link text

link

answered 15 Dec '15, 10:50

raj61's gravatar image

5★raj61
1
accept rate: 0%

I think I had the same problem like you at some point. So, if I understand correctly, your idea is to sort all the lines and check how many lines are next to each other and are parallel, but not equal?

Ok, I can't give you a specific test currently, but imagine the following situation. After you sort the lines you have got a, b, c, d, e, which are all lines. And c == d, i.e. they are the same line. but b || c || d || e, i.e. b, c, d, and e are all parallel. Then the answer should be 3, right? But your code will stop at d, because it is the same line as c and it will produce the answer 2.

(15 Dec '15, 14:22) aragar4★

Java solution by storing the slope in Map https://www.codechef.com/viewsolution/8905572

link

answered 15 Dec '15, 12:14

dp13's gravatar image

2★dp13
11
accept rate: 0%

I also tried something like sorting by slope, but without converting to float. Here is my solution. Could you help me identify the mistake?

link

answered 15 Dec '15, 14:11

aragar's gravatar image

4★aragar
995
accept rate: 7%

i just ran the authors solution in prctice link of the problem.. in c++14.. giving wrong answer!!!!!!! :p

link

answered 16 Dec '15, 14:39

aj619's gravatar image

3★aj619
1
accept rate: 0%

https://www.codechef.com/viewsolution/8965354

can anyone plz tell me where my code fails

link

answered 16 Dec '15, 15:28

amanagarwal03's gravatar image

3★amanagarwal03
11
accept rate: 0%

edited 16 Dec '15, 15:48

The only error I see is eventually of the error precision of the double. Did you try to write some test generator and a second slow-but-correct solution to test it? I can send you mine, if you would like.

(17 Dec '15, 14:08) aragar4★

yes please provide the link to your solution..

(17 Dec '15, 14:13) amanagarwal033★

You can find the file here. It contains the slow but correct solution, the generator and a bat to start it. It is a bit lame, but sorry :D

Just take in mind that I write for stuff then the given output, just check the generator first.

(17 Dec '15, 15:05) aragar4★

This is another example why I want the tests to be submitted after the contests. This is another task I can't solve because I can't find the error in my solution :\ I tried writing a test generator and a slow correct solution, but everything is ok for small tests :\ When I ask for help the setter won't help :\

link

answered 17 Dec '15, 14:06

aragar's gravatar image

4★aragar
995
accept rate: 7%

I've used y=mx+c line equation and used cmp() function for sorting. Can anyone tell me the test cases where my solution fails. https://www.codechef.com/viewsolution/8929449

link

answered 20 Dec '15, 13:24

sourabh123's gravatar image

3★sourabh123
1
accept rate: 0%

Setter's and Tester's solution showing WA in all the test cases.... :|

link

answered 29 Dec '15, 16:34

npcoder2k14's gravatar image

2★npcoder2k14
1
accept rate: 0%

My solution gives RE (SIGSEGV) for 2 test cases please sm1 cud explain. thanks in advance :) https://www.codechef.com/viewsolution/9105598

link

answered 06 Jan '16, 14:52

akchamp's gravatar image

4★akchamp
12419
accept rate: 20%

What's the bug in setter's solution? :(

link

answered 03 Mar '16, 00:38

esemzv's gravatar image

3★esemzv
212
accept rate: 0%

Do we really need to consider the case of a vertical line? The statement states that "For a line with coefficients A, B and C either A or B is not zero". So when B can not be a zero then how it is possible to form a vertical line?

link

answered 16 hours ago

tanmoy_datta's gravatar image

5★tanmoy_datta
1
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,875
×1,191
×801
×321
×174
×163
×26
×6

question asked: 12 Dec '15, 23:19

question was seen: 5,038 times

last updated: 16 hours ago