Page 1 of 3
10793 - The Orc Attack
Posted: Sun Dec 12, 2004 11:19 am
by harry
Hi every body.
this problem seems to be easy.
what i have done is
1. i used floyd warshall for shortest distance
2. then check whether any point exist which is equidistance from 1,2,3,4,5
(the fr five points)
3.if such point exists then did what the problem said.
sorry for paosting the code.
but i have got w.a. for 15 times.tried with all possible ways.
plz help
Posted: Sun Dec 12, 2004 11:50 am
by Eduard
Code: Select all
There may be multiple occurrences of the same U, V pair in the input - it is up to you to decide which one to use
Which one have You used???
Posted: Sun Dec 12, 2004 12:11 pm
by harry
the shortest one.
if(G[s][e]>cost)
{
G[s][e]=cost;
G[e][s]=cost;
}
hope i am right
Posted: Sun Dec 12, 2004 1:51 pm
by krijger
Your floyd-warshall is incorrect. The 'intermediate' node should be in the outer loop.
Posted: Sun Dec 12, 2004 2:00 pm
by shamim
Another issue, although not important,
what is the need for this:
[cpp]
if(s>e)
{
i=s;
s=e;
e=i;
}
[/cpp]
Posted: Sun Dec 12, 2004 6:00 pm
by harry
thanks a lot.really a silly mistake.thanks onece again.
10793,How node 7 has a cost of 51???
Posted: Sun Dec 12, 2004 7:17 pm
by TISARKER
I read the problem again and again.
But I don't understand How the node 7 has a cost of 51 where I think
node has a cost of 52 as the farthest point.
If I wrong , Please show me the path where node 7 has a cost of 51.
Posted: Sun Dec 12, 2004 8:55 pm
by kmhasan
Try 7-8-4-6-10. The cost would be 2+10+4+35=51.
Posted: Mon Dec 13, 2004 6:21 am
by TISARKER
Thank u Boss.Actually I am a dull student.
So for this, I couldnot solve this probem in the NCPC2004.
But as a Programmer, I should catch this problem.
Ok Thanks.
May Allah make u as a more good PS in future.
**** PS means "Problem Setter" not "Private Secretary"
Posted: Thu Dec 16, 2004 3:22 am
by technobug
Hey people, I am trying the same idea as his (simple floyd warshall then look for the best vertex) but gets WA... tried a few test cases which I tried to find my problem but did not work out.
The algo is basically the same as his (therefore I did not specify it that much, there are a few comments though)
[cpp]
ABCDE
[/cpp]
Any ideas?
Posted: Thu Dec 16, 2004 7:55 am
by Cho
hi, technobug, your code fails on this input:
Code: Select all
1
7 5
1 6 1
2 6 1
3 6 1
4 6 1
5 6 1
The correct output should be "Map 1: -1".
Posted: Thu Dec 16, 2004 4:04 pm
by Eduard
I'm getting this problem WA.Please someone give me some tests.
Thanks.
Posted: Thu Dec 16, 2004 4:52 pm
by unknown_error
Edward,
this is a simple problem and no special case is there. do exactly according to description. first found the rally point(s). for each point find the max distance to all nodes fron the rally node. ( search from 1 to n node. take the max value. suppose there 10 nodes and the rally node is 7. suppose 7 is connected to all nodes except node 9. then the max value will be infinity. otherwise the max of all nodes ). if u got several such rally nodes take the minimal max value of the rally points.
if there are any isolated node then output is -1. ( unfortunately i overlook this part and got WA in the contest. )
else if there is no rally point then output is -1
else output according to description.
if u also fails afterall, try to recode it or check I/O, initiaization or you floyed-warshall code.
Posted: Thu Dec 16, 2004 5:05 pm
by Larry
Code: Select all
FOR(j,n) {
if(con[i][j] && dmax<mat[i][j]) dmax = mat[i][j];
}
The rally point has to be connected to every other point..
Posted: Thu Dec 16, 2004 6:26 pm
by technobug
Larry wrote:Code: Select all
FOR(j,n) {
if(con[i][j] && dmax<mat[i][j]) dmax = mat[i][j];
}
The rally point has to be connected to every other point..
Thanks Cho, Larry....
So I added something:
Code: Select all
FOR(j,n) {
// skip it if not connected
if(i!=j && !con[i][j]) goto f;
if(con[i][j] && dmax<mat[i][j]) dmax = mat[i][j];
}
It corrected the sample input from Cho but did not gimme acc... looks like I did what unknown_error said, I will check it again later today...