[Solution] Task Scheduling and Data Assignment Codeforces Solution

A. Task Scheduling and Data Assignment

time limit per test

15 seconds

memory limit per test

1024 megabytes

input

standard input

output

standard output

With the rapid development of chip hardware computing capabilities, hardware architectures are evolving towards more complex multi-core and heterogeneous architectures. In this problem, your goal is to design an efficient task scheduling algorithm together with a memory allocation policy for the software-hardware co-optimization problem that exists widely in operating systems, distributed systems, and compilers.

Description

There are ℓ$\ell$ tasks that need to be scheduled on 𝑛$n$ machines with varying processing powers. There are also 𝑚$m$ disks with varying transmission speeds and storage capacities for storing the data generated by each task after its execution.

Task schedule. A task schedule is an assignment of tasks to machines and disks. More specifically, for each task 𝑖$i$, a task schedule specifies three parameters (𝑥𝑖,𝑦𝑖,𝑧𝑖)$(x_i,y_i,z_i)$, meaning that 𝑖$i$ starts at time 𝑥𝑖$x_i$ on machine 𝑦𝑖$y_i$ and stores its data to disk 𝑧𝑖$z_i$. The earliest starting time of any task is 0.

Task Running Process Here are more details about the running process of a task 𝑖$i$ when the task schedule is fixed.

• The processing power of machine 𝑗$j$ is 𝗉𝗈𝗐𝖾𝗋(𝑗)$\mathsf{p}\mathsf{o}\mathsf{w}\mathsf{e}\mathsf{r}(j)$. Each task 𝑖$i$ has a size of 𝗌𝗂𝗓𝖾(𝑖)$\mathsf{s}\mathsf{i}\mathsf{z}\mathsf{e}(i)$, which means it needs ⌈𝗌𝗂𝗓𝖾(𝑖)/𝗉𝗈𝗐𝖾𝗋(𝑦𝑖)⌉$\lceil \mathsf{s}\mathsf{i}\mathsf{z}\mathsf{e}(i)/\mathsf{p}\mathsf{o}\mathsf{w}\mathsf{e}\mathsf{r}(y_i)\rceil$ units of time to execute when it is run on machine 𝑦𝑖$y_i$. Here, ⌈.⌉$\lceil .\rceil$ means rounding up.
• Each disk 𝑘$k$ has a read/write transmission rate of 𝗌𝗉𝖾𝖾𝖽(𝑘)$\mathsf{s}\mathsf{p}\mathsf{e}\mathsf{e}\mathsf{d}(k)$. When a task 𝑖$i$ finishes its execution, it will generate a piece of data of size 𝖽𝖺𝗍𝖺(𝑖)$\mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}(i)$ that needs to be stored on some disk. This storing step will take ⌈𝖽𝖺𝗍𝖺(𝑖)/𝗌𝗉𝖾𝖾𝖽(𝑧𝑖)⌉$\lceil \mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}(i)/\mathsf{s}\mathsf{p}\mathsf{e}\mathsf{e}\mathsf{d}(z_i)\rceil$ units of time if this data is stored on disk 𝑧𝑖$z_i$. Here, the value of time also needs to be rounded up.
• Before a task 𝑖$i$ starts its execution, it needs to read the output data of some other tasks. We let 𝖯𝖱𝖤𝖣𝖽𝖺𝗍𝖺(𝑖)$\mathsf{P}\mathsf{R}\mathsf{E}{\mathsf{D}}_{\mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}}(i)$ denote the set of tasks whose output data are needed by task 𝑖$i$. This will take a total time of ∑𝑗∈𝖯𝖱𝖤𝖣𝖽𝖺𝗍𝖺(𝑖)⌈𝖽𝖺𝗍𝖺(𝑗)/𝗌𝗉𝖾𝖾𝖽(𝑧𝑗)⌉$\sum _{j\in \mathsf{P}\mathsf{R}\mathsf{E}{\mathsf{D}}_{\mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}}(i)}\lceil \mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}(j)/\mathsf{s}\mathsf{p}\mathsf{e}\mathsf{e}\mathsf{d}(z_j)\rceil$ and this must be done before task 𝑖$i$ starts its execution. Note that when calculating the total time, each term needs to be rounded up individually and then summed.

Summarizing the above process, when task 𝑖$i$ starts, it goes through three phases: reading data from other tasks, executing the task, and storing data. For convenience, we denote the starting time of the three phases as 𝑎𝑖,𝑏𝑖,𝑐𝑖$a_i,b_i,c_i$ and the finishing time of the last phase as 𝑑𝑖$d_i$. These values are determined as follows.

