Solution to ZCO13004 (Save Spaceman Spiff) not what author intended?

general
,
1

According to the discussion boards, the expected solution for this problem is O(NM + K(N+M)). There was some talk about poor test cases being fixed, but I think the problem itself may be flawed.

When a pulse occurs at a time point that could potentially block Spiff, that pulse may become synchronized with Spiff (since they move at the same speed) along both the X & Y axis’, effectively segregating some lower-right portion of the grid and making the goal unreachable for all paths.

Also blasters appear to be independent (i.e., there are no cases where the combined effects of blasters would block Spiff where individually they could not), making a synchronized pulse the only way to stop Spaceman Spiff.

Therefore, the problem becomes: Will Spiff synchronize with any reachable pulse? Which can be solved in O(K) (See solution here). Is this right?

2

Sharing the question link will allow more people to comment and get what you are saying.

3

Ah, that’s a very interesting approach :slight_smile: But I don’t think it works. Take this example:
2 2 1
2 2 0 1000
The correct answer is NO, but I believe your logic will say YES.

You are absolutely correct in saying that if Spiff is synchronized with any reachable pulse, then the answer is NO. But that is not the only way. In particular, your solution would work if each blaster sends pulses only towards the right and down. But what about the pulses going up and to the left? Your syncing trick won’t work for them.

Also, you can make larger cases similar to what I’ve given above, in which multiple blasters work together to block Spiff’s path, using their up and left pulses.

But it does look like the current testdata doesn’t consider this. I’ll see if we can upload some files with this counter.

1 Like