Table of contents

Problem Summary
Time Schedules and Spatial Structures
Constitution of a Nanogrid
Energy Balance
EV Operation
Charge/Discharge to the Battery of a Nanogrid
Scoring
Problem A
Input and Output Format 1
Input and Output Format 2
Input and Output Format 3
Constraints for Input and Output
Example of Inputs and Outputs
Sample Code A

Problem Summary

In this problem, you operate multiple electric vehicles (EVs) to protect distributed nanogrids from overloading the electrical supply to EVs and to provide additional power from EVs if there is a power shortage in the nanogrids. Since EVs consume electricity proportional to their distances traveled, they need to charge from nanogrids if necessary. Each nanogrid is equipped with a battery, a photovoltaic (PV) power system and a fuel engine. Power generation, consumption and charge/discharge to EVs occur in each nanogrid and their time-varying imbalance is compensated by charge/discharge from the battery and electrical supply from outside.

The toolkit, which can be downloaded from the bottom of this page, contains a sample of contestant code in which input/output such as reading data from the judge code has already been implemented. Also, regarding the operation of EV, "all stay" and "random walk" have been implemented as examples. When implementing a new algorithm, the sample is designed so that you can focus on describing the operation of EV by inheriting the strategy class. (See README.md for details.) You can use the sample when submitting your code.

Time Schedules and Spatial Structures

• Time Schedules: The total time length of each test case corresponds physically to one business day. The time variable t is supposed to be integer valued ranging from 0 to T_{max}. For each test case, one of the four different one day weather patterns is randomly assigned and the weather pattern affects the resulting time series of difference between generated and consumed powers (energy balance). In the beginning of each test case, each contestant gets a whole time series of predicted energy balance and, for each time t, each contestant gets the charged capacity of the battery for each nanogrid, the set of orders assigned so far, and the following values in the previous step: actual energy balance, excess amount of power discarded, and power supplied from the outside. Based on the information, each contestant is asked to decide how to operate multiple EVs in the next step for each time t.
• Spatial Structures: Let G = (V, E) be a simple and undirected graph with the vertex set V and the edge set E, which represents a road network on which EV movement and EV charge/discharge occur. Nanogrids are located on some of the vertices. An edge represents the road connecting its two endpoints and has a positive integer weight corresponding to the road distance. The graph is generated by the algorithm below.

Constitution of a Nanogrid

Each nanogrid consists of a battery, a photovoltaic (PV) power system, a fuel engine, charging/discharging stations for EVs and power consumers and has the following attributes.

• Vertex ID: ID of the vertex u on which the nanogrid is located where u \in V_{\mathrm{grid}} (V_{\mathrm{grid}}: the set of vertices on which nanogrids are located (See "Algorithm to generate the graph G".) )

• Charged Capacity: The charged capacity of the battery in the nanogrid. Its initial value is C_{\mathrm{init}}^{\mathrm{grid}} and its maximum value is C_{\mathrm{max}}^{\mathrm{grid}}, which are the same for all the nanogrids. For each time t, the charged capacity changes by the difference between generated and consumed powers (energy balance) and it also changes by the difference between discharged and charged electricity to EVs (For the detail, see Charge/Discharge to the Battery of a Nanogrid .). If the resulting charged capacity exceeds C_{\mathrm{max}}^{\mathrm{grid}} at the time t, the charged capacity is set to C_{\mathrm{max}}^{\mathrm{grid}} at the time t+1 and the excess amount is discarded. Instead, if the resulting capacity is negative at the time t, the shortage is supplied from outside and the charged capacity is set to 0 at the time t+1. If the latter is the case, the score is deducted in proportion to the amount of shortage (For the detail, see Scoring.)

• Energy Balance: Difference between generated and consumed powers except for those for charging/discharging EVs for each time t. Its predicted value for each time t is provided to contestants in the beginning of each test case. Its actual value is sums of the predicted value and random value caused by stochastic fluctuation of the environment and sudden weather changes like downpour and sudden clear sky (For the detail, see Energy Balance below.)

• Maximum charging/discharging speed: The maximum speed of charging/discharging to the battery V_{\max}^{\mathrm{grid}}, which is the same for all the nanogrids.

Energy Balance

Difference between generated and consumed powers except for those for charging/discharging EVs for each time t.

