ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1591. Abstract Thinking

I doubt if the ACed program is right
Posted by 198808xc 15 Oct 2010 13:59
I have been thinking about the problem these days, and found that the solution is much related to the 4, 5 or 6-point groups of the N points.

For the former two situations, we could simply calculate that the total number of the figures is
4 * C(n, 4)
and
5 * C(n, 5)
but what have we do when there are 6-point groups? According to the problem statement, the chords must intersect pairwise, so the solution for 6-point groups will be based on the detail position of the points. For example, we must find out if the chords will parallel with each other.

On the other side, I found we have more than one ways to connect 6 points to form the figure. For those 6-point groups with no paralleling chords, we have actually 4 ways to connect them: (1-4, 2-5, 3-6), (1-4, 2-6, 3-5), (2-5, 1-3, 4-6) and (3-6, 1-5, 2-4). Here we numbered the points in CW or CCW order.

Could anybody tell me that why the correct answer could be
4 * C(n, 4) + 5 * C(n, 5) + C(n, 6), (especially the last term)
If my analysis above is right, this formula will be wrong even in N = 7.

Thanks in advance.
Why isn't 259 the answer for N=7?
Posted by 198808xc 15 Oct 2010 17:46
I think that's indeed the correct answer.

For any 4-point group we have 4 combinations, and for any 5-point groups we have 5. So there are
4 * C(7 ,4) + 5 * C(7, 5) = 245.

For any 6-point groups, as N = 7, we could know that it is a complete group for all 7 points with only one missing. So the 7 "different" groups are actually the same.

Let's count how many interesting triangles in one group. For they are all the same, we take point 1, 2, 3, 4, 5, 6 on the circle, which is in CCW order (7 is missing).

We have the following two ways to connect them and make them intersect pairwise:
(1-4, 2-5, 3-6): a small triangle is formed inside the circle.
and
(1-3, 2-5, 4-6): a long triangle is formed, with 2 of its vertices inside the circle.

So, there are 2 (or, at least 2) combinations for every 6-point groups in N = 7. So the total number will be
245 + 7 * 2 = 259
(or, at least 259). But all the ACed program will give the answer 252.

Why? Where did I have a mistake? Anyone, please, tell me the truth about this problem.

Thanks again in advance!
Re: I doubt if the ACed program is right
Posted by bsu.mmf.team 15 Oct 2010 20:17
3 of your ways to connect 6 points are wrong:
(1-4,2-6,3-5) - segments 2-6 and 3-5 don't intersect
(2-5,1-3,4-6) - segments 1-3 and 4-6 don't intersect
(3-6,1-5,2-4) - segments 1-5 and 2-4 don't intersect

It is true, because any six different points construct a CONVEX 6-gon if they lie on one circle.
Re: I doubt if the ACed program is right
Posted by 198808xc 16 Oct 2010 21:10
Well, I suddenly realized that we should regard the CHORD as a SEGMENT, not a LINE. So the ACed programs are right.

Thank you very much.