Connection Status:
Competition Arena > LinearKingdomParkingLot

LinearKingdomParkingLot

TCO10 Round 5 · 2010-04-11 · by dolphinigle

TCO10 Round 5 · 2010-04-11 · by dolphinigle · Dynamic Programming
Class Name: LinearKingdomParkingLot
Return Type: int
Method Name: borrowKeys
Arg Types: (vector<int>)
Problem Statement

Problem Statement

NOTE: This problem statement contains images that may not display properly if viewed outside of the applet.

Gogo runs a parking lot in Linear Kingdom. This parking lot consists of consecutive cells spanning infinitely from left to right. There's only one entrance to the parking lot and it's located at an arbitrary cell. Below is a picture portraying a possible layout for his parking lot.

Note that the arrow in the image above is pointing to the entrance cell.

Today, N cars (numbered 0..N-1 by their order of arrival) are going to be parked in his parking lot. Initially, the parking lot is empty (that is, all cells are empty). Then, starting with car 0, the cars will arrive one at a time. Gogo will park each car as it arrives in an empty cell that is reachable from the entrance through a series of empty cells. Gogo will choose the cells in such a way that there will always be a reachable cell for all N cars.

After all the cars are parked, they will exit the parking lot in the order given in int[] exitOrder. The car numbered exitOrder[0] is the first car to exit, the car numbered exitOrder[1] is the next one, and so on. For a car to exit the parking lot, Gogo must drive some other cars (or none at all) out of the parking lot first until it is possible to reach the entrance from the corresponding cell. After the car gets out, Gogo must return all the cars he drove out back into the parking lot in any order and not necessarily back to their original positions. In order for Gogo to drive a car out of the parking lot, he must borrow the key from its owner. Once he has borrowed a key, he can then drive that car out and back in an arbitrary number of times. Note that the car that is about to exit the parking lot will not be driven by Gogo but by its owner.

Return the minimum number of keys Gogo will need to borrow so that there exists a way to park all the cars and to let them exit later with the method described above. Assume that exitOrder is known to Gogo before the cars even start to arrive.

Constraints

  • exitOrder will contain between 2 and 50 elements, inclusive.
  • Each element of exitOrder will be between 0 and N-1, inclusive, where N is the number of elements in exitOrder.
  • All elements of exitOrder will be distinct.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
{4,1,0,2,3}
Returns: 1

Let us number the cells ..., -4, -3, -2, -1, 0, 1, 2, 3, 4, ..., where cell 0 is the entrance cell. One of the optimal configurations is achieved by parking car 0 at cell -3, car 1 at cell -2, car 2 at cell 3, car 3 at cell 2, and car 4 at cell -1. This configuration corresponds to the picture above, and Gogo will only need to borrow the key for car 3.

1)
{0,1}
Returns: 0

Sometimes, it is not necessary to borrow any key.

2)
{1,3,5,7,0,2,4,6}
Returns: 4
3)
{1,0}
Returns: 0
4)
{0,1}
Returns: 0

Submissions are judged against all 150 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LinearKingdomParkingLot with a public method int borrowKeys(vector<int> exitOrder) · 150 test cases · 2 s / 256 MB per case

Submitting as anonymous