• Pattern of the time series of the energy balance: For each test case, one of the four different one day weather patterns, i.e., sunny with/without downpour and rainy with/without sudden clear sky is randomly assigned and is informed to each contestant in the beginning of the test case. For each nanogrid, one of the N_{\mathrm{pattern}} different expected demand patterns is randomly assigned and is informed to each contestant in the beginning of each test case. A whole time series of predicted energy balance is provided to each contestant in the beginning of each test case. The amount of generated powers from the PV power system depends on the weather pattern and thus the sums of the predicted values of energy balance in one business day is largest for the weather pattern, sunny without downpour, and is smallest for the weather pattern, rainy without sudden clear sky.

• The time series of the energy balance: The time series of the energy balance is sums of predicted one and stochastic fluctuation \delta and the variation due to downpour and sudden clear sky.

  • The total time interval 0 \leq t < T_{\max} is divided into N_{\mathrm{div}} subintervals of equal length and predicted value of the energy balance is constant for each subdivided interval.
  • For each time t, \delta is sampled from the normal distribution with the mean 0 and the variance \sigma^{2}_{\mathrm{ele}}. The variance is informed to each contestant in the beginning of each test case but the value \delta is not informed to each contestant in advance.
  • Downpour: If the weather pattern is 1 (sunny with downpour), downpour occurs with a probability p_{\mathrm{event}} for each of N_{\mathrm{div}} subintervals. The probability is constant and independent for each subinterval. If the downpour occurs, the energy balance is subtracted by \Delta_{\mathrm{event}} for 15 percent of the nanogrids randomly and independently chosen for each subinterval because generated power from a photovoltaic (PV) power system decreases.
  • Sudden clear sky: If the weather pattern is 3 (rainy with sudden clear sky), sudden clear sky occurs with the probability p_{\mathrm{event}} for each of the N_{\mathrm{div}} subintervals. If the sudden clear sky occurs, the energy balance is added by \Delta_{\mathrm{event}} for 15 percent of the nanogrids randomly and independently chosen for each subinterval because generated power from a photovoltaic (PV) power system increases.

In case of the weather patterns 1 and 3, the timing for downpour or sudden clear sky is not informed to each contestant in advance.

EV Operation

Each contestant is asked to operate multiple electric vehicles (EVs) to protect distributed nanogrids from overloading the electrical supply to EVs and to provide additional power from EVs if there is a power shortage in the nanogrids.

• Number of EVs: The number of EVs N^{\mathrm{EV}} is uniformly randomly selected from the interval [N_{\min}^{\mathrm{EV}}, N_{\max}^{\mathrm{EV}}] and is informed to each contestant in the beginning of each test case.

• Initial Position of EVs: In the beginning of each test case, N^{\mathrm{EV}} vertices are selected randomly and one EV is placed on each selected vertex.

• Attributes for EV: Each EV has the following attributes:

  • ID (0, 1,... , N^{\mathrm{EV}}-1)
  • Charged capacity: C^{\mathrm{EV}}_{t} non-negative integer valued, initialized to C^{\mathrm{EV}}_{t=0}, and has the upper limit C^{\mathrm{EV}}_{\max} common for all the EVs
  • Present location: either on a vertex or on an edge
  • Maximum charging/discharging speed: V_{\max}^{\mathrm{EV}}, which is common for all the EVs.

