Problem Overview

This problem is to maximize utilization of available machinery and personnel (referred to as “workers” for simplicity) for an agricultural equipment sharing service, performing agricultural work (referred to as “jobs”) while maximizing reward*. Instructions to workers for moving and performing work are output, to handle many jobs that are distributed over a space. Each job is composed of multiple “tasks” requiring a specific amount of processing, and is considered complete when workers have processed these tasks. Reward is obtained by completing jobs, but amount of reward depends on when tasks were completed, so the appropriate time-frame for handling each task must be considered. The number of tasks that a worker can handle at a particular time is also dependent on the capabilities of the worker.

*Reward: Assuming factors such as the harvest time for the crops and the rate of renewable energy supplied to agricultural equipment.

The following data is given as the initial input.

1. Work time frame
2. Geographical data (graph)
3. Worker data
4. All job data

For this input, contestants will produce the following output:

1. Worker actions for all time points in the work time frame.

The total reward obtained for work will be the score.

More detailed description is given below.

Input 1

The initial input is:

1. Work time frame
2. Geographical data(graph)
3. Worker data
4. All job data

This data is given on standard input in the following format:

T_{\rm{max}}\\
N_V\,\,N_E\\
u_1\quad v_1\quad d_1\\
\vdots\\
u_{N_E}\,\, v_{N_E}\,\, d_{N_E}\\
N_{\rm{worker}}\\
v^{\rm{init}}_1\,\,L^\text{max}_1\,\,N^{\rm{JobType}}_1\,\,\text{Type}^1_1\,\,\text{Type}^1_2\,\,\cdots \text{Type}^1_{N^{\rm{JobType}}_1}\\
\vdots\\
v^{\rm{init}}_{N_{\rm{worker}}}\,\,L^\text{max}_{N_{\rm{worker}}}\,\,N^{\rm{JobType}}_{N_{\rm{worker}}}\,\,\text{Type}^{N_{\rm{worker}}}_1\,\,\text{Type}^{N_{\rm{worker}}}_2\,\,\cdots \text{Type}^{N_{\rm{worker}}}_{N^{\rm{JobType}}_1}\\
N_{\rm{job}}\\
\text{Job}_1\\
\vdots\\
\text{Job}_{N_{\rm{job}}}

(The structure for \text{Job}_i is described below)

Work Time Frame

• Input
  • The length of the work time frame,T_\text{max}, is given in the first line.

For this problem, time values, t, will be integer values from 1 to T_{\text{max}}.

300

Geographical Data

• Input
  • The next line gives the number of vertices, N_V, and edges, N_E, for a graph representing geographical data for the problem (a connected, non-directed graph with positive weightings).
    • The N_V individual vertices will be numbered from 1 to N_V.
  • The following N_E lines give data for each edge: vertices u_i,v_i, and weight d_i (distance).Note that 1\leq i \leq N_E.

As described below, jobs are located on vertices and workers move along edges of this graph.

14 19
1 7 1
1 2 1
2 9 1
2 3 1
3 5 1
3 7 1
3 6 1
4 13 2
4 10 2
4 6 1
4 5 1
6 8 1
7 8 1
8 14 2
9 11 2
10 12 2
10 11 2
12 13 2
13 14 2

Workers

Workers are entities that process jobs, and have capabilities to move and to perform tasks. They operate according to input from the contestant (See Worker actions).

• Input
  • The number of workers, N_{\text{worker}}, is given on the next line.

  • This is followed by N_{\text{worker}} lines with worker configuration data:

    • Initial position (vertex index): v^{\text{init}}_i
    • The maximum tasks the worker can perform per unit time: L^{\text{max}}_i
    • Number of job types the worker can perform, N^{\text{JobType}}_i , and a list of the job types: \text{Type}^i_1\,\,\text{Type}^i_2\,\,\cdots\,\,\text{Type}^i_{N^{\text{JobType}}_i}
    (1\leq i \leq N_{\text{worker}})

These inputs are given in order of worker ID.

The upper limit for number of tasks performable per unit time and the types of jobs that can be done are different for each worker.

