CommonLounge Archive

[GCJ101BB] Picking Up Chicks

April 15, 2019

Link to Problem: Problem GCJ101BB

Clearer problem statement:

There are N chickens.

Each chicken has a starting position X[i], and a speed V[i]. They start at their starting location, and are running at the speed of V[i] towards the right.

You want K chickens to reach the barn before time T. The barn is located at location B.

The problem is that if a chicken has a slower chicken in front of it, it is not able to overtake it unless you do an “allow overtake” (in the problem, this is called “swapping”).

You want to minimize the total number of “allow overtake” / “swaps” so that at-least K chickens reach the barn before time T.

© 2016-2022. All rights reserved.