Problem Setting

Overview

• Concept: Similar to the first contest, the contestant will run a delivery service. Customers will place orders with the contestant shop. Each order has a unique \text{ID} and should be delivered to the corresponding customer. The contestant's delivery service has one car. The car will fetch the ordered item from the shop and deliver it to the customer.
• Score: The goal is to deliver as many items as possible, as quickly as possible in a given amount of time T_{\text{max}}. (Orders are expected until 0.95 \times T_{\text{max}}).
• Constraint: In this contest there is no constraint on the number of items which can be placed into the car. However, an item can only be loaded in the car, by fetching it from the shop, after the order has been placed.
• Problem C: In this problem orders appear online, that is new orders appear, while the contestant moves the car to make as many deliveries as possible as fast as possible. In addition the planning algorithm of the service will have to master several environmental uncertainties which constitute the main difference from our previous contest.
• New: Environmental Uncertainties:
  • Traffic jam may appear along speedways.
  • Car breakdown: The delivery car may break.
  • Order cancellation: Customers may cancel orders after a certain time.
  • Traffic lights may hinder cars from entering and crossing of speedways.

Specification of Time and Space:

• Time: In this contest we model the progress of time by integer values 0 \le t < T_{\text{max}}.
• Map: In this contest we model a map by a simple, undirected, and connected graph G=(V, E), consisting of a set of vertices V and a set of edges E
• Shop and customer locations: The vertices u \in V are labeled from 1 to |V| and the vertex u=1 denotes the location of your shop, while vertices u = 2,...,|V| denote locations of potential customers. Here, |V| denotes the number of elements of the set V.
• Streets: Each edge \left\{ u, v \right\} \in E represents a street connecting the vertices u, v \in V. The corresponding length is given by an integer edge weight d_{u, v} \ge 1.
• New: Graph creation: The algorithm for generating the map graph based on a random seed is specified in the following pseudo-code. For further details, please see the sample code below. Note: The graph generation algorithm is different from the previous contest.

Extra Information and pseudo code: Map graph properties and map graph generator

The map graph generator used in this contest produces map graphs with the following properties:

• The graph has a pronounced two-dimensional structure of 25\times25 vertices.
• New: Each graph has two speedway paths connecting one of the North ends to one of the South ends as well as one of the East ends to one of the West ends. Moving along the speedways is about 4 times faster than moving on other roads.
• New: In addition there is a new bottleneck line from the North end to the South end of the map graph.
• New: Speedways and the bottleneck line divide the graph into 6 sparsely connected regions.
• Typical vertices have relative order frequency 1, while those in a certain centralized region has order frequency 2. Orders do neither appear on speedways nor on the shop vertex. Both of which have order frequency 0.

A typical map graph (left) in an early construction stage and (right) in its final shape. (Left) : A vertex grid (dots) with North-South and East-West speedways (black dots and lines) and a (dashed) bottleneck line divides the rest of the vertices into 6 disjoint vertex sets (green shaded background). Speedways are connected to neighboring regions every 5 steps from the intersection point. Regions to the East and West of the bottleneck line are also connected every five steps from the intersection between the bottleneck line and the East-West speedway. (Right) : The final map graph with 2 speedways (thick gray line) and final vertex positions. Pink vertices which are not on speedways have relative order frequency 1. Green vertices in a center region have order frequency 2.

Pseudo-code of map graph generator:

• Input:|V|, |E|, \mathrm{MaxDegree}=5
• 2d vertex grid:
  • Set R \leftarrow \lfloor \sqrt{|V|} \rfloor. (In what follows we assume the case |V| = R \times R. For the treatment of a potential remainder term, please consult the code in the toolkit.)
  • Plot points (x, y) on the 2d vertex grid (0 \leq x, y \lt R) as follows. \forall u\in{1,...,|V|}
    • x \leftarrow (u-1) \mod R
    • y \leftarrow \frac{u-1-x}{R}
  • Finally, we randomly shuffle the vertex labels u. The shop is the vertex u=1.