• Operation for EVs: For each time t, each contestant chooses one of the operations below for each EV:

  • stay: Let the EV stay in the same place. In this case, the EV does not consume electricity, i.e., C^{\mathrm{EV}}_{t+1}-C^{\mathrm{EV}}_{t}=0.

  • move w: Let the EV move forward to the vertex w \in V by the distance 1. The charged capacity of the EV in the next step decreases by \Delta^{\mathrm{EV}}_{\mathrm{move}} unless the resulting charged capacity is negative. If that is the case, the operation is rejected, the EV stays at the same position and its charged capacity does not change if the following conditions are satisfied.

    • Suppose the operation move w is selected. Then, each contestant gets WA (Wrong Answer) if one of the conditions below are violated.
      • w \in V
      • Supposing the present position of the EV is on u \in V, \left\{ u, w \right\} \in E holds.
      • Supposing the present position of the EV is on \left\{ u, v \right\}, w = u or w = v holds.

  • charge_from_grid \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}}: Charge the EV by \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}}. The charged capacity of the EV in the next step C^{\mathrm{EV}}_{t+1} becomes C^{\mathrm{EV}}_{t+1} \leftarrow C^{\mathrm{EV}}_{t} + \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge},t}. It is possible to charge multiple EVs from a single nanogrid.

    • Suppose the operation charge_from_grid is selected with \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}}. Then, each contestant gets WA (Wrong Answer) if one of the conditions below is violated.
      • EV is on a vertex where a nanogrid is located u \in V_{\mathrm{grid}}.
      • \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}} is a natural number.
      • Charged amount for each EV does not exceed the maximum charge/discharge speed: \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}} \leq V_{\max}^{\mathrm{EV}}
      • The resulting charged capacity for each EV does not exceed the upper limit C^{\mathrm{EV}}_{\max}: C^{\mathrm{EV}}_{t} + \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}} \leq C^{\mathrm{EV}}_{\max}

  • charge_to_grid \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}}: Charge a nanogrid from the EV by \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}}. The charged capacity of the EV in the next step C^{\mathrm{EV}}_{t+1} becomes C^{\mathrm{EV}}_{t+1} \leftarrow C^{\mathrm{EV}}_{t} - \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge},t}. It is possible to charge a nanogrid from multiple EVs. It is also possible to charge EVs from a nanogrid and charge the nanogrid from other EVs simultaneously.

    • Suppose the operation charge_to_grid is selected with \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}}. Then, each contestant gets WA (Wrong Answer) if one of the conditions below is violated.
      • EV is on a vertex where a nanogrid is located u \in V_{\mathrm{grid}}.
      • \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}} is a natural number.
      • Charged amount for each EV does not exceed the maximum charge/discharge speed: \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}} \leq V_{\max}^{\mathrm{EV}}
      • The resulting charged capacity for each EV is not negative: C^{\mathrm{EV}}_{t} - \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}} \geq 0

Charge/Discharge to the Battery of a Nanogrid

For each nanogrid, the charged capacity of the battery varies in time depending on the difference between generated and consumed powers and the amount of charge/discharge to EVs. For each time t, sums of the difference between generated and consumed powers and gross difference between charged/discharged amounts to EVs from the nanogrid correspond to power excess or shortage in the nanogrid. If the power excess occurs, the battery is charged by the amount provided that the power excess does not exceed the maximum charge speed of the battery and the resulting charged capacity of the battery does not exceed its upper limit. If the power excess exceeds the maximum charge speed of the battery, the excess amount is discarded and the battery is charged by the maximum charge speed. If the resulting charged capacity of the battery exceeds its upper limit, the charged capacity is set to the upper limit at the next step and the excess amount is discarded. If the power shortage occurs instead, the power shortage is compensated by discharging the battery provided that the power shortage does not fall below the maximum discharge speed of the battery and the resulting charged capacity of the battery is not negative. If the power shortage falls below the maximum discharge speed of the battery, the power shortage is covered by discharging the battery by the maximum discharge speed and by power supplied from the outside. If the resulting charged capacity of the battery is negative, the charged capacity of the battery is set to zero in the next step and shortage is supplied from the outside. In all the cases, each EV is charged or discharged by the amount prescribed by each contestant.

Algorithm to determine an amount of charge/discharge to the battery in the next step consists of the following 4 steps.

• Step 1: Compute the power excess or shortage in each nanogrid at time t \Delta^{\mathrm{grid}}_{\mathrm{total}}.
  \Delta^{\mathrm{grid}}_{\mathrm{total}} = \Delta^{\mathrm{grid}}_{\mathrm{gen},t} - \sum_{i \in \mathrm{all EV}} \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}i}_{\mathrm{charge},t} + \sum_{i \in \mathrm{all EV}} \Delta^{\mathrm{EV}i \rightarrow \mathrm{grid}}_{\mathrm{charge},t}
  Here, each variable is defined as follows.

  • \Delta^{\mathrm{grid}}_{\mathrm{gen},t}: the difference between generated and consumed powers at the nanogrid at the time t, which is sums of predicted difference between generated and consumed powers \Delta^{\mathrm{grid,predict}}_{\mathrm{gen},t}, a stochastic fluctuation \delta_{t}, and the variation due to downpour and sudden clear sky. Note that the time series of predicted difference between generated and consumed powers is informed to each contestant in the beginning of each test case but the stochastic fluctuation is not informed until the time t (informed at the next time step t+1).
  • \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}i}_{\mathrm{charge},t}: Charged amount to the i-th EV from the nanogrid prescribed by the contestant at the time t
  • \Delta^{\mathrm{EV}i \rightarrow \mathrm{grid}}_{\mathrm{charge},t}: Charged amount to the nanogrid from the i-th EV prescribed by the contestant at the time t

