10947 - Bear with me, again..

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Oct 22, 2005 7:04 am

You can solve the problem without using doubles, as I imagine that might be a problem.

adnan2nd
New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg
Contact:

Post by adnan2nd » Sat Oct 22, 2005 7:22 am

but how?
the distance can be non-integer.
sobhani

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Oct 22, 2005 7:35 am

adnan2nd wrote:but how?
the distance can be non-integer.
You only need to compare the numbers. Compare their squares: for any real x,y >= 0, it holds that x <= y iff x^2 <= y^2.
Last edited by mf on Mon Oct 24, 2005 11:11 pm, edited 1 time in total.

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Oct 22, 2005 7:50 am

Quite a lot of people can finish 5 problems very fast in last contest. But then, kept struggling with this problem.
Is there any tricky thing apart from the floating point error?

adnan2nd
New poster
Posts: 14
Joined: Sat Jul 03, 2004 1:18 pm
Location: bangladesh,ctg
Contact:

Post by adnan2nd » Sat Oct 22, 2005 8:58 am

Then how can I convert the following

Code: Select all

dist=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
		
		if(fabs(dist-r1-r2-limit)<.000000001) g[i][j]=g[j][i]=1;
		else if(floor(dist-r1-r2)<limit) g[i][j]=g[j][i]=1;
into correct comarison. dist-r1-r2 is to be compared with limit. r1,r2 are integers.
sobhani

david
Learning poster
Posts: 83
Joined: Mon Apr 21, 2003 10:14 pm

Post by david » Sat Oct 22, 2005 1:02 pm

I think most problems from the last contest were badly specified (if not downright wrong, as was the case for problem A). Does anyone know how big can the coordinates be? Will a sum of squares overflow a long long? I have also tried using doubles, but nothing seems to work.

My algorithm simply uses the union-find data structure to merge connected components. Two islands are connected when the distance between their centers is no larger than the maximum distance plus the sum of their radii.
Any ideas as to why it gives WA?
Thanks in advance.

Code: Select all

deleted, it was correct... there are inputs with a negative number of islands, which makes absolutely no sense
Last edited by david on Sat Oct 22, 2005 5:06 pm, edited 1 time in total.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sat Oct 22, 2005 1:29 pm

I tried this problem in contest time firstly using long long, then bigint and then using double but with no luck. Anybody who got AC can please tell me what data type he used?


Regards
Sanny

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Oct 22, 2005 2:00 pm

adnan2nd wrote:Then how can I convert the following

Code: Select all

dist=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
if(fabs(dist-r1-r2-limit)<.000000001) g[i][j]=g[j][i]=1;
else if(floor(dist-r1-r2)<limit) g[i][j]=g[j][i]=1;
into correct comarison. dist-r1-r2 is to be compared with limit. r1,r2 are integers.
So you want to check if the inequality holds:
|dist - r1 - r2| <= limit. (*)

Start by squaring both sides.
(dist - (r1+r2))^2 <= limit^2
dist^2 - 2 dist (r1+r2) + (r1+r2)^2 <= limit^2
dist^2 + (r1+r2)^2 - limit^2 <= sqrt(4 dist^2 (r1+r2)^2)
If the LHS of the above equation is negative, then (*) holds.
Otherwise, once again square both sides.
(dist^2 + (r1+r2)^2 - limit^2)^2 <= 4 dist^2 (r1+r2)^2
The last inequality can be checked with just integer computations, since dist^2, r1, r2 and limit are all integers.
Sanny wrote:Anybody who got AC can please tell me what data type he used?
long long

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Oct 22, 2005 2:10 pm

I got AC using only ints for this problem, so overflow should not matter.

The mistake for problem A was mine. I changed the problem description and the test data very last minute for the local contest, but sent Miguel the outdated input.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Oct 22, 2005 2:20 pm

mf: I can't follow your reasoning for squaring again [EDIT: now I can]

Isn't this much simpler:

Since the islands are non overlapping, dist>=r1+r2, so we can write
dist <= limit + r1 + r2 for your condition (*)
and check
(dist)^2 <= (limit + r1 +r2)^2
which is an all-integer expression.

Still got WA, though :(

Got AC during the contest, but WA after rejudge. Still can't find my error.

Can anyone see it?

Code: Select all

DELETED AFTER AC
Integer overflow is not an issue, as I verified with other code, and it's also not TLE, although it's unnecessary slow. Please help!
Last edited by little joey on Sat Oct 22, 2005 3:54 pm, edited 2 times in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Oct 22, 2005 2:35 pm

Ah yes, your solution is correct and simpler than mine. (During the contest I just ignored that line where they say that islands don't overlap.)
Still got WA, though
Just post your code, I'll try to check what's wrong.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Oct 22, 2005 2:52 pm

mf wrote:Ah yes, your solution is correct and simpler than mine. (During the contest I just ignored that line where they say that islands don't overlap.)
Still got WA, though
Just post your code, I'll try to check what's wrong.
See the previous message, that was the code that got AC during the contest.
This is new code that runs much faster, but also is WA

Code: Select all

DELETED AFTER AC
Last edited by little joey on Sat Oct 22, 2005 3:55 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Sat Oct 22, 2005 3:31 pm

Ok, I think I know what's going on. There are test cases where N<0. (???!)
(makes one wonder, how can something "be followed by [a negative number of] lines"...)

little joey, I got your first code accepted by inserting this line after scanf("%d", &islands):

Code: Select all

if (islands < 0) { printf("Larry and Ryan will be eaten to death.\n"); continue; }

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sat Oct 22, 2005 4:01 pm

Alow me to swear in my mother tongue: G0DV3RD0MM3 !*&#*&$

You're right mf, thank you very much.

This is ridiculous. This means that L&R get eaten if the number of Islands is negative, even if the start and target island are close enough to be reached ?!?!

This also explains why some people now get TLE (while(islands--){ ...}).

This problem definitly needs re-rejudging (and I want my perfect score 6 AC for 6 submissions for the contest back...).

User avatar
Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho » Sat Oct 22, 2005 4:06 pm

little joey wrote:Alow me to swear in my mother tongue: G0DV3RD0MM3 !*&#*&$

You're right mf, thank you very much.

This is ridiculous. ...
You've just typed everything that I want to say.
So I save mine.

Btw, I couldn't imagine what Adrian K

Post Reply

Return to “Volume 109 (10900-10999)”