• Speedways and bottleneck lines
  • A North-South speedway vertex path is allocated. To this end we pick one x\in[R/2, 2R/3] and allocate all vertices with the corresponding x to the path. Neighboring speedway vertices are connected with d_{u,v}\leftarrow 1. (See figure.)
  • Similarly, an East-West speedway vertex path is allocated. To this end we pick one y\in[R/3, 2R/3] and allocate all vertices with the corresponding y to the path. Neighboring speedway vertices are connected with d_{u,v}=1. (See figure.)
  • Four speedway directions are assigned to the North, South, East, and West direction of the speedway respectively.
  • Finally, a bottleneck line is allocated at x=\xi+0.5, where \xi\in[R/6,R/3] (uniform random). (See figure.)
  • The speedways and the bottleneck line divide the remaining vertices of the vertex grid into 6 regions. (See figure.)
  • Regions neighboring the speedway are connected to the speedways every five speedway vertices (counted from the speedway intersection).
  • Similarly, regions to the East and the West of the Bottleneck line are connected every five vertex pairs (counted from the intersection of the East-West speedway with the bottleneck line).
• Final vertex positions:
  • After creating the speedways, speedway entrances, and the connections across the bottleneck line, vertices are shifted to their final vertex position by adding a uniform random offset dx, dy \in [0, 1] , giving the final vertex position (x + dx, y + dy)\in [0,R] \times [0,R].
• How we create a connected road networks within the 6 subregions:
  • To generate a connected road network within the six subregions, we create a complete graph G_{\text{comp}} on the vertex set u \in V, assigning each vertex pair u, v \in V \times V an edge weight W_{u, v} as follows:
    • W_{u, v}\leftarrow 1 for speedway edges
    • W_{u, v}\leftarrow \mathrm{EuclideanDistance} of vertex positions for all vertex pairs u,v with both u and v within the same region.
    • previously assigned edges for crossing the bottleneck line and entering the speedway are also assigned the Euclidean distance of the corresponding vertex positions.
    • Finally, W_{u, v}\leftarrow \infty, for all remaining vertex pairs with vertices in mutually distinct regions.
  • Next, we construct a minimum spanning tree of G_{\text{comp}}, by extending the edges which have already been assigned previously (speedways, speedway entrance, and connections across bottle neck line) to a full tree. The |V|-1 edges of the minimum spanning tree give a connected graph. An edge weight d_{u,v} \leftarrow \lceil 4 \times W_{u, v} \rceil is assigned to the newly added edges as well as the bottleneck line connections and the speedway entrances.
• How we add side roads:
  • To create a network of side roads, we successively add |E|-(|V|-1) edges to the graph G as follows:
    • Update \mathrm{cost}(u,v).
    • Among the vertex pairs \left( u, v \right) \in V\times V, not yet connected by an edge, select a pair with minimal \mathrm{cost}(u,v).
    • Assign the edge weight d_{u,v} \leftarrow \lceil 4 \times W_{u, v} \rceil .
  • Here, \mathrm{cost}(u,v) is essentially based on the Euclidean distance of vertices, giving preference to connecting nearby vertices with low degree. In addition, preference is given to side roads along the rectangular grid, to avoid too many bridges. The detailed definitions are as follows:
    • Define \mathrm{degree}(u), the degree of vertex u\in V as the number of incident edges.
    • Define \mathrm{color}(u) for each vertex u\in V according to its original position (x,y) on the vertex grid as:
      • If x+y is even : \mathrm{color}(u) = 0
      • If x+y is odd : \mathrm{color}(u) = 1
    • Define a factor f(u,v) as follows:
      • If \mathrm{color}(u) and \mathrm{color}(v) are the same : Set \mathrm{f}(u,v) = 5
      • If \mathrm{color}(u) and \mathrm{color}(v) are different : Set \mathrm{f}(u,v) = 1
    • Define a factor g(u) as follows:
      • If \mathrm{degree}(u) \lt \mathrm{MaxDegree} : Set g(u)=1
      • If \mathrm{degree}(u) \geq \mathrm{MaxDegree} : Set g(u)=\infty
    • Finally, the cost is defined as follows:
      • \mathrm{cost}(u,v) = W_{u,v}\times \mathrm{degree}(u) \times \mathrm{degree}(v) \times f(u,v) \times g(u) \times g(v).
• How we assign order frequencies:
  • Assign each vertex u \in V an order frequency f_u \in \left\{0,1,2\right\}.
  • Init the order frequency of the shop vertex: f_1 \leftarrow 0.
  • Init the order frequency of the other vertices: f_u \leftarrow 1
  • Now determine vertices with order frequency 2. For this draw a uniform random center point c=(c_x,c_y)\in [R/4,3R/4]\times[R/4,3R/4] and then for all vertices u=2,...,|V| do:
    • If \mathrm{EuclideanDistance}(c,u)\le R/8 + \mathrm{uniformRandom}[0,R/8]: f_{u} \leftarrow 2
  • Finally, for all vertices u along a speedway, the order frequency is set as: f_u \leftarrow 0.

