Minimum Robots to Capture Sara
Given a tree of N outposts (2 ≤ N ≤ 7×10⁴) connected by N-1 bidirectional tunnels where leaf nodes are exits, determine the minimum number of robots starting at exit outposts needed to guarantee catching Sara, who starts at a given outpost K and moves optimally to escape.
Asked at:
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid April, 2026
Senior
Cornered at last, Sarah Connor has gone to ground in a remote compound. The compound consists of N outposts (2≤N≤7 * 10^4) and N−1 bidirectional tunnels between outposts, so that there is a unique path between every pair of outposts. Every outpost which has only one tunnel is an EXIT. When morning comes, Sarah Connor will surface at some outpost and attempt to reach an EXIT. But the moment Sarah Connor surfaces at some outpost, the SKYNET surveillance system will be able to pinpoint her location. Some T2 robots will then start at various EXIT outposts, and attempt to catch Sarah Connor. The T2 robots move at the same speed as Sarah Connor (so in each time step, each T2 can move from one outpost to an adjacent outpost). The T2 robots know where Sarah Connor is at all times, and Sarah Connor knows where the T2 robots are at all times. The T2 robots catch Sarah Connor if at any instant a T2 is in the same outpost as Sarah Connor, or crossing the same tunnel as Sarah Connor. Conversely, Sarah Connor escapes if she reaches an EXIT outpost strictly before any T2 robots catch her. Question Sarah Connor is unsure at which outpost she should surface. GIVEN a starting position, help Sarah Connor determine the minimum number of T2 robots who would be needed to catch Sarah Connor if she surfaced there, assuming that the T2 robots distribute themselves optimally among the EXIT outposts. Inputs: Inputs: The first line of the input contains two numbers: N, K. N is the number of outposts. K is Sara's starting position. Each of the following N−1 lines specify two integers, each in the range 1…N, describing a tunnel between two outposts. Outputs: Please output the minimum number of T2 bots needed to ensure catching Sarah. Sample SAMPLE INPUT: 7 1 1 2 1 3 3 4 3 5 4 6 5 7 SAMPLE OUTPUT: 3 Explanation Compound structure 4 - 6 | 3 - 1 - 2 | 5 - 7 Sara starts at outpost 1 . To capture Sara, placing robot at 2, 6, 7 is required. STEP-BY-STEP First step: Sara moves from 1->3 (EXIT 2 is occupied by a robot, that robot can capture Sara if Sara moves from 1->2 while the robot moves from 2->1). Robots at 6,7 move to 4,5 respectively in first step, robot at 2 will move to 1. Second step: Sara will be caught because she is surrounded in all three directions. No matter which way she picks, she will travel across a tunnel that a robot also travels at the opposite direction. (all robots are moving toward outpost 3)
Your account is free and you can post anonymously if you choose.