Problem Statement |
| | You will be given a graph with nodes and edges. One node will be designated as a sink node. Each of the other nodes will have some number of pebbles on it. Your goal is to move all the pebbles to the sink node.
You will do this by repeatedly picking up all the pebbles on one node and finding a simple path leading away from that node (a simple path is one that follows edges and does not repeat any nodes). The length of the path should be equal to the number of pebbles in the node you selected. For instance, if you pick node A with 2 pebbles, you could select the path A->B->C. Once you have picked a path, you remove all the pebbles from the first node of the path, and add one pebble on each of the others. In the example above, you would place pebbles on nodes B and C.
The graph will be specified by N, the number of nodes in the graph, and by int[]'s u and v, where (u[i],v[i]) is an undirected edge in the graph. pebbles will give you the initial number of pebbles at each node, where pebbles[i] tells how many pebbles start at node i. The sink will always be node 0. You should return a String[] where each element specifies one move as a sequence of space-delimited integers. The first integer should specify the node to pick up pebbles from, followed by one node ID per pebble designating the path. For instance, "A B C" for the above example (substituting IDs for A, B, and C).
The graph will be generated by first selecting N uniformly in [10,1000]. N points will then be placed in the unit box from (0,0) to (1,1). The points will then be sorted by distance from the origin, so that node 0 is closest to the origin, while node N-1 is furthest. A constant C will be chosen uniformly in [0,0.2). For each pair of nodes u and v, an edge will then be formed between u and v if their distance is less than C. Each node other than the sink will start with between 1 and 10 pebbles, inclusive. If the graph ends up being disconnected, the generation is restarted from scratch.
Your score will start at 1. For each move that does not end at the sink (node 0), your score will be incremented (you want to end with a low score). At the end of all your moves, you must have moved all the pebbles to the sink. The overall scoring will be relative, so you will get BEST/YOU points for each test case, where BEST is the best score on that test case, and YOU is your score on that test case. |
| |
Definition |
| | | Class: | GraphMancala | | Method: | move | | Parameters: | int, int[], int[], int[] | | Returns: | String[] | | Method signature: | String[] move(int N, int[] u, int[] v, int[] pebbles) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The memory limit is 1024MB and the time limit is 10 seconds. |
| - | Note that if you end up with too many pebbles at one node, you might not be able to make a move. |
| - | You may not remove pebbles from the sink. |
| - | A simple path may not be a circuit. |
| - | Your return may not contain more than 100,000 elements. |
| |
Examples |
| 0) | |
| | | Returns: "" | | The text file contains the four parameters, one per line: Download |
|
|
| 1) | |
| | |
| 2) | |
| | |
| 3) | |
| | |
| 4) | |
| | |
| 5) | |
| | |
| 6) | |
| | |
| 7) | |
| | |
| 8) | |
| | |
| 9) | |
| | |
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.