Specification of Car Locations and Moves:

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:

  • on a vertex u \in V.
  • on an edge \left\{ u, v \right\} \in E. More specifically, it is located at a distance x (0 \lt x \lt d_{u, v}) from u to v .

• 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. 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 (an incorrect answer).

  • w must be a vertex, i.e., w \in V.
  • If the car is on vertex u \in V, there must be an edge connecting u and v, i.e., \left\{ u, w \right\} \in E.
  • If the car is on the edge \left\{ u, v \right\} \in E, w must either be w = u or w = v.

• New: A contestant's move may be rejected, if a contestant moves along a speedway direction which is blocked by a traffic jam.

• New: A contestant's may be required to wait at a traffic light, after entering the speedway.

Orders, Deliveries, and Constraints:

• Orders: Throughout the contest each order is characterized by three quantities: A unique order ID, a vertex v \in V indicating the order destination, and the order time t at which the order appears. For the detailed format see below.
• Order generation: At each time 0 \le t \le T_{\text{last}} = 0.95 \times T_{\text{max}} at most one new order can appear with probability p_{\text{order}}(t). In case there is an order, the order destination i is chosen from the vertex set V with probability proportional to the order frequency f_i. For details, see the pseudo-code below or the sample code further below.

Pseudo code: Order generation

• Input: Last order time T_{\text{last}} and average order probability p_{\text{order}}(t).
• Init: \mathrm{ID} \leftarrow 0.
• For each step t = 0, ..., T_{\text{last}} do:
  • Generate a uniform random number r \in [0,1] .
  • If r \le p_{\text{order}}(t) :
    • Select a vertex position u \in V at random with probability proportional to the order frequency f_{u} of the vertex.
    • \mathrm{ID} \leftarrow \mathrm{ID} + 1
    • place order (new order ID, order time t, vertex position u \in V )
  • Else: place no order

• Note: The average order probability is defined as follows:
• p_{\text{order}}(t) = \begin{cases} t / T_{\text{peak}}, & \text{if } 0\le t \lt T_{\text{peak}}, \\ (T_{\text{last}} - t) / (T_{\text{last}}- T_{\text{peak}}), & \text{if } T_{\text{peak}} \le t \lt T_{\text{last}}, \\ 0, & \text{if } T_{\text{last}} \le t, \end{cases}
• where T_{\text{last}}:=0.95 \times T_{\max} and T_{\text{peak}} is drawn randomly uniform from the interval [0, T_{\text{last}}].
• Note: The value of T_{\text{peak}} will not be given as an input.

• Delivery: To deliver an order, the contestant must do the following steps after the order has been placed:
  • (1st) Move the car onto the shop: Note: When moving a car onto the shop, all orders with order time less than or equal to the current time, will be transfered into the car. On the other hand, orders which have not appeared yet, cannot be placed into the car.
  • (2nd) Move the car to the customer position: To finalize a delivery, move the car onto the vertex of the customer position. Note: Orders which have not been transfered into the car yet or orders which are cancelled already, will not be delivered, even if you arrive at the customer position.

• Constraints: Throughout the contest, we assume each order has a unique \text{ID} and should be delivered to the corresponding customer. It is further assumed that an unlimited number of orders can be placed in the car.

• New: Orders may be canceled by impatient costumers. For details see the event section below.

New: Environmental Uncertainties

The delivery planning has to master several environmental uncertainties

