10793 - The Orc Attack

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

Moderator: Board moderators

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

10793 - The Orc Attack

Post by harry » Sun Dec 12, 2004 11:19 am

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

Code: Select all

got ac
Last edited by harry on Sun Dec 12, 2004 6:01 pm, edited 1 time in total.

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

Post by Eduard » Sun Dec 12, 2004 11:50 am

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??? :roll:
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Sun Dec 12, 2004 12:11 pm

the shortest one.


if(G[s][e]>cost)
{
G[s][e]=cost;
G[e][s]=cost;
}
hope i am right

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am

Post by krijger » Sun Dec 12, 2004 1:51 pm

Your floyd-warshall is incorrect. The 'intermediate' node should be in the outer loop.

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by shamim » Sun Dec 12, 2004 2:00 pm

Another issue, although not important,

what is the need for this:
[cpp]
if(s>e)
{
i=s;
s=e;
e=i;
}
[/cpp]

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Sun Dec 12, 2004 6:00 pm

thanks a lot.really a silly mistake.thanks onece again.

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

10793,How node 7 has a cost of 51???

Post by TISARKER » Sun Dec 12, 2004 7:17 pm

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.
Mr. Arithmetic logic Unit

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Sun Dec 12, 2004 8:55 pm

Try 7-8-4-6-10. The cost would be 2+10+4+35=51.

TISARKER
Learning poster
Posts: 88
Joined: Tue Oct 12, 2004 6:45 pm
Location: Bangladesh
Contact:

Post by TISARKER » Mon Dec 13, 2004 6:21 am

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"
Mr. Arithmetic logic Unit

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

Post by technobug » Thu Dec 16, 2004 3:22 am

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?
Last edited by technobug on Thu Dec 16, 2004 10:39 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 » Thu Dec 16, 2004 7:55 am

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

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

Post by Eduard » Thu Dec 16, 2004 4:04 pm

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

unknown_error
New poster
Posts: 5
Joined: Fri Dec 10, 2004 9:42 am

Post by unknown_error » Thu Dec 16, 2004 4:52 pm

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.

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

Post by Larry » Thu Dec 16, 2004 5:05 pm

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

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

Post by technobug » Thu Dec 16, 2004 6:26 pm

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

Post Reply

Return to “Volume 107 (10700-10799)”