• Step 2: In case of \Delta^{\mathrm{grid}}_{\mathrm{total}} \geq \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{\max}-C^{\mathrm{grid}}_{t} \right\},
  The charged capacity of the nanogrid at the time t+1 is determined by the following equation:
  C^{\mathrm{grid}}_{t+1} \leftarrow C^{\mathrm{grid}}_{t}+\min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{\max}-C^{\mathrm{grid}}_{t} \right\}
  Physically, this means if the power excess exceeds the maximum charge/discharge speed or the remaining capacity of the battery, the excess amount is discarded.
  

• Step 3: In case of \Delta^{\mathrm{grid}}_{\mathrm{total}} < - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{t} \right\},
  The charged capacity of the nanogrid at the time t+1 is determined by the following equation:
  C^{\mathrm{grid}}_{t+1} \leftarrow C^{\mathrm{grid}}_{t} - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{t} \right\}
  If the power shortage cannot be compensated by discharging the battery, the remaining shortage：
  L_t = - \Delta^{\mathrm{grid}}_{\mathrm{total}} - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{t} \right\}(>0)
  is supplied from the outside. In this case, the score is deducted in proportion to the supplied electricity with a factor \gamma. (For the detail, see Scoring.)。
  

• Step 4: The other cases than the cases in step 2 and 3,
  The charged capacity of the nanogrid at the time t+1 is determined by the following equation:
  C^{\mathrm{grid}}_{t+1} \leftarrow C^{\mathrm{grid}}_{t} + \Delta^{\mathrm{grid}}_{\mathrm{total}}
  

Scoring

• During the contest the total score of a submission is determined by summing the score of the submission with respect to 16 test cases. Among these test cases, the numbers of sunny without downpour, sunny with downpour, rainy without sudden clear sky, and rainy with sudden clear sky are fixed at 6, 2, 6, and 2, respectively.

• The score is computed by the following equation.
  \mathrm{Score}=\sum_{i=1}^{N_{\mathrm{EV}}} C_{t=T_{\max}}^{\mathrm{EV}i} + \sum_{i=1}^{N_{\mathrm{grid}}} C_{t=T_{\max}}^{\mathrm{grid}i} - \gamma \sum_{t=0}^{T_{\max}-1} \sum_{i=1}^{N_{\mathrm{grid}}} L_{i,t} + 3000000
  Here, the first and the second terms in the equation are the charged capacity of all the EVs and nanogrid at the time t=T_{\max}, respectively. L_{i,t} is power supplied from the outside at the i-th grid at the time t and \gamma is a proportional constant of the penalty and L_{i,t}. The value of L_{i,t} is set to L_{i,t} = - \Delta^{\mathrm{grid}}_{\mathrm{total}} - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{t} \right\}(L_{i,t}>0) if the step 3 is executed in Charge/Discharge to the Battery of a Nanogrid and is set to L_{i,t}=0 in the other cases.

• After the contest a system test will be performed. To this end, the contestant's last submission will be scored by summing the final score of the submission on 200 previously unseen test cases.
  Please see the table below for a breakdown of the 200 test cases.

Of the 200 test cases, 160 use 6(=N_\mathrm{pattern} \times 2(sunny, rainy)) types of predicted energy balance already disclosed in the toolkit. The remaining 40 test cases use 6(=N_\mathrm{pattern} \times 2(sunny, rainy)) types of predicted energy balance that are not disclosed to the contestants. \Delta_{\mathrm{event}}, p_{\mathrm{event}}, and percentage of nanogrids hit by downpour or sudden clear sky are all the same among 50(=25[sunny with downpour]+25[rainy with sudden clear sky]) test cases.
We are very sorry that the system test specifications have changed unlike the answer to the question received from Mr. yuusanlondon on December 18. As a result of consideration, the organizers of the contest have determined to decide the final standings based on this specification. We appreciate your understanding.
(12/29 postscript) Generation method or generator for undisclosed predicted energy balance will not be released. Patterns of undisclosed predicted energy balance are generated so that the full score for Electricity Management using undisclosed predicted energy balance is comparable to that using disclosed predicted energy balance. (Note that the full score means the upper limit of the score by applying an ideal control method.)