• Traffic jam may appear along speedways. If a new traffic jam appears, it entirely blocks one of the four possible speedway directions. Note that, a car traveling along a speedway direction blocked by a traffic jam, can only move forward in 10\% of the cases. In 90\% of the cases, it will be forced to stay on its current position. For details please see the pseudo-code or the code in the distributed toolkit.

  Pseudo code: Traffic jam

  
  

  • Given: p_{\text{duration}}(t) // Distribution of traffic jam durations.
  • Given: p_{\text{delay}}(t) // Delay time distribution, describing delay of traffic jam outbreak after peak point.
  • Input: p_{\text{jam}}=0.25 // Probability for a single traffic jam to break out.
  • Input: p_{\text{move}}=0.1 // Probability to accept a car move along a jammed direction of a speedway.

  
  

  // Handling traffic jam upon initialization

  • For each of the four speedway directions d=1,2,3,4 we sample four points in time t_{d,i} with i=1,2,3,4 from a uniform random distribution and order them in time.
    • t_{d,i} \sim \mathrm{uniformRandom}[0,T_{\max})
    • \forall d : t_{d,1} \le t_{d,2} \le t_{d,3} \le t_{d,4}
  • Each t_{d,i} defines a point in time after which a traffic jam can appear with probability p_{\text{jam}}. If the traffic jam breaks out it is delayed for some time described by p_{\text{delay}}(t) and has a duration described by p_{\text{duration}}(t) as follows:
  • For all pairs (d,i) with d = 1,...,4 and all i = 1, ..., 4 do:
    • if \mathrm{uniformRandom}[0,1] \le p_{\text{jam}}: // traffic jam appears
      • Sample delay: \delta_{d,i} \sim p_{\text{delay}}(t)
      • A traffic jam along direction d will start at: t_{\text{start}, d, i} \leftarrow t_{d,i} + \delta_{d,i}
      • Sample duration: \Delta_{\text{jam}, d, i} \sim p_{\text{duration}}(t)
      • The traffic jam along direction d will end at: t_{\text{end}, d, i} \leftarrow t_{\text{start}, d, i} + \Delta_{\text{jam}, d, i}
    • Else: // no traffic jam appears
  • For each direction the intervals [t_{\text{start}, d, i}, t_{\text{end}, d, i}] are collected in a list. Note: Overlapping intervals will be unified.
  • The contestant algorithm will receive all 16 t_{d,i} as an input. On the other hand, the traffic jam intervals [t_{\text{start}, d, i}, t_{\text{end}, d, i}] will not be provided upon initialization.

  
  

  // Handling traffic jam during the online delivery phase

  • For t=0,..., T_{\max}-1 do:
    // Notifying the contestant of traffic jam
    • For d=1,2,3,4 do:
      • If t is in one of the traffic jam intervals t\in [t_{\text{start}, d, i}, t_{\text{end}, d, i}]:
        • Send \mathrm{jam}_d=1 to contestant
      • Else:
        • Send \mathrm{jam}_d=0 to contestant
    // Processing contestant move
    • Check validity of move as usual.
    • If (no traffic jam): Move car as instructed.
    • Else if (car on speedway) and (move in direction d) and (direction d has a traffic jam):
      • If \mathrm{randomUniform}[0,1] \le p_{\text{move}}:
        • accept move, update position, and output OK to notify contestant
      • Else:
        • reject move, stay at current position, and output JAM to notify contestant
  
  
  • The distribution of traffic jam durations is an exponential with mean \mu=1000. For further details, see comment on distributions below or check the toolkit.
  • The distribution of traffic jam delays is a power-law distribution characterized by \mathrm{median}=100 and its exponent characterized by \epsilon=3. For further details, see comment on distributions below or check the toolkit.

• Car breakdown: The delivery car may break down. Several steps before suffering a car break down, the contestant receives a WARNING t upon which the user is guaranteed t steps to return to the shop and repair the car. If the contestant fails to return to the shop within the given time, the contestant receives the BROKEN signal, upon which the car cannot move for 300 moves. For details please see the pseudo-code or the code in the distributed toolkit.

  Pseudo code: Car breakdown

  • Given: Distribution of car ok time p_{\text{car ok}}(t).
  • Given: The return time at first car breakdown warning T_{\text{warning}}.
  • Init: t_{\text{car}} \sim p_{\text{car ok}}(t) and \mathrm{carStatus} = 0 // car ok
  • For t=0,..., T_{\max}-1 do:
    // Switching of car status
    • if \mathrm{carStatus} == 0 and t_{\text{car}} == 0: // enter warning status
      • t_{\text{car}} \leftarrow T_{\text{warning}}
      • \mathrm{carStatus} \leftarrow 1 // warning status
    • if \mathrm{carStatus} == 1 and t_{\text{car}} == 0: // enter car broken status
      • t_{\text{car}} \leftarrow 300
      • \mathrm{carStatus} \leftarrow 2 // car broken
    • if (\mathrm{carStatus} == 1 and current position is shop vertex) or (\mathrm{carStatus} == 2 and t_{\text{car}} == 0:) // repair car
      • t_{\text{car}} \leftarrow p_{\text{car ok}}(t)
      • \mathrm{carStatus} \leftarrow 0 // car not broken
    // Sending of Signal status
    • if \mathrm{carStatus} == 0: Send NOT_BROKEN
    • if \mathrm{carStatus} == 1: Send WARNING t // t = t_{\text{car}}
    • if \mathrm{carStatus} == 2: Send BROKEN
    // Receiving contestant move
    • \mathrm{move} \leftarrow from contestant
    // Processing contestant move
    • if \mathrm{carStatus} \in \{0,1\} : standard procedure
    • if (\mathrm{carStatus} == 2 and \mathrm{move} is not -1:)
      • Send: NG // notifies contestant of invalid move
    // Decrement timer
    • t_{\text{car}} \leftarrow t_{\text{car}} - 1
    Note:
  • p_{\text{car ok}}(t) generates random variable whose inverse is sampled from a power-law distribution with \mathrm{median} = \frac{1}{T_{\max}} and exponent characterized by \epsilon = 2.5. For further details, see comment on distributions below or check the toolkit.
  • If \mathrm{carStatus} == 0 then t_{\text{car}} is unknown to the contestant.
  • If \mathrm{carStatus} == 2, i.e., the car is broken, the contestant code must send the input -1 (stay), otherwise the result will be WA (wrong answer).