• 𝑎𝑖=𝑥𝑖$a_i=x_i$
• 𝑏𝑖=𝑎𝑖+∑𝑗∈𝖯𝖱𝖤𝖣𝖽𝖺𝗍𝖺(𝑖)⌈𝖽𝖺𝗍𝖺(𝑗)/𝗌𝗉𝖾𝖾𝖽(𝑧𝑗)⌉$b_i=a_i+\sum _{j\in \mathsf{P}\mathsf{R}\mathsf{E}{\mathsf{D}}_{\mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}}(i)}\lceil \mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}(j)/\mathsf{s}\mathsf{p}\mathsf{e}\mathsf{e}\mathsf{d}(z_j)\rceil$.
• 𝑐𝑖=𝑏𝑖+⌈𝗌𝗂𝗓𝖾(𝑖)/𝗉𝗈𝗐𝖾𝗋(𝑦𝑖)⌉$c_i=b_i+\lceil \mathsf{s}\mathsf{i}\mathsf{z}\mathsf{e}(i)/\mathsf{p}\mathsf{o}\mathsf{w}\mathsf{e}\mathsf{r}(y_i)\rceil$.
• 𝑑𝑖=𝑐𝑖+⌈𝖽𝖺𝗍𝖺(𝑖)/𝗌𝗉𝖾𝖾𝖽(𝑧𝑖)⌉$d_i=c_i+\lceil \mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}(i)/\mathsf{s}\mathsf{p}\mathsf{e}\mathsf{e}\mathsf{d}(z_i)\rceil$.

In addition, a feasible task schedule should satisfy the following requirements:

• No preemption: Each machine executes only one task or transmits one data at a time, and no interruption is allowed during its lifecycle. In other words, for each pair of tasks 𝑖$i$ and 𝑗$j$ such that 𝑦𝑖=𝑦𝑗$y_i=y_j$, the two intervals (𝑎𝑖,𝑑𝑖)$(a_i,d_i)$ and (𝑎𝑗,𝑑𝑗)$(a_j,d_j)$ cannot have any overlaps.
• Task dependencies: Each task 𝑖$i$ has a list of task-dependent tasks, denoted by 𝖯𝖱𝖤𝖣𝗍𝖺𝗌𝗄(𝑖)$\mathsf{P}\mathsf{R}\mathsf{E}{\mathsf{D}}_{\mathsf{t}\mathsf{a}\mathsf{s}\mathsf{k}}(i)$. For each task 𝑗∈𝖯𝖱𝖤𝖣𝗍𝖺𝗌𝗄(𝑖)$j\in \mathsf{P}\mathsf{R}\mathsf{E}{\mathsf{D}}_{\mathsf{t}\mathsf{a}\mathsf{s}\mathsf{k}}(i)$, task 𝑖$i$ cannot start until 𝑗$j$ finishes its execution. That is, it must satisfy 𝑎𝑖≥𝑐𝑗$a_i\ge c_j$. Note that if 𝑖$i$ is scheduled on the same machine with 𝑗$j$, then it still needs to wait for 𝑗$j$ to complete storing its data.
• Data dependencies: For each task 𝑗∈𝖯𝖱𝖤𝖣𝖽𝖺𝗍𝖺(𝑖)$j\in \mathsf{P}\mathsf{R}\mathsf{E}{\mathsf{D}}_{\mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}}(i)$, task 𝑖$i$ cannot start until 𝑗$j$ finishes storing its data. That is, it must satisfy 𝑎𝑖≥𝑑𝑗$a_i\ge d_j$.
• Affinity of machines: Each task 𝑖$i$ has a list of affinitive machines. denoted by 𝐴𝑖$A_i$, that it can be assigned to. Each task must be scheduled on one of its affinitive machines. That is, it must satisfy 𝑦𝑖∈𝐴𝑖$y_i\in A_i$.
• Disk Capacity: Each disk 𝑘$k$ has a storage capacity of 𝖼𝖺𝗉𝖺𝖼𝗂𝗍𝗒(𝑘)$\mathsf{c}\mathsf{a}\mathsf{p}\mathsf{a}\mathsf{c}\mathsf{i}\mathsf{t}\mathsf{y}(k)$. The total size of all data stored on the same disk cannot exceed that disk's capacity. That is, for each disk 𝑘$k$ it must satisfy ∑𝑖:𝑧𝑖=𝑘𝖽𝖺𝗍𝖺(𝑖)≤𝖼𝖺𝗉𝖺𝖼𝗂𝗍𝗒(𝑘)$\sum _{i:z_i=k}\mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}(i)\le \mathsf{c}\mathsf{a}\mathsf{p}\mathsf{a}\mathsf{c}\mathsf{i}\mathsf{t}\mathsf{y}(k)$.

