Container Service Preheating

Обмеження: 10 сек., 1024 МіБ

In cloud computing environments, virtual machines (VMs) host containerized microservices. When users request to launch a container, the scheduler initially allocates containers to existing VMs, provisioning additional VMs if necessary. However, creating new VMs takes time and it can introduce additional latency for clients. This can result in a poor quality of experience (QoE). We can mitigate this by purchasing a set of VMs before the actual container requests. This strategy is known as “preheating”.

The demand for new containers is unpredictable. Various VM types are available for purchase. Each type of VM has corresponding resource specifications (CPU and memory) and price per unit of time. For each container request, you must decide which VM to run the container on. Once a container is associated with a VM, the container runs on it, occupying a certain amount of resources until the container is deleted. After a container is deleted, the resources are released and can be used by other containers.

You need to determine the optimal number of VMs, the optimal time to pre-provision them and how to place containers into those VMs in order to minimize the total cost, which has two components:

• Resource Reservation Cost (RC): This is the cost of running the VMs.

• Container Launch Delay Cost (DC): This is the cost incurred when a user request cannot be immediately fulfilled due to a lack of available VMs.

You can find more information about scoring in the Scoring section of the problem statement.

Please note that this is an interactive problem. Your solution will communicate with the interactor through the stdin/stdout streams.

Interaction protocol

The first line of the input contains two integers \(m\) and \(d\) — the number of available VM types and VM creation delay. The following \(m\) lines contain the description of the types. Each line contains three space-separated integers: \(cpu_i\), \(mem_i\), and \(price_i\) which represent the number of CPU units, the memory, and the price of the VM type. The VM types are enumerated from 1 to \(m\).

The next line contains a single integer \(t\) — the number of time steps of the interaction. The first line of each time step contains an integer \(e_j\) — the number of events during this time step. In case if \(e_j = 0\), it is followed by an integer \(cnt_j\). This means that there are no events on the current time step, as well as \(cnt_j - 1\) following time steps (\(cnt_j\) empty time steps in total). There will be no input for any of the next \(cnt_j - 1\) time steps and you have to process each of them in a single batch. For each of the \(cnt_j\) time steps you have to print a list of actions as described below.

In case if \(e_j > 0\), the following \(e_j\) lines contain events for the current time step. There are two types of events:

• \(1\ id^{cont}_{jk}\ cpu^{cont}_{jk}\ mem^{cont}_{jk}\): a new container creation request has arrived. The container is identified by \(id^{cont}_{jk}\) and requires \(cpu^{cont}_{jk}\) CPU units and \(mem^{cont}_{jk}\) memory. This request can be fulfilled immediately within the current time step.

• \(2\ id^{cont}_{jk}\): a container with an identifier \(id^{cont}_{jk}\) must be shut down. The resources occupied by this container might be used during the next time step.

After your solution has read the information about the events during the current time step, you have to print a line with an integer \(a_j\) — the number of actions that you want to perform during this time step. Then print \(a_j\) lines, one for each action. There are three possible actions you can perform:

• \(1\ id^{vm}_{jk}\ type^{vm}_{jk}\) — start a new VM with an identifier \(id^{vm}_{jk}\) and a type \(type^{vm}_{jk}\). This action takes \(d\) time steps, meaning the VM becomes available at time step \(x+d\) if provisioned at time step \(x\).

• \(2\ id^{vm}_{jk}\) — shut down a VM with an identifier \(id^{vm}_{jk}\). To perform this action, the VM with an identifier \(id^{vm}_{jk}\) should have no containers allocated before the beginning of this time step. If the last container on a VM is terminated at step \(x\), the VM can be shut down starting from step \(x + 1\).

• \(3\ id^{cont}_{jk}\ id^{vm}_{jk}\) — allocate the container with an identifier \(id^{cont}_{jk}\) on a VM with an identifier \(id^{vm}_{jk}\). To perform this action, the container with an identifier \(id^{cont}_{jk}\) has to not be yet allocated and the VM with an identifier \(id^{vm}_{jk}\) has to have at least \(cpu^{cont}_{id^{cont}_{jk}}\) CPUs and \(mem^{cont}_{id^{cont}_{jk}}\) memory available.

After printing \(a_j\) lines with your actions, ensure the output is flushed, so that the interactor can read your actions and proceed with the next time step.

Please note, that if \(e_j = 0\), you have to print \(cnt_j\) blocks of actions, one for each time step with no events. You should flush the output only after you printed actions for all \(cnt_j\) time steps. This is needed to improve the performance of the i/o of your solution.

If the interactor prints the value \(e_j = -1\) — this means that one of your actions during the previous step was invalid. Your program has to exit immediately. In this case, you will get the Wrong Answer verdict.

After \(t\) time steps, the interactor prints a single integer \(e_{t + 1}\), which equals 0 if your last action is valid or -1 if the last action is invalid. Afterwards, the interaction is over and your solution must exit.

Input constraints

\(1 \le m \le 47\),

\(1 \le d \le 40\),

\(1 \le cpu_i, cpu^{cont}_{jk} \le 10^5\),

\(1 \le mem_i, mem^{cont}_{jk} \le 2 \cdot 10^6\),

\(1 \le price_i \le 2 \cdot 10^5\),

\(1 \le id^{cont}_{jk} \le 10^9\),

each container has a unique identifier,

\(1 \le t \le 2 \cdot 10^7\),

\(-1 \le e_j \le 2.4 \cdot 10^4\),

\(1 \le \sum e_j \le 2.4\cdot 10^4\).

\(1 \le cnt_j \le 20\),

Output constraints

