Page 1 of 3
10402 - Triangle Covering
Posted: Tue Nov 05, 2002 5:05 pm
by Ivan Golubev
I'm just puzzled with this problem, mainly with case T4.
In my computations if P1 (and P2) is a point of intersections of three lines (for short, PITL) then constant == 2.312677596894 and P3 is not a PITL, otherwise if P3 is PITL then P1 and p2 cannot be PITL and constant == 2.3094010767585.
Looks like that second constant is closer to sample output but in this case how about "b) When three or more lines appear coincident they are actually coincident"?
Am I wrong or something else wrong?
I don't know what's the problem also!!!
Posted: Tue Nov 05, 2002 9:47 pm
by Saiful Karim
I also faced the same problem & sending the two versions for T4 got
WA
can any one help please?
Posted: Tue Nov 05, 2002 11:30 pm
by Adil
hello guys.
from the symmetry, we can deduce that P3 is the mid-point. now, let A and B be the end-points of the line of P3. so we have,
AP3 = r / sin(60 deg) ==> where r is the side of the squares
thus, AB = 2 * r / sin(60 deg)
hope i am correct, and hope this helps.
Posted: Wed Nov 06, 2002 4:55 pm
by Ivan Golubev
Adil wrote:thus, AB = 2 * r / sin(60 deg)
This is trivial, don't you think that 2.3094010767585 == 2 / sin(60) ? The problem in this case that points P1 & P2 won't be at the triangle border (at least, in my computations, may be I'm wrong but I don't think so).
Posted: Thu Nov 07, 2002 1:49 am
by Adil
hello there.
i think P1 and P2 are PITL. might it be that the middle square doesn't intersect the lower two squares on the border of the triangle? but in that case, the problem statement is partially-wrong i guess.
Posted: Sun Nov 10, 2002 8:57 am
by dwyak
In my opinion, p3 should be on the bottom side of the triangle, or the triangle will not be the largest. And p1 and p2 are not on the side of the triangle. But i got WA.
ATTN : PROBLEMSETTER
Posted: Sun Nov 10, 2002 3:04 pm
by Mahbub
There is no doubt that t4 = s*4/sqrt(3)...Becoz it is written by the
dicoverer of the problem!
The result for t2 is s* (4*root(6) - 6*root(2)) which is also as stated by
David Candrell...
So the prob is for t3 and t6..where he stated that t3 = 2.108+ and t6 =
3.168+..which do not hav analytic solutions. (He didnt wrote the equation
either...
..).
But i was very hopeful when i succeeded to construct equations which
have the following results as constant :
2.1088402140624
3.1688842013610
which are both in agree with his approximate result. I think that its very
unlikely to get an erroneous equation and derive constants that are so
close to actual ones..Furthermore i didnt use any complex symmetry
property or something that i have doubt in.
So my opnion is that "THE PROBLEMSETTER NEEDS TO RECHECK HIS
SOLUTION AND THE PROBLEM DESCRIPTION"
Thanks
Light
ATTN : PROBLEMSETTER 10402 (TRIANGLE COVERING)
Posted: Sun Nov 10, 2002 3:07 pm
by Mahbub
There is no doubt that t4 = s*4/sqrt(3)...Becoz it is written by the
dicoverer of the problem!
The result for t2 is s* (4*root(6) - 6*root(2)) which is also as stated by
David Candrell...
So the prob is for t3 and t6..where he stated that t3 = 2.108+ and t6 =
3.168+..which do not hav analytic solutions. (He didnt wrote the equation
either...
..).
But i was very hopeful when i succeeded to construct equations which
have the following results as constant :
2.1088402140624
3.1688842013610
which are both in agree with his approximate result. I think that its very
unlikely to get an erroneous equation and derive constants that are so
close to actual ones..Furthermore i didnt use any complex symmetry
property or something that i have doubt in.
So my opnion is that "THE PROBLEMSETTER NEEDS TO RECHECK HIS
SOLUTION AND THE PROBLEM DESCRIPTION"
Thanks
Light
Re: ATTN : PROBLEMSETTER
Posted: Mon May 19, 2003 10:49 am
by hzickner
Mahbub wrote:
But i was very hopeful when i succeeded to construct equations which
have the following results as constant :
2.1088402140624
3.1688842013610
Light
I found the same constants but got WA too. I have an analytic solution for T3, but needs a whole sheet of paper. for T6 I have only the numerical approximation (100 digits computed with MuPad). There must be something wrong with the correction software.
Holger
Judge just plain wrong
Posted: Fri May 30, 2003 9:03 pm
by Cletus
"There is no doubt that ...Becoz it is written by the
dicoverer of the problem!"
Code: Select all
After many years of reading academic papers, I would not
take that as very strong evidence.
But in this case, it is undoubtedly right. I have come up with
exactly the same analytic results for t2 and t4, and exactly
the same numbers fot t2, t3, t4, and t6, by numeric methods,
to 14 or 15 digits of accuracy. We can not all have got the
same numbers and got them wrong. I've done this with
double self checking code to make sure all the intersections
really are exact, and they are.
Except of course for the one at the bottom of the construction
for T4. If t4=4.0/sqrt(3.0), which it is, it is absolutely
impossible for the intersection of the two lowest squares to
coincide with the base of the triangle.
In fact, regardless of the value of t4 it is still impossible.
If those two squares met on the base of the triangle, we'd
have a right-angled triangle with angles 30 and 60 degrees,
one side = s, and the hypotenuse = t/2, giving t=2/cos(30).
A similar but slightly less trivial construction on the left
edge of the triangle gives t=(1+cos(15)+tan(15))/cos(15)
Those two formulas are just not the same.
The two bottom squares of T4 must intersect approximately
0.00123 units of distance below the mid-point of the base of
the triangle.
So we have both a wrong problem description and a wrong
judge. We really have been honoured.
10402
Posted: Tue Sep 02, 2003 12:58 am
by Zaheed
ohh my god... i've made it...
i've always been fond of geometrical problems... but this one is undoubtedly the best one i ever came across... it took me almost 3 hours to get accepted but at the end i was about to give up & it was my last attempt that reflected green...
after putting up so much effort when i got W/A i was really frustrated & for a moment i even thought the problemsetter must be some stupid person & he might have written a wrong solution cause i was really confident that my solution was correct... but you know we shouldn't think this way, its really unfair of us (or may be just me) to think this way... we should understand that this people (the genius problemsetters) really work hard to make it error-free & there is very little chance that their solution is incorrect... anyway, i could point out my mistake & now the corrected submission has been happiliy accepted my the judge...
i must admit shahriar manzoor is a real genius... plz DONT think therez anything wrong in this problem... it was a really nice problem.. & also i liked his problem, Flowers of a beautiful mind prob # 10540... it took me approx 36 mins to solve that in the last online contest... i was the one to solve it 1st but may be thats because i attempted it 1st...
anyway, this kind of geometrical problems are really nice... i'm a newbie programmer & i'm yet to know all of those 1000 types of algoz properly
so this kind of algo-free probs are really helpful... i don't mean algoz are bad cause those are also nice & i really find it interesting to learn new algoz every now n then but i need some more time to complete digesting all of the most commonly used algoz...
a friend of mine once told me the stuffs that are to be learned keeps on growing exponentially but we can only learn linearly...
but still we don't give up & i guess thats where our real strength lies...
anyways... its really nice to solve a problem that stayed unsolved for quite some time... thanks to everyone for waiting for me to solve it first...
Sabur Zaheed (AIUB)
Posted: Tue Sep 02, 2003 1:01 am
by Zaheed
both the problem desrciption & its solution is quite ok!
regards
Sabur Zaheed
Posted: Tue Sep 02, 2003 1:05 am
by Zaheed
Posted: Tue Sep 02, 2003 1:24 pm
by Ivan Golubev
Zaheed, the only reason of your accepted result is that you've been enough lucky to make the same mistake as the author of judge's test input/output. Nothing else.
Hmm
Posted: Tue Sep 02, 2003 2:03 pm
by shahriar_manzoor
I myself also believe that this problem is wrong as I interpreted a figure wrongly. But somehow I don't find enough free time to fix this problem (may be reluctent to think down the same line again)