Given a feasible schedule, the makespan of this schedule is the finishing time of the last task. In other words, 𝗆𝖺𝗄𝖾𝗌𝗉𝖺𝗇=max1≤𝑖≤ℓ𝑑𝑖$\mathsf{m}\mathsf{a}\mathsf{k}\mathsf{e}\mathsf{s}\mathsf{p}\mathsf{a}\mathsf{n}=\underset{1\le i\le \ell }{max}{d}_i$

Objectives

Your objective is to find a feasible task schedule that minimizes the makespan.

Input

The first line contains an integer ℓ$\ell$ representing the number of tasks. In the following ℓ$\ell$ lines, each line represents a task: The first three integers represent task id 𝑖$i$, task size 𝗌𝗂𝗓𝖾(𝑖)$\mathsf{s}\mathsf{i}\mathsf{z}\mathsf{e}(i)$, and the size of its output data 𝖽𝖺𝗍𝖺(𝑖)$\mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}(i)$. All task ids are distinctive integers between 1$1$ and ℓ$\ell$. The fourth integer 𝑘$k$ is the number of affinitive machines for this task, and the remaining 𝑘$k$ integers are the IDs of these affinitive machines and they are distinctive as well.

Next, a line contains an integer 𝑛$n$ representing the number of machines. In the following 𝑛$n$ lines, each line has two integers representing machine id 𝑗$j$ and its power 𝗉𝗈𝗐𝖾𝗋(𝑗)$\mathsf{p}\mathsf{o}\mathsf{w}\mathsf{e}\mathsf{r}(j)$. All machine ids are distinctive integers between 1$1$ and 𝑛$n$.

Next again, a line contains an integer 𝑚$m$ representing the number of disks. In the following 𝑚$m$ lines, each line has three integers representing disk id 𝑘$k$, its speed 𝗌𝗉𝖾𝖾𝖽(𝑘)$\mathsf{s}\mathsf{p}\mathsf{e}\mathsf{e}\mathsf{d}(k)$, and capacity 𝖼𝖺𝗉𝖺𝖼𝗂𝗍𝗒(𝑘)$\mathsf{c}\mathsf{a}\mathsf{p}\mathsf{a}\mathsf{c}\mathsf{i}\mathsf{t}\mathsf{y}(k)$. All disk ids are distinctive integers between 1$1$ and 𝑘$k$.

The remaining part describes the two types of dependencies between tasks.

The first line of this part is an integer 𝑁$N$ representing the number of data dependencies. In the following 𝑁$N$ lines, each line contains two integers 𝑖,𝑗$i,j$, which means task 𝑗$j$ is data-dependent on task 𝑖$i$.

Next, there is a new line with an integer 𝑀$M$ representing the number of task dependencies. In the following 𝑀$M$ lines, each line contains two integers 𝑖,𝑗$i,j$, which means task 𝑗$j$ is task-dependent on task 𝑖$i$.

All numbers on the same line are separated by whitespaces.

Variable constraints

• number of tasks: 6≤𝑙≤10000$6\le l\le 10000$
• number of machines: 1≤𝑛≤50$1\le n\le 50$
• number of disks: 10≤𝑚≤30$10\le m\le 30$
• size of task: 10≤𝗌𝗂𝗓𝖾(𝑖)≤600$10\le \mathsf{s}\mathsf{i}\mathsf{z}\mathsf{e}(i)\le 600$
• size of outputted data: 1≤𝖽𝖺𝗍𝖺(𝑖)≤20$1\le \mathsf{d}\mathsf{a}\mathsf{t}\mathsf{a}(i)\le 20$
• computing power of machines: 1≤𝗉𝗈𝗐𝖾𝗋(𝑖)≤20$1\le \mathsf{p}\mathsf{o}\mathsf{w}\mathsf{e}\mathsf{r}(i)\le 20$
• capacity of disks: 1≤𝖼𝖺𝗉𝖺𝖼𝗂𝗍𝗒≤1050000$1\le \mathsf{c}\mathsf{a}\mathsf{p}\mathsf{a}\mathsf{c}\mathsf{i}\mathsf{t}\mathsf{y}\le 1050000$
• rate of disks: 1≤𝗌𝗉𝖾𝖾𝖽≤20$1\le \mathsf{s}\mathsf{p}\mathsf{e}\mathsf{e}\mathsf{d}\le 20$
• all the ids are consequent and starts from one.
• the dependence graph which includes both two types of dependence edge is acyclic.