5
6 100 3 1 2 3
13 59 1 3
10 55 2 2 3
9 47 3 1 2 3
9 89 1 2

Jobs

A job is work that workers perform at one of the vertices.

• A job:
  • Is a unit of work in the real world, such as harvesting a crop or applying agricultural chemicals.
  • Is composed of multiple smaller work tasks. For example, picking a single piece of fruit, harvesting a set area of rice plants, or spreading a chemical over a set area. These smaller amounts of work comprising a job will be called “tasks”.
  • A job is completed by completing the set number of tasks that comprise the job.
  • In reality, a job could consist of multiple types of task, but in this case, we focus on just the number of tasks. Thus, a job is completed by just processing a set number of a task.
  • The location of a job is different for each job. For this problem, this is represented by locating each job on a vertex of the geographical data graph given with the problem.
• Task processing and reward
  • The tasks for each job are processed by workers.
  • The contestant shall output instructions for each worker to move and perform work, to move them to the vertex of a job and to perform the job’s tasks.
  • The contestant will receive reward by completing jobs (processing the set number of tasks).
  • Each worker has a maximum number of tasks they can process per unit time (L^{\text{max}}), so completion of a job will take a certain amount of time. Typically, a set number of tasks are processed during each time interval from a set time.
  • The amount of reward received when completing a job will depend on the time when tasks were processed. More specifically, it is the sum for all time intervals (t=1,2,\cdots,T_\text{max}), of

    the product of the reward rate per task processed at that time point r(t) \times the number of that task processed at that time point

  • The reward rate, r(t) for processing the task at each time point is different for each job.
  • The total reward collected by all workers will be the main constituent of the score for this problem (Scoring method). Contestants need to decide worker actions to maximize this total reward.
• Dependencies between jobs
  • Some jobs are dependent on other jobs. That is, if a job is dependent on another job, its tasks cannot be processed until the tasks of the other job have been completed.
  • If a job is not dependent on another job, there are no such constraints.

• Input
  • The next line gives N_{\text{job}}, the number of jobs.
  • This is followed by lines indicating the composition of each job, \text{Job}_i, for the N_{\text{job}} jobs(N_{\text{job}}\times 3 lines).

The composition of \text{Job}_i is given in the following format:

\text{ID}^{\rm{job}}_i\,\,\text{Type}_i\,\,N^{\rm{task}}_i\,\,v^{\rm{job}}_i\\
N^{\rm{reward}}_i\,\, t^{\rm{reward}}_{i,1}\,\, y^{\rm{reward}}_{i,1}\cdots t^{\rm{reward}}_{i,N^{\rm{reward}}_i}\,\, y^{\rm{reward}}_{i,N^{\rm{reward}}_i}\\
N^{\rm{depend}}_i\,\, {\rm{id}}^{\rm{depend}}_{i,1}\,\, \cdots \,\,{\rm{id}}^{\rm{depend}}_{i,N^{\rm{depend}}_i}

• Line 1
  • Job ID: \text{ID}^{\text{job}}_i
  • Job type: \text{Type}_i
  • No. of tasks to complete: N^{\text{task}}_i
  • Job location (vertex index): v^{\text{job}}_i
• Line 2 (definition of reward function, r(t))
  • Number of control points in reward function:N^{\text{reward}}_i
  • Control point list:t^{\rm{reward}}_{i,1}\,\,y^{\rm{reward}}_{i,1}\,\,t^{\rm{reward}}_{i,2}\,\,y^{\rm{reward}}_{i,2}\,\,\cdots\,\,t^{\rm{reward}}_{i,N^{\text{reward}}_i}\,\,y^{\rm{reward}}_{i,N^{\text{reward}}_i}
• Line 3 (job dependencies)
  • Number of job dependencies: N^{\text{depend}}_i
  • Dependency job IDs: {\rm{id}}^{\rm{depend}}_{i,1}\,\,{\rm{id}}^{\rm{depend}}_{i,2}\,\, \cdots \,\,{\rm{id}}^{\rm{depend}}_{i,N^{\rm{depend}}_i}

