173 - Network Wars

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

Moderator: Board moderators

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Post by paulhryu »

Okay, first of all, a trap takes a unit of time. That is, at one time the program may enter into a position but until the next unit of time the program does not realize it is trapped. That is why the trap and then annihilate can happen. Just make sure annihilate and destroy don't both happen.

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

Post by paulhryu »

If that wasn't helpful, email me (click the little thingy on the bottom) with the complete code or go to my website to find a full program, which I suggest you not to do but may be helpful.

Lawrence
New poster
Posts: 17
Joined: Sat Feb 09, 2002 2:00 am
Location: China
Contact:

Post by Lawrence »

I don't know why you get WA, but the following is my 'moving sequence', since I got accepted, it might help.

1. Move paskill.
2. If paskill trapped print
3. Move lisper.
4. If lisper destroyed print
5. If both annihilated print
6. If lisper trapped print

rbuchan
New poster
Posts: 27
Joined: Fri Feb 28, 2003 7:59 am
Contact:

173 - Network Wars

Post by rbuchan »

Does anyone have any test data, more than what is with the problem? I have walked through several scenarios I created, but get correct answers.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity »

You can get some tests at http://acm.uva.es/board/viewtopic.php?t=196, but my solution gives correct anwers to all of them and still WA with OJ... :( If anybody have other sample imputs, or AC'd code please, post them here.

halyavin
New poster
Posts: 3
Joined: Thu Nov 06, 2003 4:36 pm

173 - Network Wars. Can't understand problem.

Post by halyavin »

Give me right output:
Input
A:B;B:D;D:C;C:A. A D
#
Give others examples, please. I have WA for all variants of output for this input.

Quantris
Learning poster
Posts: 80
Joined: Sat Dec 27, 2003 4:49 am
Location: Edmonton AB Canada

Post by Quantris »

I just got AC in this problem, here's a description of my decision tree:

1. If both start in the same place, output "both annihilated" and that's all (not sure if this occurs in the data though) EDIT: it does.

2. Find the next position for paskill and lisper (when doing paskill, you assume he cannot move into lispers current position).

3. If paskill can't move, print that he is trapped. This is the only way that
you can output more than one message.

4. Check if lisper is trapped, annihilates both, or gets destroyed (at most one can happen) -- if so print it.

5. If you didn't finish, update the positions and continue.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon »

Finally AC. :lol: Thanks Sumudu.

lord_burgos
New poster
Posts: 43
Joined: Mon Oct 13, 2003 4:54 pm
Location: Mexico
Contact:

Post by lord_burgos »

input

Code: Select all

A:BD;C:BD;F:E;G:DEH;H:EG. A H 
E:AB. A B 
B:ACD. B D 
A:B;B:C;D:E. A D 
A:A. A A 
A:B. A B 
A:B. B A 
A:B. C C 
A:B. C D 
A:B;C:BDE;F:EG;G:H. A H 
A:B;C:BDE;F:EG;G:H. A G 
A:B;C:BE;F:EG;G:H. A G 
A:B;C:BDE;F:EG;G:H. H C 
A:B;C:BDE;F:EG;G:H. B H 
A:B;C:BDE;F:EG;G:H. B E 
A:B;C:BDE;F:EG;G:H. C B 
A:BD;C:BD;F:E;G:DEH;H:EG. A H 
E:AB. A B 
B:ACD. B D 
A:B;B:C;D:E. A D 
A:BD;C:BD;F:E;G:DEH;H:EG. A H
E:AB. A B
B:ACD. B D
A:B;B:C;D:E. A D
A:A. A A 
A:B. A B 
A:B. B A
A:B. C C 
A:B. C D 
#
My AC Output is

Code: Select all

