10803 - Thunder Mountain

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

Moderator: Board moderators

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

10803 - Thunder Mountain

Post by neno_uci »

I used this algorithm but i get WA:

1.For each pair of nodes i calculate the distance, if it is less or equal than 10 then d[j] = d[j] = that distance else d[j] = d[j] = infinity.

2.Apply Floyd to find All Pairs Shortest Paths.

3.Then i look for the maximum distance.

What is wrong...???

Thanx in advance,

Yandry. :D

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

Precision errors? Instead of checking (distance <= 10) try checking (distance^2 <= 100) using ints only.

Do you really calculate the distance for all pairs? Also the pairs [i,i]?

Not forgetting the "Send Kurdy" message? No typos?

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci »

I am also getting WA, this is my code.

Code: Select all

Cut after AC...
:(
Last edited by neno_uci on Wed Mar 09, 2005 9:29 am, edited 1 time in total.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego »

Your dis variable is of type "real". So when you compare it to 100 using the <= operator, things will break if dis=100.0000001. I couldn't find any other mistakes on first glance. I've never used pascal, and I don't have a pascal compiler. Otherwise, I could try running your solution on the official input data to see where the mistake is.
If only I had as much free time as I did in college...

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

Problem statement wrote:Put an empty line after each test case.
You're not doing it right, you omit the last one.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci »

Cut after AC...
Last edited by neno_uci on Wed Mar 09, 2005 9:28 am, edited 1 time in total.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci »

Cut after AC...
Last edited by neno_uci on Wed Mar 09, 2005 9:30 am, edited 1 time in total.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego »

I don't think you understood the problem correctly.

"If it is impossible to get from some town to some other town" means "If there exists a pair of towns T and U such that it is impossible to get from T to U".
If only I had as much free time as I did in college...

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci »

Ok, i will try again tomorrow, thanx for your help!!!

:D

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci »

I have solved it :D . I got AC with my C++ code. As Abednego said i had a wrong idea about the problem. Thanx to both of you Abednego and Misof.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug »

hmmmm... am i missing something?

1. connects all which d<=100 (long)
2. sqrt the distance for them
3. floyd it
4. if its not connected, send kurdy
5. if it is, check for the biggest distance
6. round it, print it

Code: Select all

...
Last edited by technobug on Thu Jan 13, 2005 10:35 pm, edited 1 time in total.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

Technobug: When using Floyd-Warshall, the order in which you nest the cycles matters. Yours is wrong. The k-cycle must be the outermost one.

Note that in the correct implementation, after running the k-cycle x times the value in d[p][q] is the shortest p-q path such that all intermediate vertices have numbers not exceeding x. (This is how the algorithm works :))

Also, if you initialize d[j] to a sufficiently large value for i!=j, you may omit the con[][] array from your solution completely. Not that this matters but the presence of the con[][] array makes your implementation unnecesarilly complicated.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:

Post by technobug »

hmmm..... something seemed wrong... thanks misof...

btw, i got everything you sugested, even took out the con array (which i am always afraid, as i usually mess things up)....

the resulting code is much more simple but still did not get it right:

Code: Select all

....


hmmm.... 10000.0 solved the problem :) thanks sir....
Last edited by technobug on Thu Jan 13, 2005 11:34 pm, edited 1 time in total.

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego »

There is a bug in your rounding. Your code always rounds the answers down to the nearest integer, so if the correct answer is 98.4567, your code will print 98.0000.
If only I had as much free time as I did in college...

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard »

Hello.
I'm getting this problem WA.Somebody give me some tests please.
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Post Reply

Return to “Volume 108 (10800-10899)”