173 - Network Wars

[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]

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]

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]

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]

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]

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]

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]

Finally AC. Thanks Sumudu.

[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]

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]

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]

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]

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]

// 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]

My AC code prints:
Paskill trapped in node B Lisper destroyed in node A