11139 - Counting Quadrilaterals

[Darko]

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]

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]

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

[luishhh]

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.

[mf]

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.

[shahriar_manzoor]

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]

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

[luishhh]

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 )

[fh]

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

[mf]

Here are my outputs:

118 - 2691512617349032
119 - 2877994834324016
120 - 3075682094608520

[fh]

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?

[sclo]

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.

[Cho]

Mine is O(n^4). Although it's just marginally passed within 10 seconds.

[tywok]

You can do it in O(n^3)