A city is described as a 2D grid from (0,0) to (1000,1000). You are starting a new company, Ganges, that specializes in online order and delivery of various products. You have several warehouses that stock different products, at various locations around the city, and customers have ordered various products.
Each customer orders only a single item, however there may be multiple orders, possibly even for the same item, that go to the same point on the map.
Shipment of products happens via two methods: trucks and couriers. Trucks can transport any number of items between any two points on the map, but cannot deliver directly to customers. A courier takes a single item at a time, and delivers it to a customer. Note that while items are initially stocked only at warehouses, trucks can move any number of those items arbitrarily around the map, to any given point.
The cost of shipping by truck is made of two components: fixed and variable. The fixed cost is a one-time cost associated with every truck or courier that does a delivery. The variable cost refers to the cost per block of transport (calculated as Manhattan distance). For example, with a fixed cost of 10 and a variable cost of 3, a transport running from (2,3) to (5,8) has a Manhattan distance is 8, then we can calculate the total cost as 10 + 8 * 3 = 34.
Courier shipments always incur a cost of 1 per unit of Manhattan distance. So in the previous example, it would be a cost of 8.
Your code should implement a single method, planShipping that takes the following parameters:
The warehouse inputs arrays are all the same length, and the customer input arrays are all the same length. They work together as follows:
Your code should return a String, where each element represents a truck or courier shipment. The order of the elements is the order in which the shipments should take place. The string should be in the following forms for truck or courier shipments:
Test Case Generation
See the offline tester for more details about test case generation.
Your raw score for a test case will be equal to the total delivery costs, plus a penalty of 10,000 for each item not delivered. Your overall score will be the sum of BEST/YOUR across all test cases, where BEST is the lowest anyone scored on a given test case, and YOUR is your score on that test case.
Any attempt to do a transport of an item that does not exist at the start location will result in failing the test case. Similarly, attempting a transport that starts or ends outside of the city limits will also result in a failure. Any test cases that fails, exceed the memory or time limit, runtime error, etc, will score -1, and will not award any points towards you overall score.
Limits and Test Cases
An offline tester is available here.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2020, TopCoder, Inc. All rights reserved.