Official algorithmic problem description and constraints.
There are 100 rooms arranged in a row and 99 doors between them; the i-th door connects rooms π and π+1.
Each door can be either locked or unlocked. Initially, all doors are unlocked.
We say that room π₯ is reachable from room π¦ if all doors between them are unlocked.
You know that:
However, you don't know the exact rooms they are in.
You don't want Alice and Bob to be able to reach each other, so you are going to lock some doors to prevent that. What's the smallest number of doors you have to lock so that Alice and Bob cannot meet, regardless of their starting positions inside the given segments?
Detailed video explanations, mathematical intuition, and clean C++ implementation code.