\(1 \le a_j \le 3 \cdot 10^7\),

\(\sum a_j \le 3 \cdot 10^7\),

\(1 \le id^{vm}_{jk} \le 10^9\),

each VM should have a unique identifier,

\(1 \le type^{vm}_{jk} \le m\).

Interaction example

Scoring

If on any time step your solution performs an invalid action, violates one of the output constraints, or fails to allocate one of the containers, it is considered to be incorrect and for such a test case you receive 0 points. Otherwise, your score is calculated as follows:

\[score = \left\lfloor \frac{TC \cdot BP}{RC + DC \cdot 10} \cdot 10^7 \right\rfloor\]

Where:

• TC is the total number of CPU time units in all container requests:

  \[TC = \sum (shutdown_{jk} - alloc_{jk}) \cdot cpu^{cont}_{jk}\]

  Where \(shutdown_{jk}\) and \(alloc_{jk}\) are the time units of container shutdown and allocation to vm respectively. If the container didn’t shut down then \(shutdown_{jk} = t + 1\) for such container.

• BP is the best possible price per CPU between all VM types:

  \[BP = min \frac{price_i \cdot 10^{-4}}{cpu_i}\]

• \(RC\) is the Resource Reservation Cost, which is the total cost of running all the virtual machines. Suppose that in total you started \(v\) VMs, \(s\)-th of them was launched at time step \(VM^{start}_s\), stopped at time step \(VM^{end}_s\) (if you didn’t stop a VM then \(VM^{end}_s\) = \(t + 1\)) and has type \(VM^{type}_s\). Then the Resource Reservation Cost equals:

  \[RC = \sum_{s = 1}^{v} (\mathit{VM}^{\mathit{end}}_s - \mathit{VM}^{\mathit{start}}_s) \cdot \mathit{price}_{\mathit{VM}^{\mathit{type}}_s} \cdot 10^{-4}\]

• \(DC\) is the Container Launch Delay Cost. Suppose that in total there were \(c\) container requests, \(f\)-th of them appeared at time step \(C^{start}_f\), and was allocated to a VM at the time step \(C^{alloc}_f\). Then the Container Launch Delay Cost equals:

  \[DC = \sum_{f = 1}^{c} (1.1 ^ {(C^{\mathit{alloc}}_f - C^{\mathit{start}}_f)} - 1)\]

Submissions

• The execution time limit is 10 seconds per test case, and the memory limit is 1024 mebibytes.

• The code size limit is 64 kibibytes.

• The compilation time limit is 1 minute.

• There are 20 provisional test cases. Your submissions will be evaluated on the provisional set during the submission phase.

• You can submit your code once every 30 minutes, and you will get feedback with your score for each of the provisional tests.

• There will be 200 test cases in the final testing after the submission phase is over. Please note that provisional tests are not included in the final testing. The final results will be announced in one week.

Quick start

Check the sample solution, which implements a very simple algorithm: for each container request find a VM type that can host this container with minimal price, launch a VM with this time, wait for it to warm up and then host the container on this VM. After container shut down event, shut down the VM for this container as well.

• C++

• Python

• C#

Local testing

You have access to the ganerator, checker and scorer, as well as a tool for local testing of your solution. All of them are implemented using Algotester Library and Algotester Generator Library. You can download the source codes of both libraries using the following links: algotester.h, algotester_generator.h. Both files should be places into the same directory as problem source codes.

Please note that the generator, checker and scorer provided to you are actually used to score your solutions on the Algotester website. You can use the source codes to clarify any questions that you have about the test cases, scoring, or the interaction protocol.

All test cases, including provisional and final sets, are generated by the generator. You can use the generator to create tests for local testing by using a few simple steps:

1. Save the generator source code to a file named generator.cpp

2. Compile the source code:

   g++ generator.cpp -O2 -o generator

3. Generate a test case

   ./generator <seed>

   This will print a test case for a specific seed to standard output.

The purpose of the checker in this problem is to read the test input data and interact with your solution: provide it with test data and read your solution’s output. The checker also checks your solution for validity: it will print an error message to stdout if your solution is incorrect on a given test case. If the stdout of the checker is empty, this means that your solution is correct on the current test case.

The scorer reads the test case input data as well as an interaction log created by the checker and scores your solution. Please note that the scorer assumes that the solution provided correct outputs for the test case, i.e. the checker did not print anything into stdout.

The tool for local testing automates the process of managing the solution, checker, scorer and generator. In order to use the local testing tool, follow these steps:

1. Save the interactor source code to a file named interactor.py

2. Save the checker source code to a file named checker.cpp

3. Save the scorer source code to a file named scorer.cpp

4. Save the generator source code to a file named generator.cpp

5. Compile the checker, scorer and generator source codes:

   g++ checker.cpp   -O2 -o checker
   g++ scorer.cpp    -O2 -o scorer
   g++ generator.cpp -O2 -o generator

6. Prepare your solution for execution. (Compile the code for compiled languages (C++, Java, C#). Do nothing for interpreted languages (Python, Node).

7. Write down the command for the solution execution. (For example: C++ - "./solution", Python - "python solution.py", Java - "java solution.class".)

8. Pass the command and the path to the input file to the interactor. Use the "--help" command to find out what the tool can do.

   python interactor.py --solution "./solution" --test_file "in.txt"
   python interactor.py --solution "python solution.py" --test_file "in.txt" --seed 47
   python interactor.py --help

9. The interactor will generate the test (in case that seed is specified), launch your solution with the checker, and then, if checker found no errors in your solution, launch scorer to calculate your score for the test. The interactor prints a detailed log of the process to stdout.