• Order cancellation: Customers, who had to wait for their orders for more than T_{\text{wait}}=2000 steps, are allowed to cancel their orders. Order cancellation is handled probabilistically as described in the following pseudo-code. For further details please consult the distributed toolkit.

  Pseudo code: Order cancellation

  • Given: T_{\text{wait}}=2000 and a distribution of extra waiting time p_{\text{extra}}(t).
  • For t=0,..., T_{\max}-1 do:
    // When generating an order with \text{ID}:
    • Sample: t_{\text{extra}} \sim p_{\text{extra}}(t)
    • t_{\text{cancel}}(\text{ID}) \leftarrow t + T_{\text{wait}} + t_{\text{extra}}
    // When updating orders:
    • For each undelivered order \text{ID} do:
      • if t_{\text{cancel}}(\text{ID}) < t : send order cancellation signal
    
    
  • Note 1: t_{\text{extra}} and t_{\text{cancel}}(\text{ID}) are unknown to the contestant.
  • Note 2: p_{\text{extra}}(t) generates random variable whose inverse is sampled from a power-law distribution with \mathrm{median} = \frac{1}{T_{\max}} and exponent characterized by \epsilon=0.5. For further details, see comment on distributions below or check the toolkit.

• Traffic lights: When entering into a speedway a car may have to wait at the traffic light. In particular, access to vertices which constitute a speedway from vertices outside of a speedway is periodically granted, depending on the time t. Note that this will also affect cars which simply drive across a speedway. For details, refer to the following pseudo code or distributed toolkit.

  Pseudo code: Traffic light

  • Input: Signal period P_{\text{light}}
  • For t=0,..., T_{\max}-1 do:
    • If (car has moved onto a speedway vertex from non-speedway vertex) or (car received WAIT signal in previous step):
      • if (\lfloor t / P_{\text{light}} \rfloor \mod 2) == 0: // green traffic light
        • the contestant move receives an OK verdict
        • the car moves onto the speedway vertex
        • the next move can be decided in a standard manner
      • else: // red traffic light
        • x \leftarrow P_{\text{light}} - \left(t \mod P_{\text{light}}\right)
        • the contestant move receives a WAIT x verdict
        • the car moves onto the speedway vertex
        • the car is required to stay on the current speedway vertex for the next x steps
  • Note: Unlike other events, this event is deterministic.

• Definitions of the utilized probability distributions can be found in the following details section. For further details please see the code distributed with the toolkit.

  Definitions: Probability distributions

  • Throughout the contest we use three types of random variables: (i) Exponentially distributed random variables, (ii) power-law distributed random variables, and (iii) random variables which are the inverse of a power-law distributed variable. Power-law distributed variables have heavy tails and lead to many large outliers. Random variables whose inverse is drawn from a power-law have many small outliers.
  • All random variables are defined in the range t \in [0,\infty).
  • Exponential distribution:
    • Parameter: \mu (mean)
    • Probability density: p(t) = \frac{1}{\mu}\exp{\left(-\frac{t}{\mu}\right)}
    • Tail probability: P(t \ge s) := \int_{s}^{\infty} p(t) \text{d}t = \exp{\left(-\frac{s}{\mu}\right)}
    • The traffic jam duration is sampled from this type of distribution.
  • Power-law distribution
    • Parameters: \epsilon (characterizes the exponent) and the \mathrm{median}
    • Derived scaling parameter: \mu = \frac{\mathrm{median}}{2^{\frac{1}{\epsilon}} - 1}
    • Probability density: p(t)= \frac{\epsilon}{\mu}\left(1+\frac{t}{\mu}\right)^{-(1+\epsilon)}
    • Tail probability: P(t \ge s) := \int_{s}^{\infty} p(t) \text{d}t = \left(1+\frac{s}{\mu}\right)^{-\epsilon}
    • The traffic jam outbreak delay times are sampled from this type of distribution.
  • Random variables with inverse distributed as power-law.
    • Parameters: \epsilon, \mathrm{median}
    • The variable x:=1/t is sampled from a power-law distribution p(x) with parameters \epsilon, \mathrm{median}
    • In the algorithm we sampling a variable x from the power-law distribution with \epsilon, \mathrm{median} and then take its inverse to get the desired variable as t \leftarrow 1/x.
    • The duration during which the car is not broken and extra waiting times for costumer cancellation are sampled from this type of distribution.