Problem A

Problem A is an interactive problem. To obtain a high score, each contestant is asked to operate (charge/discharge) multiple EVs so that there is no excess or deficiency in the charged capacity of the battery in each nanogrid depending on the energy balance that fluctuates stochastically. Each contestant and a host machine (judge) interact with the following protocol.

The graph G, the weather \mathrm{DayType}, the information related to energy balance, the nanogrid, EVs, the score, and T_\mathrm{max} are outputted only once in the beginning of each test case. For each test case, contestants are supposed to interact with judges T_\mathrm{max} times. Note that \mathrm{info}_t and the score at the time t=T_\mathrm{max} must be read by the contestant code (otherwise it may be TLE).

Input and Output Format 1

In the beginning of each test case, the graph G, the weather \mathrm{DayType}, the information related to energy balance, the nanogrid, EVs, the score, and T_\mathrm{max} are provided through the standard input.

|V| |E|
u_1 v_1 d_1
:
u_{|E|} v_{|E|} d_{|E|}
\mathrm{DayType}
N_\mathrm{div} N_\mathrm{pattern} \sigma^{2}_{\mathrm{ele}} p_{\mathrm{event}} \Delta_{\mathrm{event}}
\mathrm{pw}_{1,1}^{\mathrm{predict}} \mathrm{pw}_{1,2}^{\mathrm{predict}} ... \mathrm{pw}_{1,N_\mathrm{div}}^{\mathrm{predict}}
:
\mathrm{pw}_{N_\mathrm{pattern},1}^{\mathrm{predict}} \mathrm{pw}_{N_\mathrm{pattern},2}^{\mathrm{predict}} ... \mathrm{pw}_{N_\mathrm{pattern},N_\mathrm{div}}^{\mathrm{predict}}
N_\mathrm{grid} C_{\mathrm{init}}^{\mathrm{grid}} C_{\mathrm{max}}^{\mathrm{grid}} V_{\max}^{\mathrm{grid}}
x_1 \mathrm{pattern}_1 
: 
x_{N_\mathrm{grid}} \mathrm{pattern}_{N_\mathrm{grid}} 
N_\mathrm{EV} C_{\mathrm{init}}^{\mathrm{EV}} C_{\mathrm{max}}^{\mathrm{EV}} V_{\max}^{\mathrm{EV}} \Delta_{\mathrm{move}}^{\mathrm{EV}}
\mathrm{pos}_1
:
\mathrm{pos}_{N_\mathrm{EV}}
\gamma
T_\mathrm{max}

• In the 1st line, the number of vertices |V| and the number of edges |E| of the graph G are provided.
• In the following |E| lines, the edges of the graph along with their weights are provided. The i-th line of the lines indicate that there exists an edge connecting u_{i} and v_{i} with the edge weight d_i.
• In the following 1 line, the weather pattern \mathrm{DayType} is provided, which is either \mathrm{DayType} 0 (sunny without downpour), 1 (sunny with downpour), 2 (rainy without sudden clear sky), or 3 (rainy with sudden clear sky).
• In the following 1 line, the number of subintervals of equal length on which the predicted energy balance is constant N_\mathrm{div}, the number of possible patterns of the time series of predicted energy balance N_\mathrm{pattern}, the variance of the stochastic fluctuation of the difference \sigma^{2}_{\mathrm{ele}}, the probability of occurrences of downpour or sudden clear p_{\mathrm{event}} (p_{\mathrm{event}}=0.0 in the case of \mathrm{DayType}=0 or 2), and the variation of energy balance in case of downpour or sudden clear sky \Delta_{\mathrm{event}}.
• In the following N_\mathrm{pattern} lines, the time series of predicted energy balance is provided. The j-th element in the i-th line of the lines (\mathrm{pw}_{i,j}^{\mathrm{predict}}) indicates the predicted energy balance of the j-th subinterval in case of the i-th pattern.
• In the following 1 line, the number of nanogrids N_\mathrm{grid} and the initial value of the charged capacity of the battery for each nanogrid C_{\mathrm{init}}^{\mathrm{grid}} (t=0), the upper limit of the charged capacity of the battery C_{\mathrm{max}}^{\mathrm{grid}}, and the maximum charge/discharge speed of the battery V_{\max}^{\mathrm{grid}} is provided.
• In the following N_\mathrm{grid} lines, the information about each nanogrid is provided. In the N_\mathrm{grid} lines, the i-th line indicates that a nanogrid is located on the vertex x_i whose pattern of the time series of predicted energy balance is \mathrm{pattern}_i.
• In the following 1 line, the number of EVs N_\mathrm{EV}, their initial charged capacity C_{\mathrm{init}}^{\mathrm{EV}}, their maximum charged capacity C_{\mathrm{max}}^{\mathrm{EV}}, and their maximum charge/discharge speed V_{\max}^{\mathrm{EV}}, and the amount of electricity necessary for each EV to travel in a unit distance \Delta_{\mathrm{move}}^{\mathrm{EV}}.
• In the following N_\mathrm{EV} lines, the position of each EV is provided. In the N_\mathrm{EV} line, the i-th line indicates that the i-th EV is located on the vertex \mathrm{pos}_i.
• In the following 1 line, the proportional constant \gamma for the penalty of getting power supply from outside is provided.
• In the last line, the total time step for each trial of each test case T_{\max} is provided.

