Marathon Match 102 - Marathon Match 102

Problem Statement

Overview

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.

Method Description

Your code should implement a single method, planShipping that takes the following parameters:

• int truckFixedCost: The fixed cost of a truck shipment.
• int truckVariableCost: The variable cost of a truck shipment.
• int[] warehouseX: The x-coordinate of a warehouse.
• int[] warehouseY: The y-coordinate of a warehouse.
• int[] warehouseItem: The item stocked in that warehouse.
• int[] warehouseQuantity: The quantity of that item in the warehouse.
• int[] customerX: The x-coordinate of a customer.
• int[] customerY: The y-coordinate of a customer.
• int[] customerItem: The item number ordered by a customer.

The warehouse inputs arrays are all the same length, and the customer input arrays are all the same length. They work together as follows:

• There are warehouseQuantity[i] of item number warehouseItem[i] in a warehouse located at (warehouseX[i], wearhouseY[i]).
• A customer located at (customerX[i], customerY[i]) ordered item number customerItem[i].

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:

• "T,startX,startY,endX,endY,itemNumber,itemNumber,itemNumber ..."
• "C,startX,startY,endX,endY,itemNumber"

Test Case Generation

• truckFixedCost is selected between 5 and 50
• truckVariableCost is selected between 1 and 20
• The number of warehouses are chosen, between 3 and 20, and their placements selected at random
• The number of different items is chosen, between 10 and 100.
• The number of customers is chosen, between 20 and 1000, along with their location and selected item
• Each item is stocked in quantity between N and N * 1.5, where N is the number of customers that ordered the item
• The stock of each item is divided across (up to) 3 warehouses.

See the offline tester for more details about test case generation.

Scoring

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

• Each test case is limited to 10s and 1GB memory
• There will be 50 provisional tests and 1000 system tests

Offline Tester

An offline tester is available here.

Definition

Examples