7
1 2 625 8
15 1 0 2 1581724 4 1733369 6 1561173 8 1596919 10 1090320 12 1031662 14 929778 16 1095326 18 665006 20 757205 22 567001 24 600233 26 576475 27 0
0
2 3 993 14
15 2 0 3 1147309 5 1186255 7 1098060 9 836498 11 872163 13 1071865 15 1408708 17 2135395 19 1517111 21 1079036 23 740032 25 904947 27 976790 28 0
1 1
3 2 1310 14
15 2 0 3 992842 5 818304 7 676647 9 859283 11 871992 13 859663 15 1776296 17 3025691 19 1304819 21 1606358 23 3469915 25 2801513 27 3046487 28 0
2 2 1
4 2 1356 13
15 3 0 4 2016014 6 2138183 8 1711305 10 2020927 12 2030686 14 1203758 16 973133 18 1102291 20 954221 22 725869 24 700613 26 604824 28 742452 29 0
0
5 1 1225 10
15 5 0 6 1256998 8 1096984 10 820728 12 818626 14 1089776 16 1014615 18 1062766 20 900374 22 1190773 24 1050656 26 1876847 28 1530806 30 952050 31 0
1 4
6 3 1362 7
15 0 0 1 608492 3 960135 5 961858 7 998014 9 1101543 11 1288452 13 1825126 15 1145645 17 1057616 19 1312087 21 991237 23 1123573 25 882743 26 0
2 7 5
7 1 1307 1
15 5 0 6 299791 8 303708 10 533803 12 879014 14 828842 16 946449 18 991630 20 1551550 22 1499622 24 1793967 26 1425447 28 1732069 30 1207139 31 0
0

300
14 19
1 7 1
1 2 1
2 9 1
2 3 1
3 5 1
3 7 1
3 6 1
4 13 2
4 10 2
4 6 1
4 5 1
6 8 1
7 8 1
8 14 2
9 11 2
10 12 2
10 11 2
12 13 2
13 14 2
5
6 100 3 1 2 3
13 59 1 3
10 55 2 2 3
9 47 3 1 2 3
9 89 1 2
7
1 2 625 8
15 1 0 2 1581724 4 1733369 6 1561173 8 1596919 10 1090320 12 1031662 14 929778 16 1095326 18 665006 20 757205 22 567001 24 600233 26 576475 27 0
0
2 3 993 14
15 2 0 3 1147309 5 1186255 7 1098060 9 836498 11 872163 13 1071865 15 1408708 17 2135395 19 1517111 21 1079036 23 740032 25 904947 27 976790 28 0
1 1
3 2 1310 14
15 2 0 3 992842 5 818304 7 676647 9 859283 11 871992 13 859663 15 1776296 17 3025691 19 1304819 21 1606358 23 3469915 25 2801513 27 3046487 28 0
2 2 1
4 2 1356 13
15 3 0 4 2016014 6 2138183 8 1711305 10 2020927 12 2030686 14 1203758 16 973133 18 1102291 20 954221 22 725869 24 700613 26 604824 28 742452 29 0
0
5 1 1225 10
15 5 0 6 1256998 8 1096984 10 820728 12 818626 14 1089776 16 1014615 18 1062766 20 900374 22 1190773 24 1050656 26 1876847 28 1530806 30 952050 31 0
1 4
6 3 1362 7
15 0 0 1 608492 3 960135 5 961858 7 998014 9 1101543 11 1288452 13 1825126 15 1145645 17 1057616 19 1312087 21 991237 23 1123573 25 882743 26 0
2 7 5
7 1 1307 1
15 5 0 6 299791 8 303708 10 533803 12 879014 14 828842 16 946449 18 991630 20 1551550 22 1499622 24 1793967 26 1425447 28 1732069 30 1207139 31 0
0

Output 1

Given the data described above, the contestant must produce output for all workers in each time interval in the following format.

\text{Actions}_1\\
\vdots\\
\text{Actions}_{T_\text{max}}

(Insert a line-break after the last line)

Here, \text{Actions}_i represents the actions for all workers at time i, and is represented as follows, given that \text{action}^i_j represents the action of worker j at time i.

