Problem 5 - Tennis Robot II

Here, we will discuss the solution to Tennis Robot II from AIO 2024.

Solution

Subtask 1: N, M ≤ 1000 and X_i ≤ 1000 for all i

We could try simulating the robot's instructions while storing the current number of tennis balls in each bin. We stop if the robot attempts to take from an empty bin:

• Unfortunately, if the robot never crashes, our solution will run forever.
• Instead, we could simulate up to some maximum number of instructions. If the robot doesn't crash we will assume it runs forever.
• We need to be careful: if we don't simulate enough instructions, our solution might incorrectly assume the robot runs forever when it actually does crash later on.

Let's call a sequence of M instructions a round. Then, each of the N bins falls into one of three categories:

1. Type 1: The number of balls in the bin is the same at the end of the round as it was at the beginning. That is, the number of balls that leave the bin during each round is the same as the number of balls that enter the bin.
2. Type 2: The number of balls in the bin is less at the end of the round than it was at the beginning. That is, the number of balls that leave the bin during each round is more than the number of balls that enter the bin.
3. Type 3: The number of balls in the bin is more at the end of the round than it was at the beginning. That is, the number of balls that leave the bin during each round is less than the number of balls that enter the bin.

Let's make (and prove) our first observation for this problem. Any bin could cause the robot to crash during the first round. However, after the first round, only type 2 bins can crash the robot. Proof:

• First, note that the exact same instructions are run during each round.
• If a bin did not cause the robot to crash during the first round, then it can only cause the robot to crash in a later round if it begins the later round with fewer balls.
• Only type 2 bins meet this criteria. Therefore, only type 2 bins can crash the robot after the first round.

Now let's make another observation: In subtask 1, we need to simulate at most 1001 rounds. Proof:

• In subtask 1, each bin starts with at most 1000 balls.
• The number of balls in each type 2 bin decreases by at least 1 during each round.
• This can happen at most 1000 times before crashing the robot.

This gives us a solution: simulate for 1001*1000 = 1001000 operations. If the robot does not crash, then it must run forever.

Subtask 2: A_j ≠ A_k for all j ≠ k

The subtask 1 solution needs to simulate 1000001*200000 = 200000200000 operations in this subtask. This is too slow and we need a faster approach.

Observation: In this subtask, the robot will not crash in the first round. Proof:

• In this subtask, all instructions take tennis balls from different bins.
• Therefore, the number of balls in each bin decreases by at most 1 each round.
• Each bin starts with at least 1 ball, and so cannot cause the robot to crash in the first round.

Observation: In this subtask, only type 2 bins can cause the robot to crash. Proof:

• In subtask 1, we proved that only type 2 bins can crash the robot after the first round.
• In this subtask, the robot will always crash after the first round.

Solution: We simulate the first round and determine all the type 2 bins:

• If there are no type 2 bins, then the robot will run forever.
• Otherwise, let i be the type 2 bin with the smallest X_i. Because X_i will decrease by 1 each round, we know that the robot will crash in the (X_i+1)th round.
• We can jump forward X_i rounds by subtracting X_i from each type 2 bin.
• We then simulate the (X_i+1)th round and stop once the robot crashes.

This has a time complexity of O(N+M), which is fast enough to solve this subtask.

The below video shows an example of this algorithm.

Full Solution

There are 2 key issues with the subtask 2 solution:

1. In subtask 2, the robot will never crash during the first round. In subtask 3, it can crash during the first round.
2. In subtask 2, every type 2 bin decreases by 1 ball each round. In subtask 3, a type 2 bin can decrease by more than 1 ball in each round.

The first issue is simple to fix: when we simulate the first round, we check whether the robot crashes. The second issue is more complicated to fix:

• Let D_i be the net decrease of bin i in a single round.
• Then, each type 2 bin will crash during or before round ⌊X_i/D_i⌋+1. For example, if X_i = 7 and D_i = 2, then after 4 rounds the robot must have crashed.
• However, it is possible that the robot may have crashed in an earlier round. For example, consider the following input:

  2 10
  7 7
  1 2
  1 2
  1 2
  1 2
  1 2
  1 2
  2 1
  2 1
  2 1
  2 1

• Bin 1 is a type 2 bin with a net decrease of 2 (because 6 balls leave the bin and 4 balls enter the bin). However, bin 1 will crash the robot during the 2nd round, not the 4th round:
  • At the start of the second round, bin 1 has 5 balls. The next 6 instructions each take 1 ball away, which will crash the robot.
• We need to consider both the net decrease and the maximum decrease during each round:
  • In the example, bin 1 has a net decrease of 2 and a maximum decrease of 6.
  • Let the net decrease be D_i and the maximum decrease be E_i. Then, bin i will crash the robot during round ⌊(X_i-E_i)/D_i⌋ + 2.

Putting this together, we get a solution:

• Simulate the first round. If the robot crashes, then we are finished.
• Otherwise, if there are no type 2 bins, the robot will run forever.
• If there are type 2 bins, then calculate D_i and E_i for each of them.
• Calculate the minimum ⌊(X_i-E_i)/D_i⌋ + 2 across all type 2 bins. This is the round when the robot will crash.
• Skip ahead to the round and then simulate it to determine exactly when the robot will crash.

This has a time complexity of O(N+M).

Click here to go back.