Marathon Match 55 - Marathon Match 55

Marathon MatchCompetitive ProgrammingTest Case
Register
Submit a solution
The challenge is finished.

Challenge Overview

Problem Statement

    

In this problem you will guide special trucks around in an underground coal mine. Your goal is to gather as much coal as you can in the smallest time possible. The mine consists of solid rock, solid coal, shafts and some open space around each shaft. Four trucks will enter the mine at each shaft. Solid coal must first be loosened to become loose coal which can be picked up by a truck. Each truck contains a mechanism that can loosen all the solid coal in the 4 cardinal directions around it. A truck can load a certain maximum amount of coal, and should then dump the coal into any shaft. Solid rocks can not be mined. The trucks are so small that all of them can be at the same position at any given time -- trucks do not collide with each other.

Implementation Details

The mine contains H rows and W columns. There are S shafts in the mine. There are S*4 trucks available for mining. Each truck can load a maximum of C coal. You are given the initial state of the mine, the starting position of each truck and the maximum capacity of a truck. You need to return the moves of the trucks such that they maximize the coal gathered and minimize the time in which the coal were collected.

Your code should implement one method gather. A String[] mine describe the initial state of the mine. Each element of the array contains a row of the mine. There will be H rows and each string will contain W characters. The ���#��� character represents solid coal. The ���+��� character represents solid rock which can not be destroyed. The ���S��� character represents a shaft. The ���.��� character represents an open space. truckX and truckY give the starting positions of each truck. The ith element of each array corresponds to the ith truck. truckX contains the zero-based column index and truckY contains the zero-based row index. capacity contains the maximum number of coal that a truck can pick up before it needs to unload the coal.

You must return the moves for the trucks. Your output must contain an array of strings. Each string represents the moves of all the trucks for one time unit. The ith character of the string contains the move for truck i.



Possible moves:
  • N: Moves the truck north. One row up.
  • S: Moves the truck south. One row down.
  • E: Moves the truck east. One column right.
  • W: Moves the truck west. One column left.

    Note: Trucks can not move through solid rock, solid coal or a shaft. When a truck drives over loose coal and the truck has not reached its maximum capacity yet, the loose coal will be loaded onto the truck. A fully loaded truck may not move through loose coal.
  • X: The truck will drill in four directions (North, east, south and west), breaking all solid coal adjacent to the truck. Solid coal will become loose coal which can be driven over. The truck will stay in the same position while drilling.
  • D: The truck will dump the loaded coal into a shaft. All the coal will be unloaded in one time step. The truck must be next to a shaft to be able to dump the coal.
  • P: The truck will be paused and won���t do anything during the time step.

Example:

If there are 4 trucks and your return consists of ���NPXE���, ���EXED���.

Time 1: The first truck will move north, the second truck will do nothing. The third truck will loosen the solid coal around it. The last truck will move east.

Time 2: The first truck will move east, the second truck will loosen coal around it. The third truck will move east. The last truck will dump all its coal into a shaft, assuming that a shaft is next to it. (A truck won���t dump the load if a shaft is not next to it.)

Scoring

You will score 100 points for each coal that is dumped into a shaft. 1 point is deducted for each time step that you use, this relates to the running costs of your trucks. You may only use a maximum of 10000 time steps. All time steps greater than 10000 will be ignored. Your score for a test case will be Max(0, 100*(Coal gathered) ��� (Simulation steps used)). Any invalid move will result in a zero score. Your overall score will be the sum of your scores over all test cases.

Test Case Generation

The width and height of the mine is chosen between 20 and 100. The capacity of the trucks is selected randomly between 1 and 10. There will be between 1 and 10 solid rock formations. There will be between 2 and 10 shafts. Each shaft contains 4 trucks. Areas around each shaft will be cleared from any rock or coal. See visualizer source code for more detail.

Visualizer

A visualizer is available for offline testing.
 

Definition

    
Class:CoalMining
Method:gather
Parameters:String[], int[], int[], int
Returns:String[]
Method signature:String[] gather(String[] mine, int[] truckX, int[] truckY, int capacity)
(be sure your method is public)
    
 

Notes

-W will be chosen uniformly between 20 and 100 inclusively.
-H will be chosen uniformly between 20 and 100 inclusively.
-C will be chosen uniformly between 1 and 10 inclusively.
-S will be chosen uniformly between 2 and 10 inclusively.
-There will be S*4 trucks.
-Maximum of 10000 moves for each truck allowed.
-For more implementation details see the visualizer source.
-The memory limit is 1024 MB and the time limit is 20 seconds (which includes only time spent in your code).
-There are 10 example test cases and 100 full submission test cases.
-A fully loaded truck can not move through loose coal.
-The total score shown on the standings is divided by 10000 for display purposes.
 

Examples

0)
    
"1"
Returns: "seed = 1
W = 27 H = 62
Capacity = 1
Number of trucks = 24"
1)
    
"2"
Returns: "seed = 2
W = 74 H = 86
Capacity = 2
Number of trucks = 8"
2)
    
"3"
Returns: "seed = 3
W = 78 H = 74
Capacity = 3
Number of trucks = 24"
3)
    
"4"
Returns: "seed = 4
W = 41 H = 65
Capacity = 10
Number of trucks = 8"
4)
    
"5"
Returns: "seed = 5
W = 43 H = 68
Capacity = 2
Number of trucks = 28"
5)
    
"6"
Returns: "seed = 6
W = 71 H = 77
Capacity = 3
Number of trucks = 20"
6)
    
"7"
Returns: "seed = 7
W = 80 H = 28
Capacity = 2
Number of trucks = 8"
7)
    
"8"
Returns: "seed = 8
W = 24 H = 35
Capacity = 8
Number of trucks = 24"
8)
    
"9"
Returns: "seed = 9
W = 84 H = 44
Capacity = 2
Number of trucks = 36"
9)
    
"10"
Returns: "seed = 10
W = 87 H = 33
Capacity = 1
Number of trucks = 16"

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.

ID: 13923