\text{action}^i_1\\
\text{action}^i_2\\
\vdots\\
\text{action}^i_{N_{\text{worker}}}

Worker Actions

• stay:Neither move, nor perform a job, staying at the current location.
• move w:Move a distance of 1 along the shortest path from the current position to the vertex which corresponds to vertex index w. If the following constraints are not satisfied, it will result in WA(Wrong Answer).
  • A vertex corresponding to vertex index w must exist.
  • The current position must not be vertex w.
• execute i a:Perform the task for the job with ID=i, a times. If the following constraints are not satisfied, it will result in WA(Wrong Answer).
  • The worker’s current position must be the same as the location of the job with ID=i.
  • The type of the job with ID=i must be included in the job types that the worker can perform.
  • a must be an integer greater than or equal to 1.
  • a must not exceed the amount of remaining tasks for the job with ID=i.
  • a must not exceed L^\text{max}_i, the upper limit for number of tasks the worker can perform.
  • The jobs on which the job with ID=i depends must have been completed.
  • The reward value must be positive.

For move w, if there are 2 or more different shortest paths between the current location and vertex w, how to select one is not specified. In such cases, the contestant can choose the desired path by repeatedly selecting and moving to points along the path.

Specifying an \text{action} string that does not match any of the patterns above will result in WA(Wrong Answer).

Also, if there exist some jobs whose total task amount processed exceeds its No. of tasks to complete N^{\text{task}}_i, it will result in WA or RE.

• Output
  • For the following N_\text{worker}\times T_\text{max} lines, output the actions, \text{action}^i_j, for each worker, where 1 \leq i \leq T_\text{max} and 1 \leq j \leq N_\text{worker}.

move 8
stay
move 13
stay
stay
execute 1 100
stay
move 13
stay
stay
execute 1 100
stay
move 13
move 1
stay
execute 1 100
stay
move 13
move 1
stay
execute 1 100
stay
move 13
move 1
stay
execute 1 100
stay
move 13
execute 7 47
stay
execute 1 100
stay
execute 4 55
execute 7 47
stay
execute 1 25
move 14
execute 4 55
execute 7 47
stay
stay
move 14
execute 4 55
execute 7 47
stay
stay
move 14
execute 4 55
execute 7 47
stay
stay
move 14
execute 4 55
execute 7 47
stay
stay
move 14
execute 4 55
execute 7 47
stay
stay
move 14
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
execute 2 59
execute 4 55
execute 7 47
stay
stay
stay
execute 4 55
execute 7 47
stay
stay
stay
stay
execute 7 47
stay
stay
stay
stay
execute 7 47
stay

Ranking method

Provisional test

For the provisional test, 50 test cases are randomly selected from the ones used for the system test and executed. However, only one test case is selected for one parameter pattern.

The evaluation method is the same as for the system test. See the System test section below.

System test

For the system test, some of the following characteristic parameters are given to satisfy the properties listed in the Remarks column:

For each pattern of these, 40 test cases with different seed values are generated, for a total of 3 \times 3 \times4\times 3 \times 40 = 4320 test cases.

This is only pattern generation of the parameters in the above table. Apart from this process, data such as geographic information, jobs, etc. are generated for each test case.

Relative evaluation system is used for rankings. For each test case, we compute the relative score \text{round}(10^{9} \times \frac{\text{YOUR\_SCORE}}{\text{MAX\_SCORE}}), where \text{YOUR\_SCORE} is your Score and \text{MAX\_SCORE} is the highest score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.

If your submission produces invalid output or exceeds the time limit for some test cases, only the score for those test cases will be zero.

The system test will be performed only for the last submission which received a result other than CE. Be careful not to make a mistake in the final submission.

About Relative Evaluation System

In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE . Only the last submissions are used to calculate the highest score among all competitors for each test case in calculating the relative scores.

The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is an absolute score obtained by summing up the scores for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces invalid output or exceeds the time limit for some test cases, the absolute score shown in the submissions page becomes 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.

Constraints