Paskill trapped in node D Lisper trapped in node F
Both annihilated in node E
Lisper destroyed in node B
Lisper trapped in node E
Both annihilated in node A
Paskill trapped in node A Both annihilated in node A
Paskill trapped in node B Both annihilated in node B
Both annihilated in node C
Paskill trapped in node C Lisper trapped in node D
Paskill trapped in node D Lisper destroyed in node C
Lisper destroyed in node C
Paskill trapped in node C Both annihilated in node C
Lisper trapped in node A
Paskill trapped in node D
Both annihilated in node C
Paskill trapped in node D Lisper trapped in node A
Paskill trapped in node D Lisper trapped in node F
Both annihilated in node E
Lisper destroyed in node B
Lisper trapped in node E
Paskill trapped in node D Lisper trapped in node F
Both annihilated in node E
Lisper destroyed in node B
Lisper trapped in node E
Both annihilated in node A
Paskill trapped in node A Both annihilated in node A
Paskill trapped in node B Both annihilated in node B
Both annihilated in node C
Paskill trapped in node C Lisper trapped in node D

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

The problem says: "if either (or both) cannot move both will halt", so if Paskill is stuck (cannot move), wouldn't Lisper halt? (and thus cannot be destroyed or annihilated).

I think the wording of the problem does not match the data....

rickyliu
New poster
Posts: 30
Joined: Thu Sep 28, 2006 7:16 am

Post by rickyliu »

yiuyuho wrote:The problem says: "if either (or both) cannot move both will halt", so if Paskill is stuck (cannot move), wouldn't Lisper halt? (and thus cannot be destroyed or annihilated).

I think the wording of the problem does not match the data....
I don't think so. The question said:
Both programs move through the network at the same speed.
Thus, both Paskill and Lisper move simultaneously. When Paskill is being stuck, Lisper is still moving, and vice versa.

Apart from this case, I agreed with you for the case where both start at the same node. The question said:
if they ever arrive at a node simultaneously they annihilate each other.
It depends on how you interpret *arrive*. I think *start* and *arrive* are different. Maybe just because of my poor English...

nbauernf
New poster
Posts: 5
Joined: Thu Mar 08, 2007 4:33 am

173 Network Wars

Post by nbauernf »

I'm getting WA for this problem and I've written and re-written my solution and can't seem to get it.

I pass all of the tests found here: http://acm.uva.es/board/viewtopic.php?t=196

So I'm not really sure where the problem is. Anyone else have extra test sets? Any common common mistakes?

Are there more output combinations in addition to these (or are any of these extraneous?):
1) Paskill trapped in node %c
2) Paskill trapped in node %c Both annihilated in node %c
3) Paskill trapped in node %c Lisper trapped in node %c
4) Paskill trapped in node %c Lisper destroyed in node %c
5) Lisper trapped in node %c
6) Both annihilated in node %c
7) Lisper destroyed in node %c

Thanks

nbauernf
New poster
Posts: 5
Joined: Thu Mar 08, 2007 4:33 am

Post by nbauernf »

Nevermind =). I was missing two edge cases. In particular (for anyone else looking for ideas) I made a mistake when paskill was in 'Z' and when lisper was in 'A'. And all of those statements above are necessary.

yanli
New poster
Posts: 1
Joined: Sat Feb 16, 2008 8:19 am

AC for problem 173 Network Wars

Post by yanli »

// Important: The problem mentioned rules
// 1. Paskill move next: next cannot be a node already visited by Paskill, neither can it be a node already visited by Lisper
// 2. Lisper move next: next cannot be a node already visited by Lisper, but it may be a node already visited by Paskill
// 3. Destroy rule: Lisper entered a node visited by Paskill but NOT the node Paskill is currently in
// 4. Both Annihilate rule: Lisper's next pos and Paskill's next pos coincides, the next pos is the same as current pos if no move possible, i.e., it is trapped.
// 5. Additional clarification: if both start in the same node, output both annihilate and then finished

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 173 - Network Wars. Can't understand problem.

Post by brianfry713 »

My AC code prints:
Paskill trapped in node B Lisper destroyed in node A
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 1 (100-199)”