Scoring

• During the contest the total score of a submission is determined by summing the score of the submission with respect to 30 input cases.
• After the contest a system test will be performed. To this end, the contestant's last submission will be scored by summing the score of the submission on 100 previously unseen input cases.
• For each input case, the score is calculated as follows:

  \text{Score} = \sum_{i \in D} {(T_{\text{max}})}^{2} - {(\mathrm{waitingTime}_i)}^{2},

  Here we use the following definitions:
  • D : the set of orders delivered until t=T_{\text{max}}
  • the waiting time of the ith order: \mathrm{waitingTime}_i = \mathrm{deliveredTime}_i - \mathrm{orderedTime}_i.
  • Note that an input case giving the output WA will receive 0 points.

Particulars of Problem C:

Problem C is an interactive contest, in which 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. In addition, the planning algorithm of the service, will have to master changing circumstances such as traffic jam, car breakdown, order cancellation, and traffic lights.

The precise flow which details the interaction of the contestant and host code is shown below.

Note: The host code outputs the graph, the order frequencies and the traffic jam information 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.

Interactive Input/Output Format through the Standard IO

Initialization

At first, the host code will output a graph G and the order frequencies f_{i} for each vertex i, which are proportional to the probability of an order to appear at vertex i. In addition, the times t_{d,i}, \cdots, t_{d,i} for potential traffic jam outbreaks along direction d, the switching period of a traffic light P_{\text{light}} and the total number of steps T_{\max} is provided.

|V| |E|
u_1 v_1 d_{u_1, v_1} e_{u_1, v_1} e_{v_1, u_1}
u_2 v_2 d_{u_2, v_2} e_{u_2, v_2} e_{v_2, u_2}
\vdots
u_{|E|} v_{|E|} d_{u_{|E|}, v_{|E|}} e_{u_{|E|}, v_{|E|}} e_{v_{|E|}, u_{|E|}}
f_1 f_2 \ldots f_{|V|}
t_{1,1}, \cdots, t_{1,4}
\vdots
t_{4,1}, \cdots, t_{4,4}
P_{\text{light}}
T_{\text{warning}}
T_{\max}

• First line: |V| number of vertices, |E| number of edges
• The next |E| lines: The edges of the graph. In particular, the ith line denotes the vertices u_i and v_i which form an edge, along with the corresponding edge weight d_{u_i, v_i}. In addition, e_{u_i, v_i} and e_{u_i, v_i} denote the street type along edge direction u_i \to v_i) and v_i \to u_i, respectively. In particular:
  • e_{u_i, v_i} = 0 : The edge direction u_i \to v_i connects two standard roads.
  • e_{u_i, v_i} = d \in {1,2,3,4} : The edge direction u_i \to v_i is along the speedway of direction d.
  • e_{u_i, v_i} = 5 : The edge direction u_i \to v_i has its endpoint vertex v_i on a speedway.
  • e_{u_i, v_i} = 6 : The edge direction u_i \to v_i has its start vertex u_i on a speedway.
• The next line: The order frequencies f_i which determine the probability of an order at vertex i as p_{i}=\frac{f_{i}}{\sum_{i}f_{i}}.
• The next four lines: Each line t_{d,1}, \cdots, t_{d,4} (d=1,\cdots,4) denotes four points in time after which a new traffic jam may outbreak along direction d.
• The next line: Denotes the light period P_{\text{light}}.
• The next line: Denotes the period T_{\text{warning}}, after which a car breaks, if the contestant does not return to the shop.
• The last line: The total number of car position updates T_{\max}.

Interactive Loop

At time t we first obtain the following information through the standard input.

\mathrm{CAR\_STATUS}
\mathrm{jam}_{1} \mathrm{jam}_{2} \mathrm{jam}_{3} \mathrm{jam}_{4}
N_{\text{cancel}}
\mathrm{cancel\_id}_1
\mathrm{cancel\_id}_2
\vdots
\mathrm{cancel\_id}_{N_{\text{cancel}}}
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
\vdots
\mathrm{put\_id}_{N_{\text{put}}}

