2
$\begingroup$

A criminal has been spotted along a straight single-filed road of length $L$ at position $P$, measured from the left endpoint of the road! Two police officers arrive to the road at positions $A$ and $B$ respectively, also measured from the left endpoint of the road. The chase begins! Pursuit occurs in 1 time unit intervals, of which the following can happen in order:

  1. The police officers can choose to wait, or move to the left or right of where they are by 1 unit distance.

  2. The criminal can choose to wait, or move to the left or right of where he is by 1 or 2 unit distance. However, if a police officer occupies the same position as the criminal, he can only move 1 unit distance now as he needs to perform a manoeuvre to evade them!

  3. The police officer captures the criminal!

What is the longest time the criminal can evade the police officers for, assuming optimal decision making from all parties?

Assume the following:

  • $1 \leq L \leq 1000$
  • $0 \leq A \leq L$
  • $0 \leq B \leq L$
  • $0 \leq P \leq L$
  • $A \ne B \ne P$.

Seems like a classic pursuit-evasion question. However, I seem to be missing something. These are my following considerations thus far:

  1. Start tracking $T$, the time the criminal has evaded the police officers for so far.
  2. First, I will just consider $A < B$ as I can freely swap the police officer's positions anyway.
  3. If the criminal is to the left or right of both police officers, i.e. $P < A$ or $P > B$ where he is not in between them, he can only run to the left or right end of the road, so I will arbitrarily just set $P$ to either be $0$ or $L$. Else, I will note that he was between the officers.
  4. Now, I will make the police officers travel together. This stops the criminal from evading the police officers multiple times in a row if they happen to end up on the same square. So while $B - A > 2$, I will move $B$ to the left and $A$ to the right. Of course, this takes time in itself, so I will increment $T$ for every movement they make.
  5. So here, if the criminal is actually at an endpoint, the solution is fairly simple. You wil simply move either $A$ to the right if the criminal is at the right endpoint ($P = L$) by $L - A - 1$ units, or move $B$ to the left if the criminal is at the left endpoint ($P = 0$) by $B - 1$ units, and catch the criminal there.
  6. However, if the criminal was originally between the officers, I now need to check if there is a space between the officers, and subsequently either move $A$ to the right or $B$ to the left (and also increment $T$). Then, I can say that the officers will catch the criminal in $max(A, L - B)$.

Logically this makes sense to me, but yet it is not the correct answer (solution is implemented as code and ran against test cases using judging software). Any hints or ideas?

$\endgroup$
5
  • $\begingroup$ The way your 3 steps read now I don't see how the police officers can ever catch the criminal. In step 1 assume one police officer moves onto the spot where the criminal is, the second one is either to the left or to the right (one or several steps). Now it is the criminals turn who will move one step away from the second one. So the criminal is not caught. With two policeman there doesn't seem to be a configuration where they actually catch the criminal. $\endgroup$
    – quarague
    Nov 25, 2023 at 21:14
  • $\begingroup$ Probably among your assumptions you meant to include that A, B, and P are integers. $\endgroup$
    – msh210
    Nov 25, 2023 at 22:10
  • $\begingroup$ @msh210 Indeed. Thanks for pointing it out. $\endgroup$
    – Kevin
    Nov 26, 2023 at 4:02
  • 1
    $\begingroup$ Your third assumption seems to be faulty. when P=1, A=2, B=10, there is the option of A moving 1 left, then P moving 1 right. So P doesn't always move left when P<A. $\endgroup$
    – justhalf
    Nov 27, 2023 at 5:48
  • 3
    $\begingroup$ Welcome to Puzzling, take our tour! Could you please provide proper attribution for this question? $\endgroup$
    – LeppyR64
    Nov 27, 2023 at 12:18

1 Answer 1

3
$\begingroup$

First of all, how can the criminal even get caught?

The criminal has three possible moves: move left, stay still, or move right. Each cop can catch the criminal after at most one of these moves, so the remaining one must be blocked by the end of the road.

The last turn will proceed as follows (WLOG, at the left end of the road): The cops are at positions 1 and 2, and the crook is at 0. The cops both move left, the crook either waits or moves right 1 sunit (he can't move 2 because a cop just walked up to him), and is captured by one of the cops.

Can the cops arrange this scenario?

Suppose the cops are in adjacent squares. The criminal can't run past them - either he starts in an unoccupied unit, and must move three squares to reach the other side, or he starts in one cop's unit, and can only move as far as the other cop.
Therefore, the cops' best bet is to meet up as soon as possible, and chase the criminal together. If the criminal is not in either of their units, then they both move in his direction. Otherwise, they wait - either the criminal runs away and is chased in the next time step, or is blocked in and arrested.

How long does this take?

The best bet for the cops is to meet up in the middle, no matter what: not only is it the earliest meeting possible, it also minimizes the length the robber can run after they meet. This will take $\lfloor\frac{L}{2}\rfloor$ steps, and then chasing the robber will take another $\lfloor\frac{L}{2}\rfloor$ steps, for a total of $2\lfloor\frac{L}{2}\rfloor$ steps.

$\endgroup$
3
  • $\begingroup$ Doesn't seem to be correct. If $L = 5$, $A =4$, $B= 3$, $P = 2$, you get 4 steps but it should be 3? $\endgroup$
    – Kevin
    Nov 26, 2023 at 4:02
  • 1
    $\begingroup$ @Kevin this answer is considering the worst case given L, and it's not for any arbitrary A, B, P. You can equally also say in the case L=10, A=0, B=1, P=0 it should be 1 step :). That's probably because the ambiguity in the phrase "longest time", which could be interpreted as "worst case". Maybe can rephrase the question to say explicitly along the lines of "given L, A, B, P, what is the time taken to catch the thief assuming best play from both the thief and the police?" $\endgroup$
    – justhalf
    Nov 27, 2023 at 5:44
  • $\begingroup$ @justhalf Thanks. Updated $\endgroup$
    – Kevin
    Nov 27, 2023 at 12:00

Not the answer you're looking for? Browse other questions tagged or ask your own question.