11139 - Counting Quadrilaterals

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

11139 - Counting Quadrilaterals

Post by Darko » Mon Oct 23, 2006 7:08 am

I'll probably sound silly because someone solved this problem during the contest, but I am not sure how that last test case might be correct. For a 10x10 grid, there are 121 points, so even if you count degenerate cases (triangles and line segments), the result is the number of ways to choose 4 elements out of 121 which is ~8.5 mil. So the actual answer must be less than that, but it is given as ~12mil

Or I just misunderstood the problem? What does "different" mean here?

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Mon Oct 23, 2006 7:32 am

You have to consider the concave quads as well. Consider the points

(0,0), (10, 0), (0,10) and (1,1)

They can actually create three quadrilaterals. Although according to the combination there is only 4C4=1 quads

Sorry I mistyped previously four, they actually create three quads.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Oct 23, 2006 2:36 pm

Ah, thanks, that was silly of me after all.

luishhh
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain

11139 Counting Quadrilaterals

Post by luishhh » Tue Oct 24, 2006 4:30 pm

Oh! This is a nice example of an easy-to-formulate and hard-to-solve problem. I tried it in the online contest and I wasted more than 2 hours, but yesterday I managed to finish it. Obviously, (see the ranklist) I used precomputation, I wrote a brute-force solution O(n^7) (can be O(n^6) if implemented better) that needs lots of computation time. I wonder what is the complexity of the algorithm used by other people solving the problem.

My (mixture of my colleagues and mine ideas) approach was:
- First, I count all the posibilities of selecting 4 distinct points in the grid, no 3 collinear; it is actually the number of convex quadrilaterals + 1/3 * concave quadrilaterals. It doesn't take much effort for a machine, it runs in about half a minute in my computer.
- Second, the brute-force. For each possible segment I count the points in the grid above the segment (actually the line extending the segment) and the points under it; and count the couples of points one above and one under the segment. It gives, as a result, the number of concave quadrilaterals + 2 * convex quadrilaterals.

I'd be glad to hear more ideas to solve the problem, especially those that can be implemented and precomputated during an online contest.
"From lost to the river" --> Spanish quote

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Oct 24, 2006 4:48 pm

Mine is O(n^4).
From the total total number of possible sets of 4 points (which is the binomial coefficient: (n+1)^2 choose 4), I first subtract number of sets in which four or three points are collinear (this can be done in O(n^2)).
Then for each lattice triangle (there are O(n^6) of them, but only O(n^4) different ones need to be checked -- all others can be obtained by translation), I find number p of lattice points inside it (by Pick's theorem). Number of concave quadrilaterals for which this triangle is the convex hull is 3*p. I add to the answer 2*p, because p of those quadrilaterals were already counted in the beginning.
Last edited by mf on Tue Oct 24, 2006 4:55 pm, edited 1 time in total.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Oct 24, 2006 4:54 pm

If you use pick's theorem in this problem then solution can be much faster. Did you try to use it :).

Actually I was so fed up with in finding efficient solution that when I found it I did not care to optimize much. I split the problem into some parts:

a) Find all concave quadrilaterals in efficient manner.

b) Find C(n,4).

c) Find the zero area quads and the triangles that was counted as quads.

Then use some inclusion exclusion. Not posting the details or it will be an spoiler.

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Oct 24, 2006 4:58 pm

I think me and mf were almost concurrent in posting time and use similar methods.

luishhh
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain

Post by luishhh » Tue Oct 24, 2006 5:14 pm

Wow, great!, your solutions are more than enough for me, they completely satisfy my curiosity. In fact I remember thinking about using Pick in the contest for a second, as everybody usually does when faces a problem with lattice and figures, but I didn't know how to apply it (it was before I needed to count only the concave or convex ones :D)
"From lost to the river" --> Spanish quote

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Tue Oct 31, 2006 9:15 am

I follow the algorithm described above, but got WA.
the maximum input is n = 120, right?
please verify my output for n = 118,119 and 120:

118 2691512617349032
119 2877994834324016
120 1085980800144653612

Is it correct? if yes, why do I get WA then? any idea?

Thanks
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Oct 31, 2006 9:23 am

Here are my outputs:

118 - 2691512617349032
119 - 2877994834324016
120 - 3075682094608520

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Post by fh » Tue Oct 31, 2006 9:39 am

Thanks for the quick reply.

It seemed that I got overflow just for the nCk[n^2][4].
I just got it AC, thanks.

Btw, is there anyone can solve this problem without pre-calc?
Or this problem was designed to be solved by precalculation?
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Nov 03, 2006 12:51 am

Need to find a O(n^3) algorithm if you want to do it without pre-calculation. My O(n^4) gets tle if I don't do pre-calculation. It needs a bit of optimizing to pass the time limit.
Last edited by sclo on Fri Nov 03, 2006 1:52 am, edited 2 times in total.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Fri Nov 03, 2006 1:40 am

Mine is O(n^4). Although it's just marginally passed within 10 seconds.
I code, therefore I am.

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Fri Nov 03, 2006 2:19 pm

You can do it in O(n^3) :wink:
Impossible is nothing

Post Reply

Return to “Volume 111 (11100-11199)”