Discussion @ 1591. Abstract Thinking @ Timus Online Judge

198808xc I doubt if the ACed program is right [3] // Problem 1591. Abstract Thinking 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.

198808xc Why isn't 259 the answer for N=7? // Problem 1591. Abstract Thinking 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!

bsu.mmf.team Re: I doubt if the ACed program is right [1] // Problem 1591. Abstract Thinking 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.

198808xc Re: I doubt if the ACed program is right // Problem 1591. Abstract Thinking 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.

svr Too simple Ac,may be checker wrong [7] // Problem 1591. Abstract Thinking 31 Oct 2007 11:08

Let S4(n),S5(n),S6(n)- number of different
4-poligons,5-poligons and 6-poligons in n poligon.
I have AC using formula F(n)=4*S4(n)+5*S5(n)+S6(n).
But this formula can not be right because
in different 6-poligons 3 hords may intersect in
the same point and this triangle will be counted
more the once.

RLE Re: Too simple Ac,may be checker wrong [3] // Problem 1591. Abstract Thinking 1 Nov 2007 18:54

Your worry is superfluous
This condition (put mentally n points on its periphery at equal distances) can guarantee that there will not be different 6-poligons 3 hords may intersect in
the same point and this triangle will be counted
more the once

P.S My English is so poor...

svr Re: Too simple Ac,may be checker wrong [2] // Problem 1591. Abstract Thinking 1 Nov 2007 22:02

My suspictions based on considering
ideal 12-poligon in which exist two ideal
6- sub-poligons which different and distinvished
by rotation and having common centre in
which their hord intersected.

Edited by author 01.11.2007 22:26

Denis Koshman Re: Too simple Ac,may be checker wrong [1] // Problem 1591. Abstract Thinking 20 Jul 2008 17:11

I doubt anyone can mentally put 2000 points on a circle =)

Alexander Georgiev Re: Too simple Ac,may be checker wrong // Problem 1591. Abstract Thinking 2 Oct 2008 05:56

Hah, I on the other hand believe everyone can mentally (and not only) put infinitely many points on a circle. After all - isn't that the definition of a circle? (Infinitely many points with equal distance from one other point - the center?) :D

Programmer Re: Too simple Ac,may be checker wrong [1] // Problem 1591. Abstract Thinking 9 Jan 2010 04:08

F(n)=4*S4(n)+5*S5(n)+S6(n)
Why is it true and how to guess about it?

mirzauzairbaig ADMIN(s) help // Problem 1591. Abstract Thinking 13 Jan 2010 23:40

a picture is needed to understand ! please assist

2rf [Perm School #9] Re: Too simple Ac,may be checker wrong // Problem 1591. Abstract Thinking 14 Aug 2010 20:46

Yes, I was thinking about it too and I understand it now. In fact, it's said in statement that interesting triangle is not a triangle but "any three different chords from this set that intersect pairwise" and "at least one of their intersection points lies inside the circle". Therefore, three segments intersecting in one point are interesting triangle( and not a triangle).

It's like saying that interesting triangle is a four-sided figure =)

DK [SamaraSAU 2: AKA NULL] 4 cheaters (some test cases) [4] // Problem 1591. Abstract Thinking 29 Oct 2007 02:51

Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) c++ must die, pascal forever (+) [7] // Problem 1591. Abstract Thinking 16 Nov 2007 01:55

Pavel Semushin Three hords intersecting at the same point // Problem 1591. Abstract Thinking 18 Nov 2007 18:38

Anix Why on this code stands out "Compilation error"? [1] // Problem 1591. Abstract Thinking 18 Nov 2007 12:47

L@MeP input = 6 [1] // Problem 1591. Abstract Thinking 27 Oct 2007 17:35

Discussion of Problem 1591. Abstract Thinking