Input and Output Format 2

For each time t, contestants get the status of EVs and nanogrids \mathrm{info}_t from the standard input.

x_1 y_1 \mathrm{pw}_{1}^{\mathrm{actual},t-1} \mathrm{pw}_{1}^{\mathrm{excess},t-1} \mathrm{pw}_{1}^{\mathrm{buy},t-1}
:
x_{N_\mathrm{grid}} y_{N_\mathrm{grid}} \mathrm{pw}_{N_\mathrm{grid}}^{\mathrm{actual},t-1} \mathrm{pw}_{N_\mathrm{grid}}^{\mathrm{excess},t-1} \mathrm{pw}_{N_\mathrm{grid}}^{\mathrm{buy},t-1}
\mathrm{carinfo}_1
:
\mathrm{carinfo}_{N_\mathrm{EV}}

• In the N_\mathrm{grid} lines, the i-th line indicates the charged capacity of the battery of the nanogrid on the vertex x_i is y_i, and \mathrm{pw}_{i}^{\mathrm{actual},t-1}, \mathrm{pw}_{i}^{\mathrm{excess},t-1}, and \mathrm{pw}_{i}^{\mathrm{buy},t-1} indicate actual energy balance, excess amount of power discarded, and power supplied from the outside at the previous time step t-1, respectively. At t=0, \mathrm{pw}_{i}^{\mathrm{actual},t-1}, \mathrm{pw}_{i}^{\mathrm{excess},t-1}, and \mathrm{pw}_{i}^{\mathrm{buy},t-1} are all displayed as 0.
  Note that \mathrm{pw}_{i}^{\mathrm{actual},t-1}, \mathrm{pw}_{i}^{\mathrm{excess},t-1}, and \mathrm{pw}_{i}^{\mathrm{buy},t-1} correspond to \Delta^{\mathrm{grid}}_{\mathrm{gen},t-1}, \Delta^{\mathrm{grid}}_{\mathrm{total},t-1} - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{\max}-C^{\mathrm{grid}}_{t-1} \right\}, and - \Delta^{\mathrm{grid}}_{\mathrm{total},t-1} - \min \left\{ V_{\max}^{\mathrm{grid}}, C^{\mathrm{grid}}_{t-1} \right\}, respectively (see Charge/Discharge to the Battery of a Nanogrid ).
  If "step 2" and "step 3" are not executed at the previous time t−1, \mathrm{pw}_{i}^{\mathrm{excess},t-1} and \mathrm{pw}_{i}^{\mathrm{buy},t-1} are 0, respectively.
• In the following N_\mathrm{EV} groups of 3 lines, the i-th group \mathrm{carinfo}_i indicated the status of the i-th EV. For the detail, see the information below.

Here, \mathrm{carinfo}_i is provided in the following format.

\mathrm{charge}_i
u_i v_i \mathrm{dist\_from}\_u_i \mathrm{dist\_to}\_v_i
N_{\mathrm{adj},i} a_{i,1} a_{i,2} \ldots a_{i,N_\mathrm{adj}}

