## 10803 - Thunder Mountain

Moderator: Board moderators

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

### 10803 - Thunder Mountain

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...???

Yandry.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
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
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:
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
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
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
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:
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
Ok, i will try again tomorrow, thanx for your help!!!

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
I have solved it . 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:
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
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:
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:
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
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