In order to make deliveries you will operate a delivery car, which can take positions and make moves as specified below.
Car position: A car can generally take two types of position:
Car move: At each step 0 \le t < T_{\text{max}} you have to choose one of the following actions in order to control your delivery car.
stay
: stay at the current position.move w
: Take one step towards vertex w \in V.In case of choosing move w
, w must obey the following constraints. A failure to obey these constraints results in a wrong answer WA
.
\text{Score} = \sum_{i \in D} {(T_{\text{max}})}^{2} - {(\mathrm{waitingTime}_i)}^{2},
Here we use the following definitions:WA
will receive 0 points.Problem B is an interactive contest, where the contestant code successively receives updates on newly generated and delivered orders from a host code, while simultaneously servicing the customer by moving the car to a neighboring position in every step t=0,...,T_{\max}-1. The precise flow which details the interaction of the contestant and host code is shown below.
Contestant Code | Host Code | |
---|---|---|
Generate and output graph G | ||
+ | Time t: Generate and output new orders | |
+ | Time t: If on shop, output orders loaded into car | |
+ | Time t: Determine and output a move | |
+ | Check feasibility of move; If move unfeasible: output NG , If feasible: output OK |
|
+ | Time t+1: update and output information on delivered items (if any) |
Note: The host code outputs the graph only once. The processes marked by a "+" on the left side of the table are repeated iteratively for integers t in t = 0,..., T_{\max} - 1.
At first, the host code will output a graph G, the order frequencies f_{i} for each vertex i, which are proportional to the probability of an order to appear at vertex i, and the total number of steps T_{\max}.
|V| |E| u_1 v_1 d_{u_1, v_1} u_2 v_2 d_{u_2, v_2} \vdots u_{|E|} v_{|E|} d_{u_{|E|}, v_{|E|}} f_1 f_2 \ldots f_{|V|} T_{\max}
At time t we first obtain the following information through the standard input.
N_{\text{new}} \mathrm{new\_id}_1 \mathrm{dst}_1 \mathrm{new\_id}_2 \mathrm{dst}_2 \vdots \mathrm{new\_id}_{N_{\text{new}}} \mathrm{dst}_{N_{\text{new}}} N_{\text{put}} \mathrm{put\_id}_1 \mathrm{put\_id}_2 \mathrm{put\_id}_{N_{\text{put}}}
Next, in order to move the delivery car to a neighboring position the contestant code must at every time t (0 \leq t \lt T_{\max}) output the following \mathrm{command} to the standard output.
\mathrm{command}
Here, \mathrm{command} must be of the following form
stay
at its current position, send -1
to the standard outputmove w
, send w
to the standard outputNote: In case you choose move w
, w must meet all of the following conditions. If any of the following conditions is violated, the host code will output NG
and the contestant should terminate the program, ultimately leading to WA
(incorrect).
After your action at time t is send to the standard output, the host code will send the following information about time t + 1 to the standard input.
\mathrm{verdict} N_{\text{achieve}} \mathrm{achieve\_id}_1 \mathrm{achieve\_id}_2 \vdots \mathrm{achieve\_id}_{N_{\text{achieve}}}
OK
: Indicating that your action was feasibleNG
: Indicates that your action is infeasible. If you receive this input, you must terminate the program immediately. It is guaranteed to be WA (incorrect), if it is terminated immediately.If you do not terminate immediately the behavior is undefined.Finally, after receiving the standard input of the host code after the last step T_{\max} you must terminate the program immediately.
Time | Contestant | Host Code | Explanation |
---|---|---|---|
5 7 1 2 5 5 3 4 2 4 8 1 5 1 2 3 3 4 5 3 4 3 9 0 1 1 5 5 500 |
At first, the host code provides the graph data through the standard input. In this example, the graph has |V| = 5 vertices and | E | = 7 edges. Next, the order frequency for each vertex is given in one line. Finally, T_{\max} is given. | ||
0 \rightarrow 1 |
1 1 5 1 1 |
At time t=0 we get one order. This order has ID= 1 and should be delivered to vertex 5. Because your car is currently at vertex one, the order will be automatically transfered into your car. In this way, when your car is at the shop, all orders which have been made at present and before, will automatically be loaded into your car. | |
2 |
You decided to move one step towards vertex. | ||
OK 0 |
The first line indicates that your move was feasible. The second line shows that no orders have been delivered. | ||
1 \rightarrow 2 |
1 2 2 0 |
One new order (ID =2, delivery vertex =2) has occured. Your car is on the edge between vertex 1 and 2, so zero orders have been transfered to your car. | |
-1 |
You decided to keep your car in the same position. | ||
OK 0 |
Your move was valid. No orders will be delivered, because you are not at a delivery item position. | ||
2 \rightarrow 3 |
1 3 4 0 |
A new order (ID =3, delivery vertex =4) has appeared. | |
1 |
You decided to move back one step towards vertex 1. In this way you are allowed to perform a U-turn. | ||
OK 0 |
No orders have been delivered. | ||
3 \rightarrow 4 |
0 2 2 3 |
Since the car has returned to the store, products corresponding to order ID 2 and 3 are loaded onto the car. | |
5 |
The contestant has decided to move one step towards vertex 5. | ||
OK 1 1 |
Since you arrived at vertex 5, the order with ID 1 was delivered. | ||
4 \rightarrow 5 |
0 0 |
There is no new order. | |
5 |
The contestant decides to move one step towards vertex 5. | ||
NG |
The input was invalid and you should terminate your program. |
When returning your move instruction to the standard output, please use the flush command. As an example, consider the case where you want to output -1
. This is how to do it in some of the major programming languages.
std::cout << "-1" << std::endl;
System.out.println("-1");
print("-1", flush=True)
A software toolkit for generation of input samples, scoring and testing on a local contestant environment, and sample codes for beginners is provided through the following link. In addition we provide software for visualizing the contestants results.