Output

You should output ℓ$\ell$ lines describing the task schedule for all tasks. The 𝑖$i$th line should contain four integers 𝑖,𝑥𝑖,𝑦𝑖,𝑧𝑖$i,x_i,y_i,z_i$, separated by whitespaces, meaning that task 𝑖$i$ will start at time 𝑥𝑖$x_i$ on machine 𝑦𝑖$y_i$ and store its data on disk 𝑧𝑖$z_i$.

Scoring

For each test, the score is your makespan divided by the lower bound, where the lower bound is computed via

where, 

𝗈𝗎𝗍𝖽𝖾𝗀𝗋𝖾𝖾(𝑖)$\mathsf{o}\mathsf{u}\mathsf{t}\mathsf{d}\mathsf{e}\mathsf{g}\mathsf{r}\mathsf{e}\mathsf{e}(i)$ means the number of edges that go out from task 𝑖$i$ in DAG (In other words, it is the number of tasks that depends on task 𝑖$i$).

We guarantee that all the cases have feasible solutions since there is a disk of rate 1$1$ with a capacity greater or equal to the sum of 𝗌𝗂𝗓𝖾(𝑖)$\mathsf{s}\mathsf{i}\mathsf{z}\mathsf{e}(i)$ over all tasks 𝑖$i$. If you output an invalid solution, you get zero. Here, makespan stands for the latest end-time of all tasks when the earliest start time of all tasks is zero. The final score is the summation of all tests' scores.

Note

At time 0$0$, 𝐽1$J_1$ is scheduled on 𝑀2$M_2$ and stores its output to 𝐷2$D_2$, it costs 40/2$40/2$ and 6/2$6/2$ unit time in executing phase and writing phase, respectively. So, it finishes at time 23$23$. Note that the time cost in the reading phase is zero since it does not data-dependent on any task.

At time 23$23$, 𝐽2$J_2$ is scheduled on 𝑀1$M_1$ and reads its data from 𝐷2$D_2$ and stores its output to 𝐷1$D_1$. Finally, It costs 6/2+20+6=29$6/2+20+6=29$ unit time and it finishes at time 52$52$.

At the same time, 𝐽3$J_3$ is scheduled on 𝑀2$M_2$ and reads its data from 𝐷2$D_2$. And it costs 6/2+96/2+10/2$6/2+96/2+10/2$ and finishes at 79$79$. Note though 𝐽3$J_3$ and 𝐽1$J_1$ are running on the same machine, 𝐽3$J_3$ still needs to read the 𝐽1$J_1$'s outputted data from disk.

At time 52$52$, 𝐽4$J_4$ starts on 𝑀1$M_1$ and reads data of 𝐽1$J_1$ and 𝐽2$J_2$, which costs 6/2+6/1$6/2+6/1$ unit time. So the final time cost is (3+6)+20+6$(3+6)+20+6$ and finishes at time 87$87$.

At time 79$79$, 𝐽5$J_5$ starts on 𝑀2$M_2$ and costs 10/2+6$10/2+6$ unit time to read data and another 60/2$60/2$ unit time to execute, and does not output any data. So, it finishes at time 120$120$.

At time 87$87$, 𝐽6$J_6$ starts on 𝑀1$M_1$ and finishes at time 118$118$.

So, the final makespan is 120$120$ and it is a feasible solution. Let's verify the feasibility of the above solution.

Dependency constraints: In the solution, 𝐽2$J_2$,𝐽3$J_3$ start after 𝐽1$J_1$ and 𝐽4$J_4$ starts after 𝐽1$J_1$,𝐽2$J_2$, and so on.

The affinity of machines: In this case, the only restriction of affinity is that task 6 can only run in machine 1. And in this solution, it DOES.

No preemption: it is obvious.

The quota of disk: (1) The tasks storing data in disk 1 are 𝐽2,𝐽4,𝐽5$J_2,J_4,J_5$, their total data size is 6+6+0<30$6+6+0<30$; (2) The tasks storing data in disk 2 are 𝐽1,𝐽3,𝐽6$J_1,J_3,J_6$, their total data size is 6+10<17$6+10<17$.