• The first line indicates that the charged capacity of the i-th EV is \mathrm{charge}_i.
• The second line indicates the present position of i-th. If u_i \ne v_i holds, the i-th EV is on the edge connecting u_i and v_i, and the distance to the vertex u_i is \mathrm{dist\_from}\_u_i and that to v_i is \mathrm{dist\_to}\_v_i. If u_i = v_i holds, the i-th EV is on the vertex u_i (in this case, both \mathrm{dist\_from}\_u_i and \mathrm{dist\_to}\_v_i are displayed as 0).
• The third line indicates that there are N_{\mathrm{adj},i} possible vertices to which the i EV moves by the operation move and a_{i,1}, a_{i,2}、\ldots and a_{i,N_\mathrm{adj}} are the possible vertices.

In responding to the input, contestants are asked to output the operation of each EV \mathrm{command}_i (1 \leq i \leq N_\mathrm{EV}) for each time t (0 \leq t \lt T_{\max}). Each operation should be separated by the new line and the output should end with the new line.

\mathrm{command}_{1}
\mathrm{command}_{2}
:
\mathrm{command}_{N_\mathrm{EV}}

Here, \mathrm{command} should be in the following format. There are four possible operations stay, move w, charge_from_grid, and charge_to_grid for each EV. Contestants should choose one of them for each EV and output it in one line as follows:

• stay
• move w
• charge_from_grid \Delta^{\mathrm{grid} \rightarrow \mathrm{EV}}_{\mathrm{charge}}
• charge_to_grid \Delta^{\mathrm{EV} \rightarrow \mathrm{grid}}_{\mathrm{charge}}

There are constraints for each operation (See EV Operation for EVs for the detail). The behavior of the judge when one of these constraints is violated is undefined.

Input and Output Format 3

After the operation of each EV at t=T_\mathrm{max}-1 is output, \mathrm{info}_t at t=T_\mathrm{max} is provided through the standard input from the judge (the format of \mathrm{info}_t is the same as the format written in Input/Output format 2). On the next line, then, the judge gives the score to the standard input in the following format.

\mathrm{Score}

Constraints for Input and Output

• Of the following numbers, those described as "[float]" are given as floats, and the others are given as integers.

Input and output format 1 provided in the beginning of each test case

• |V| = 225
• 1.5 |V| \leq |E| \leq 2 |V|
• 1 \leq u_{i}, v_{i} \leq |V|, u_i \ne v_i (1 \leq i \leq |E|)
• 1 \leq d_i \leq \lceil 2\sqrt{2|V|} \rceil (1 \leq i \leq |E|)
• The graph G is guaranteed to be simple and connected.
• \mathrm{DayType} \in \left\{ 0, 1, 2, 3 \right\}
• N_\mathrm{div} = 20
• N_\mathrm{pattern} = 3
• \sigma^{2}_{\mathrm{ele}} = 100
• p_{\mathrm{event}} \in \left\{ 0.0, 0.1 \right\} "[float]"
• \Delta_{\mathrm{event}} = 1000
• -1000 \lt \mathrm{pw}_{i,j}^{\mathrm{predict}} \lt 1000 (1 \leq i \leq N_\mathrm{pattern}, 1 \leq j \leq N_\mathrm{div})
• N_\mathrm{grid} = 20
• C_{\mathrm{init}}^{\mathrm{grid}} = 25000
• C_{\mathrm{max}}^{\mathrm{grid}} = 50000
• V_{\max}^{\mathrm{grid}} = 800
• 1 \leq x_i \leq |V| (if i \neq j, x_i \neq x_j. 1 \leq i \leq N_\mathrm{grid})
• 1 \leq \mathrm{pattern}_i \leq N_\mathrm{pattern} (1 \leq i \leq N_\mathrm{grid})
• N_{\min}^{\mathrm{EV}} = 15
• N_{\max}^{\mathrm{EV}} = 25
• N_{\min}^{\mathrm{EV}} \leq N_\mathrm{EV} \leq N_{\max}^{\mathrm{EV}}
• C_{\mathrm{init}}^{\mathrm{EV}} = 12500
• C_{\mathrm{max}}^{\mathrm{EV}} = 25000
• V_{\max}^{\mathrm{EV}} = 400
• \Delta_{\mathrm{move}}^{\mathrm{EV}} = 50
• 1 \leq \mathrm{pos}_i \leq |V| (1 \leq i \leq N_\mathrm{EV})
• \gamma = 2.0 "[float]"
• T_\mathrm{max} = 1000

