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 » Wed Jan 12, 2005 9:49 pm

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 » Thu Jan 13, 2005 12:14 am

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 » Thu Jan 13, 2005 2:16 am

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.

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

Post by Abednego » Thu Jan 13, 2005 2:34 am

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 » Thu Jan 13, 2005 2:55 am

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 » Thu Jan 13, 2005 3:05 am

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 » Thu Jan 13, 2005 3:08 am

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

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

Post by Abednego » Thu Jan 13, 2005 3:39 am

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 » Thu Jan 13, 2005 3:51 am

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 » Thu Jan 13, 2005 4:41 am

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 » Thu Jan 13, 2005 8:18 pm

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 » Thu Jan 13, 2005 8:29 pm

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 » Thu Jan 13, 2005 10:36 pm

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.

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

Post by Abednego » Thu Jan 13, 2005 11:09 pm

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 » Fri Jan 14, 2005 12:55 pm

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)”