• The first line represents the \mathrm{CAR\_STATUS} which can take one of the following values:
  • NOT_BROKEN : Denotes that the car is in good shape.
  • WARNING t : Denotes that the car will break in t steps, if not returning to the shop.
  • BROKEN : Denotes that the car is currently broken and cannot move in this step. In this case, the contestant should output stay, i.e. -1 or otherwise the answer will become NG.
• The second line broadcasts traffic conditions along the speedway directions d=1,2,3,4. In particular, if \mathrm{jam}_d is 0, direction d has no traffic jam. On the other hand, if \mathrm{jam}_d is 1, direction d is jammed.
• The next line : N_{\text{cancel}} represents the number of orders which have been canceled at time t.
• The subsequent N_{\text{cancel}} lines indicate canceled orders. In particular, the ith line indicates that the order with ID \mathrm{cancel\_{id}}_i has been canceled.
• The next line : N_{\text{new}} represents the number of new orders which appeared at time t.
• The next N_{\text{new}} lines give the newly generated order information. The ith order information indicates that the order ID \mathrm{new\_{id}}_i of the new order, while \mathrm{dst}_i denotes the vertex to which the customer wishes the order to be delivered.
• The next line : N_{\text{put}} represents the number of items transfered into the car at time t.
  • If the car is not at the vertex of the store N_{\text{put}} will be zero.
• The subsequent N_{\text{put}} lines indicate the order information for the newly loaded items. In particular, the ith line indicates that the order ID corresponding to the product loaded in the car is \mathrm{put\_{id}}_i.

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

• If you want the car to stay at its current position, send -1 to the standard output
• If you want the car to move one step towards a neighboring vertex move w, send w to the standard output

Note: 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).

• w is a vertex index with w \in \left\{1, ... , |V|\right\}
• If the car is on a vertex u, the edge \left\{ u, w \right\} \in E must exist
• If the car is on an edge \left\{ u, v \right\}, w must either be w = u or w = v

Moreover, if the \mathrm{CAR\_STATUS} is BROKEN, the contestant is required to send -1 to the standard output. A failure to do so, will result in the the host code judging the move as NG, ultimately leading to WA, i.e., a wrong answer as described further below.

After the contestant 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}}}

• \mathrm{verdict} is a string indicating whether your action at time t was valid. It can be one of the two following options.
  • OK: Indicating that the requested move was feasible and the car has been moved accordingly.
  • NG: 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.
  • JAM : Appears, if the requested move along a jammed direction was rejected. (Note: Moves along a jammed direction which have been accepted, will receive an OK, indicating that the move was executed as requested.)
  • WAIT t : Indicates that the requested move was feasible and the car has been moved accordingly. However, since the car has been moved onto a speedway vertex from outside a speedway, the contestant is now requested to wait at the traffic light for t steps, i.e., the contestant code must output -1 for the next t steps. A failure to do so will result in the verdict NG. Further note, when entering a speedway vertex during a green traffic signal, the host code will send the verdict OK.
• N_{\text{achieve}} represents the number of orders that have been delivered at time t.
  • If the car is not at a delivery vertex, no orders have been delivered and N_{\text{achieve}}=0.
• The subsequent N_{\text{achieve}} lines indicate the delivered orders. In particular, the ith line indicates the order ID \mathrm{achieve\_{id}}_i.

Finally, after receiving the standard input of the host code after the last step T_{\max} you must terminate the program immediately.

I/O Constraints

• All numbers given through the standard input are integers.
• All outputs must be integers

Initialization

• T_{\text{max}} = 10000
• |V| = 625
• 1.5 |V| \leq |E| \leq 2|V|
• 1 \leq u_{i}, v_{i} \leq |V| (1 \leq i \leq |E|)
• 1 \leq d_{u_i, v_i} \leq \lceil 4\sqrt{2|V|} \rceil (1 \leq i \leq |E|)
• 0 \leq e_{u_i, v_i}, e_{v_i, u_i} \leq 6 (1 \leq i \leq |E|)
• The given graph has no self-loops, no multiple edges and is guaranteed to be connected.
• f_1 = 0
• f_i \in \left\{0, 1, 2 \right\} (2 \leq i \leq |V|)
• 0 \leq t_{d,1} \leq t_{d,2} \leq t_{d,3} \leq t_{d,4} \lt T_{\text{max}} (1 \leq d \leq 4)
• 50 \leq T_{\text{warning}} \leq 120
• 10 \leq P_{\text{light}} \leq 30

Interactive Loop