Input and output format 2 provided for each time step

• 1 \leq x_i \leq |V| (if i \neq j, x_i \neq x_j. 1 \leq i \leq N_\mathrm{grid})
• 0 \leq y_i \leq C_{\mathrm{max}}^{\mathrm{grid}} (1 \leq i \leq N_\mathrm{grid})
• -10000 \lt \mathrm{pw}_{i}^{\mathrm{actual},j} \lt 10000 (1 \leq i \leq N_\mathrm{grid}, -1 \leq j \leq T_\mathrm{max}-2)
• 0 \leq \mathrm{pw}_{i}^{\mathrm{excess},j} \lt 10000, (1 \leq i \leq N_\mathrm{grid}, -1 \leq j \leq T_\mathrm{max}-2)
• 0 \leq \mathrm{pw}_{i}^{\mathrm{buy},j} \lt 10000, (1 \leq i \leq N_\mathrm{grid}, -1 \leq j \leq T_\mathrm{max}-2)
• 0 \leq \mathrm{charge}_i \leq C_{\mathrm{max}}^{\mathrm{EV}} (1 \leq i \leq N_\mathrm{EV})
• 1 \leq u_i, v_i \leq |V| (1 \leq i \leq N_\mathrm{EV})
• 0 \leq \mathrm{dist\_from}\_u_i \leq \lceil 2\sqrt{2|V|} \rceil (1 \leq i \leq N_\mathrm{EV})
• 0 \leq \mathrm{dist\_to}\_v_i \leq \lceil 2\sqrt{2|V|} \rceil (1 \leq i \leq N_\mathrm{EV})
• 1 \leq N_{\mathrm{adj},i} \leq 5(\mathrm{MaxDegree}) (1 \leq i \leq N_\mathrm{EV})
• 1 \leq a_{i,j} \leq |V| (1 \leq i \leq N_\mathrm{EV}, 1 \leq j \leq N_{\mathrm{adj},i})

Input and output format 3 provided at the end of each test case

• \mathrm{Score} "[float]"

Example of Inputs and Outputs

Note: This example is to explain how a judge and a contestant interact with each other through inputs and outputs. To simplify the explanation, some of the parameter values like the number of vertices are set to small and they may be outside of the ranges in Constraints of Input and Output. For example, the number of vertices is set to 4 in this example but is set to 225 in each test case.

4 4
1 2 1
2 3 2
3 4 3
4 1 1
0
2 2 1 0 10
5 -2
-4 4
2 10 20 4
1 1
4 2
2 5 10 2 1
2
4
0.5
4

1 10 0 0 0
4 10 0 0 0
5
2 2 0 0
2 1 3
5
4 4 0 0
2 1 3

move 1
charge_from_grid 2

1 14 5 1 0
4 6 -4 0 2
4
1 1 0 0
2 2 4
7
4 4 0 0
2 1 3

stay
charge_from_grid 2

1 18 5 1 0 
4 2 -4 0 2
4
1 1 0 0
2 2 4
9
4 4 0 0
2 1 3

move 4
charge_to_grid 2

1 17 -1 0 0
4 6 3 1 0
3
4 4 0 0
2 1 3
7
4 4 0 0
2 1 3

stay
move 1

1 15 -2 0 0
4 10 5 1 0
3
4 4 0 0
2 1 3
6
1 1 0 0
2 2 4
3000032.0

Sample Code A

A software toolkit for generation of input samples (test cases), scoring and testing on a local contestant environment is provided through the following link. Sample code for beginners is also available.
The toolkit has been updated because minor bugs were found. (December 18th)
The toolkit that can also be used on windows (Cygwin and WSL) has been released. The English version of the README (short ver.) has also been added. A bug related to constraints has also been fixed. (December 18th)
The English version of the README (full version) has been released. Also, a small error in the Japanese version of the README has been fixed. (December 21st)
The toolkit has been updated according to a fix in the judge system regarding submission of the source code written in Python etc. Also, sample code written in Python has been included. Please see the README for how to use it.(January 6th)
The toolkit has been updated.(A fix regarding DEBUG_LEVEL, etc.) Sample code has also been updated. (January 12th)

• Input sample (test case) generator
• Tester
• Sample code for beginners