• Character encoding is UTF-8 (although only ASCII characters are used).
• End-of-line code is LF(0x0A).
• Delimiter is the half-width space (0x20)
• Trailing delimiter characters are permitted.

For decimal values, [Decimal] is appended.

Input 1

• 300 \leq T_\text{max} \leq 1000 and T_\text{max} is a multiple of 100
• 150\leq N_V\leq 2000
• 4N_V/3\leq N_E\leq 2 N_V
• 1\leq u_i,v_i\leq N_V, u_i \neq v_i (1 \leq i \leq N_E)
• 1\leq d_i \leq 128 (1 \leq i \leq N_E)
• The graph given is guaranteed to be connected and not contain self-loops or multiple edges.
• 1 \leq N_\text{worker} \leq 10
• 1\leq v^\text{init}_i \leq N_V (1 \leq i \leq N_\text{worker})
• 30\leq L^\text{max}_i\leq 100 (1 \leq i \leq N_\text{worker})
• 1 \leq N^\text{JobType}_i \leq 3 (1 \leq i \leq N_\text{worker})
• 1\leq \text{Type}^i_j\leq 3 (1 \leq i \leq N_\text{worker},1 \leq j \leq N^\text{JobType}_i)
• 250 \leq N_\text{job} \leq 1003
• \text{ID}^\text{job}_i=i (1 \leq i \leq N_\text{job})
• 1\leq \text{Type}_i\leq 3 and \text{Type}_i is included in the processable job types of 1 or more workers. (1 \leq i \leq N_\text{job})
• 500 \leq N^\text{task}_i \leq 1500(1 \leq i \leq N_\text{job})
• 1 \leq v^\text{job}_i \leq N_V (1 \leq i \leq N_\text{job})
• 1 \leq N^\text{reward}_i \leq 43 (1 \leq i \leq N_\text{job})
• 0\leq t^\text{reward}_{i,1}<t^\text{reward}_{i,2}<\cdots<t^\text{reward}_{i,N^\text{reward}_i}\leq T_\text{max}+1(1 \leq i \leq N_\text{job})
• y^\text{reward}_{i,1}=y^\text{reward}_{i,N^\text{reward}_i}=0,1 \leq y^\text{reward}_{i,j} \leq 10^7 (1 \leq i \leq N_\text{job},2 \leq j \leq N^\text{reward}_i-1)
• 0\leq N^\text{depend}_i\leq 3(1 \leq i \leq N_\text{job})
• 1 \leq \text{id}^\text{depend}_{i,j} \leq N_\text{job},\text{id}^\text{depend}_{i,j} \neq \text{id}^\text{depend}_{i,k},\text{id}^\text{depend}_{i,j}\neq i (1 \leq i \leq N_\text{job},1\leq j \leq N^\text{depend}_i,1\leq k\leq N^\text{depend}_i,j\neq k)
• Job dependency relationships can be viewed as a directed acyclic graph (which will not necessarily be connected) with each job as a vertex and dependencies between jobs as directed edges, and each connected component having size of 4 or less.

Input 2 (Scoring)

• 0 \leq S \leq 2^{63}-1

Geographical data

• L=2048
• d_\text{max}\in\{5,6,7\}
• s=1
• 0.3 \leq C < 0.4 [Decimal]
• M=\text{round}(0.45(4^{d_\text{max}+1}-1)/(3\times 2^{d_\text{max}-5}))

Segmented linear reward function

• 100 \leq L \leq T_\text{max}
• l = 25
• 10^6 \leq s \leq 2\times 10^6
• 0.3 \leq \sigma' < 0.38 [Decimal]
• M = 10^7
• m = 1

Toolkit

A toolkit for this problem can be downloaded from here. It includes the following:

• Judge program (for both A, B)
• Test case generator (both A and B)
• Sample codes (In C++, one each for problems A and B)
• Visualizer

Visualizer

Log files (in JSON format) generated from the judge program in the toolkit can be used to visualize the results.

The visualizer is included in the toolkit, but is also available here on the server.

For details, please read the README in the toolkit and the description at the bottom of the visualizer page.