| Show all threads Hide all threads Show all messages Hide all messages | | I doubt if the ACed program is right | 198808xc | 1591. Abstract Thinking | 16 Oct 2010 21:10 | 4 | 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. 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! 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. 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. | | Too simple Ac,may be checker wrong | svr | 1591. Abstract Thinking | 14 Aug 2010 20:46 | 8 | 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. 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... 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 I doubt anyone can mentally put 2000 points on a circle =) 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 F(n)=4*S4(n)+5*S5(n)+S6(n)
Why is it true and how to guess about it? a picture is needed to understand ! please assist 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 =) | | 4 cheaters (some test cases) | DK [SamaraSAU 2: AKA NULL] | 1591. Abstract Thinking | 14 Sep 2008 13:33 | 5 | Unfortunaly, test cases allows using of one wide - known method :)
The answer is of course P(n), and P(n) hasn't more than x^6.
3: 0
4: 4
5: 25
6: 91
7: 252
8: 588
...
1000: 1409590423741500
Edited by author 29.10.2007 02:57 can anyone send algorithm of this problem on my mail?
gio-saghinadze@mail.ru
thanks
Edited by author 30.10.2007 17:42 No subject Giorgi Saghinadze (Tbilisi SU) 30 Oct 2007 18:07
Edited by author 30.10.2007 18:07 I'm sorry, but could you give answer fo 2000? I have WA10 with correct answer for 1000 and I have no idea what can be wrong. For 2000:
89553445611633000 | | c++ must die, pascal forever (+) | Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) | 1591. Abstract Thinking | 20 Jul 2008 17:10 | 8 | It's enough the pascal's extended type to solve this problem.
But the C++'s double type has only 15 digits :'(
Edited by author 16.11.2007 01:58 I think it's enough int64 I agree with topic), but
i think it depends on compiler
VS help says that long double equals to double and have
15 digits, but actually can store up to 18
strange.. If you can't normaly solve the problem, just agree with it.
C++ - the best! Pascal - already died. gcc has 10 bytes for long double while VC long double is 8 bytes long. Anyway, __int64 can hold up to 18 digits. And keep it unsigned :) | | Three hords intersecting at the same point | Pavel Semushin | 1591. Abstract Thinking | 18 Nov 2007 18:38 | 1 | Am i right that it's not important that some three hords intersect at the same point, and this figure is according to condition of promlem?
For example, three diagonals of ideal 6-polygon which intersects at its center make an interesting triangle, aren't they? | | Why on this code stands out "Compilation error"? | Anix | 1591. Abstract Thinking | 18 Nov 2007 13:26 | 2 | Thank's. VS6.0 has very stupid compiler :)
Edited by author 18.11.2007 21:28 when you submit your code you can use option
"reply to this email"
maybe you use Visual Studio 6.0 and it's stupid compiler
for (int i=0;i<k;i++) // there you define i
{
tmp*=n;
n--;
} // end of area where i is visible
for (i=1;i<=k;i++)
^^^^^^^^^^ i is undefined there
{
d*=i;
}
in c++ standart you can do such cicles
for (int i = 0; i < 4; i++) .....
for (int i = 0; i < 4; i++) .....
but stupid VS 6.0 compiler think that it is wrong
anyway you can do as this:
int i;
for (i = 0; i < 4; i++) ...
for (i = 0; i < 4; i++) ...
Edited by author 18.11.2007 13:27 | | input = 6 | L@MeP | 1591. Abstract Thinking | 28 Oct 2007 22:01 | 2 | what answare on input = 6 Yep, and for 7 8 9 10 give some answers too plz:)
Btw, why when n = 5 ans answer is 25. Somehow I managed to find 28 trianles. |
|
|