• \mathrm{CAR\_STATUS} \in \{ NOT_BROKEN, WARNING t, BROKEN\}
• \mathrm{jam}_{1}, \mathrm{jam}_{2}, \mathrm{jam}_{3}, \mathrm{jam}_{4} \in \{0,1\}
• 0 \leq N_{\text{new}} \leq 1
• 1 \leq \mathrm{new\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{new}}). Note: If all orders are generated by the order generation rule as explained above, the total number of orders is at most T_{\text{last}}+1. Therefore, the possible range of \mathrm{new\_id}_{i} should be from 1 to T_{\text{last}}+1.
• The order IDs \mathrm{new\_{id}}_i are unique.
• 2 \leq \mathrm{dst}_i \leq |V| (1 \leq i \leq N_{\text{new}})
• 0 \leq N_{\text{cancel}} \leq T_{\text{last}}+1
• 1 \leq \mathrm{cancel\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{cancel}}).
• 0 \leq N_{\text{put}} \leq T_{\text{last}}+1
• 1 \leq \mathrm{put\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{put}}).

• The integer which the contestant outputs to the standard output at time t must either be -1 or 1 \leq w \leq |V|

• \mathrm{verdict} \in \{OK, NG,JAM, WAIT t\}
• 0 \leq N_{\text{achieve}} \leq T_{\text{last}}+1
• 1 \leq \mathrm{achieve\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{achieve}}).

Input/Output Example

In this IO example, we will use the situation visualized below. In particular:

• Graph : The example shows a graph with 16 vertices and 18 edges.
• Speedways are marked in black and have the following directions.
  • d=1 : 3\to7\to11\to15
  • d=2 : 15\to11\to7\to3
  • d=3 : 9\to10\to11\to12
  • d=4 : 12\to11\to10\to9.
• From step 0 to 8 : The car will deliver an order with ID 1 to vertex 14, while the order at vertex 16 will expire. The delivery route is marked by red arrows. A traffic jam is experienced at steps 4\to5.
• From step 8 to 14 : A car breakdown warning WARNING 5 will appear and the car tries to return to the shop vertex 1 for repair. However, the traffic light at vertex 9 will output a red signal WAIT 2 requiring the car to wait two steps 11, 12.
• In step 13 the car arrives in between the vertex pair 1, 9 and breaks, receiving a BROKEN.
• Step 14 : An infeasible move towards the shop during car BROKEN leads to the output NG.

Note: This example has been shrunk for pedagogical reasons and does not fulfill the constraints listed above.

16 18
5 1 2 0 0
2 3 2 5 6
2 6 4 0 0
3 4 2 6 5
3 7 1 1 2
4 8 4 0 0
1 6 2 0 0
1 9 2 5 6
7 11 1 1 2
9 10 1 3 4
9 13 2 6 5
9 14 2 6 5
10 11 1 3 4
11 12 1 3 4
11 15 1 1 2
12 16 2 6 5
14 15 2 5 6
15 16 2 6 5
0 1 0 1 1 2 0 1 0 0 0 0 1 1 0 1
3 167 311 913
63 617 791 837
325 473 893 915
156 387 627 849
6
5
10000

NOT_BROKEN
0 0 0 0
0
1
1 14
1
1

9

OK
0

NOT_BROKEN
0 0 0 0
0
1
2 16
0

9

OK
0

NOT_BROKEN
0 0 0 0
0
0
0

10

OK
0

NOT_BROKEN
0 0 0 0
0
0
0

11

OK
0

NOT_BROKEN
1 0 0 0
0
0
0

15

JAM
0

NOT_BROKEN
1 0 0 0
0
0
0

15

OK
0

NOT_BROKEN
1 0 0 0
0
0
0

14

OK
0

NOT_BROKEN
0 0 0 0
1
2
0
0

14

OK
1
1

WARNING 5
0 0 0 0
0
0
0

9

OK
0

WARNING 4
0 0 0 0
0
0
0

9

WAIT 2
0

WARNING 3
0 0 0 0
0
0
0

-1

WAIT 1
0

WARNING 2
0 0 0 0
0
0
0

-1

OK
0

WARNING 1
0 0 0 0
0
0
0

1

OK
0

BROKEN
0 0 0 0
0
0
0

1

NG

Using the Standard Output

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.

C++

std::cout << "-1" << std::endl;

Java

System.out.println("-1");

Python 3.4

print("-1", flush=True)

Sample Code C

A software toolkit for generation of input samples, scoring and testing on a local contestant environment is provided through the following link. In addition we provide software for visualizing the contestants results.