This is an optimization problem. The optimal solution for each test is not known to the jury, and your score for each test will be determined as described below.
The Beutsche Dahn (BD) railway network has always been praised for its... unique approach to punctuality. Specifically, every passenger who has ever managed to board a train has eventually reached their destination. But now the future is upon us — the year is $$$1879$$$, and Beutsche Dahn has just been acquired by White Tree Capital (WTC). They intend to use the railroads to relocate their tradesmen to strike urgent deals, so efficiency is extremely important.
As the newly appointed Efficiency Manager for BD at WTC, your job is to manage the entire train fleet according to exact demand. Since you have the complete list of tradesmen and their appearance times at stations in advance, you can precompute a master routing plan to get every tradesman to their destination as fast as humanly possible, while avoiding train collisions (see below).
Formally, you must minimize:
Where:
- $$$N$$$ is the total number of tradesmen;
- $$$T_{\text{appearance}, i}$$$ is the time tick at which the $$$i$$$-th tradesman appears on the platform (provided in the input);
- $$$T_{\text{arrival}, i}$$$ is the time tick at which the $$$i$$$-th tradesman is dropped off at their destination city $$$v_i$$$;
- $$$P_i$$$ is the penalty for additional train rides (see below).
Now, we will explain how the entire process is emulated and how arrival times are calculated.
The time is split into ticks, starting with tick $$$1$$$. Each tick is processed in the following sequence:
- Tradesmen Appearance: At tick $$$t$$$, all tradesmen with $$$t_i = t$$$ appear at their starting city $$$u_i$$$.
- Loading/Unloading: The trains perform pick and drop actions in the order provided in the output. A train and a tradesman must be in the same city for an action to be valid. Each train cannot exceed its maximum capacity $$$C$$$. If the tradesman arrives at their destination city, they disappear.
- Movement: Each train $$$j$$$ moves from its current city $$$\text{pos}_j$$$ to the destination city $$$\text{dest}_j$$$ specified in the output. This is only valid if a rail track $$$(\text{pos}_j, \text{dest}_j)$$$ exists. At the beginning of the next tick, the train is considered to be in $$$\text{dest}_j$$$. To avoid train collisions, two trains cannot use the same rail track during the same movement phase, regardless of whether they are moving in the same or in different directions.
Note on transfers: a tradesman does not have to reach their destination in a single ride. They may be dropped off at an intermediate city and picked up by another train. This can even happen within the same tick, provided that the commands are ordered correctly: the drop action must appear before the corresponding pick action in your output. However, due to travel fatigue, a penalty is incurred when multiple train rides are involved. More specifically:
- If a tradesman reaches their destination in one train ride, $$$P_i = 1$$$.
- If a tradesman reaches their destination in two train rides, $$$P_i = 1.05$$$.
- If a tradesman reaches their destination in three train rides, $$$P_i = 1.2$$$.
- If a tradesman reaches their destination in four train rides, $$$P_i = 1.5$$$.
- No tradesman will accept a plan involving more than four train rides.
You are given a zip archive "problem-a-inputs.zip" with $$$8$$$ tests: 01, 02, $$$\ldots$$$, 08.
Each test describes the rail network, the train fleet, and the information about tradesmen. All indices are $$$1$$$-based.
The first line contains two integers $$$V$$$ and $$$E$$$ — the number of cities and undirected rail tracks. Each of the next $$$E$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \leq V, u \neq v$$$) — an undirected rail track between cities numbered $$$u$$$ and $$$v$$$. It is guaranteed that all rail tracks are unique; there is no rail track that goes from a city to itself, and any city is reachable from any other city by following a sequence of rail tracks.
The next line contains an integer $$$T$$$ — the number of trains at your disposal.
The next line contains $$$T$$$ integers between $$$1$$$ and $$$V$$$ — the initial city of each train.
The next line contains an integer $$$C$$$ — the maximum capacity of each train.
The next line contains an integer $$$N$$$ — the total number of tradesmen for the scenario.
Each of the next $$$N$$$ lines contains three integers $$$u_i, v_i, t_i$$$ ($$$1 \le u_i, v_i \leq V$$$, $$$u_i \ne v_i$$$, $$$1 \le t_i \le 10^5$$$) — the starting city, the destination city, and appearance time for the $$$i$$$-th tradesman. Additionally, the tradesmen are ordered by their appearance times: for every $$$i \lt N$$$, it is guaranteed that $$$t_{i} \leq t_{i+1}$$$.
Submit a zip archive with files 01.out, 02.out, $$$\ldots$$$, 08.out. Some of the files may be missing.
Each file should be formatted as follows.
The first line should contain an integer $$$S$$$ — the total number of ticks in your plan. This number should not exceed $$$10^6$$$.
For each tick $$$s = 1, 2, \ldots, S$$$, output should contain the following:
- An integer $$$K_s$$$ — the number of pick-up and drop-off actions performed at the start of this tick.
- $$$K_s$$$ lines, each containing one of the following commands:
- pick <train_id> <tradesman_id>
- drop <train_id> <tradesman_id>
- An integer $$$M_s$$$ — the number of trains performing a move action at the end of this tick.
- $$$M_s$$$ lines, each containing two integers train_id and city_id — the moving train and its next city. All identifiers of the moving trains during one tick must be distinct, and for each of them, the city it is going to must be reachable via a single rail track.
All indices are $$$1$$$-based: $$$1 \le \mathtt{train\_id} \le T$$$, $$$1 \le \mathtt{tradesman\_id} \le N$$$, $$$1 \le \mathtt{city\_id} \le V$$$.
Additionally, to maintain manageable output sizes, the total number of move operations performed, $$$\sum\limits_{s=1}^{S} M_s$$$, must not exceed $$$2 \cdot 10^6$$$. We expect that most solutions would satisfy this restriction without additional optimization.
Your number of points is calculated using the formula
Your final score for the test is calculated as follows:
- If the output is not properly formatted or is inconsistent, e.g.:
- a tradesman does not reach their target destination,
- a train tries to pick up a tradesman who has already reached their destination, or is not present in that city,
- a train uses a rail track that is already in use during the current tick,
- a train moves to a city that is not accessible from its current city,
- Otherwise, it will be $$$100$$$ times the ratio of the lowest number of points among all participants for this test to the number of points for your output: $$$100 \cdot \frac{\mathtt{best\_points}}{\mathtt{your\_points}}$$$.
Note that the scoreboard will consider your best score for each test among all your submissions.
3 2 1 2 2 3 2 1 1 2 3 1 2 1 1 3 1 1 2 1
3 3 pick 1 1 pick 1 2 pick 2 3 1 1 2 1 drop 1 1 2 1 3 2 2 2 drop 1 2 drop 2 3 0
The sample test illustrates the input and output formats. This test is not part of the graded test set.
In this sample, three cities are connected by two rail tracks in a line. There are two trains in city $$$1$$$, each capable of holding $$$2$$$ tradesmen. Three tradesmen appear in city $$$1$$$ at tick $$$1$$$: tradesmen $$$1$$$ and $$$3$$$ need to get to city $$$2$$$, while tradesman $$$2$$$ needs to get to city $$$3$$$.
In the sample output:
- During tick $$$1$$$, tradesmen $$$1$$$ and $$$2$$$ board train $$$1$$$, and tradesman $$$3$$$ boards train $$$2$$$. Then, train $$$1$$$ moves to city $$$2$$$, while train $$$2$$$ cannot move since the track is already in use.
- During tick $$$2$$$, tradesman $$$1$$$ gets off the train and arrives. Then, train $$$1$$$ moves to city $$$3$$$, while train $$$2$$$ moves to city $$$2$$$.
- During tick $$$3$$$, tradesmen $$$2$$$ and $$$3$$$ both get off their respective trains and arrive.
Thus, the three tradesmen contribute $$$1$$$, $$$2$$$, and $$$2$$$ to the sum under the square root. Hence, the number of points is
Problem by Alber Blanc
This is an optimization problem. The optimal solution for each test is not known to the jury, and your score for each test will be determined as described below.
The year is $$$6202$$$, and the world-famous artist Hcivelam is going through her retrospective phase. She has created a digital art piece that is hard for her contemporaries to explain, but it essentially looks like an ancient monochrome monitor. It is a play of space and negative space, a representation of the dual nature of everything: a grid of size $$$n \times n$$$ consisting of black and white pixels.
The piece is almost finished, but Hcivelam cannot complete it: she has lost her artistic tool, the cursor, somewhere on her black-and-white digital canvas. She does not know the cursor's position, but she knows for sure that it is currently located on a white pixel (if it were on a black pixel initially, she would already see it).
She can press the arrow keys on her keyboard to move the cursor: 'U' (up), 'D' (down), 'L' (left), and 'R' (right).
The cursor behaves as follows:
- Movement: When you press a key, the cursor moves by one pixel in the corresponding direction.
- Borders: If the cursor attempts to move outside the screen boundaries, it hits the edge and stays in its current position.
- Visibility: If the cursor lands on a black pixel at any point, it immediately becomes visible, and you find it!
Your task is to help Hcivelam find a sequence of moves, as short as possible, such that regardless of where the cursor started, as long as it started on a white pixel, it is guaranteed to visit a black pixel at least once. The length of your sequence must not exceed $$$5000$$$.
You are given a zip archive, "problem-b-inputs.zip", containing $$$8$$$ tests in the form of PNG images: 01.png, 02.png, $$$\ldots$$$, 08.png.
Each test describes the art-piece grid in standard grayscale PNG format. The size of the grid is $$$n \times n$$$ ($$$495 \le n \le 500$$$). Each pixel is either black or white, and there is at least one black pixel and at least one white pixel.
Submit a zip archive with files 01.out, 02.out, $$$\ldots$$$, 08.out. Some of the files may be missing.
Each file should contain a single string consisting of the characters 'U', 'D', 'L', and 'R' — a sequence of moves that guarantees the cursor becomes visible.
Your number of points is the length of the output string.
Your final score for the test is calculated as follows:
- If the sequence of moves does not guarantee the cursor becomes visible, your score is $$$0$$$.
- Otherwise, it will be $$$100$$$ times the square of the ratio of the lowest number of points among all participants for this test to the number of points for your output: $$$100 \cdot \left( \frac{\mathtt{best\_points}}{\mathtt{your\_points}} \right)^2$$$.
Note that the scoreboard will consider your best score for each test among all your submissions.
We also provide two small sample grids in the zip archive "problem-b-samples.zip".
In the first sample, the grid is $$$2 \times 2$$$. In the explanations below, coordinates are given as $$$(\operatorname{row}, \operatorname{column})$$$.
The only black pixel is at $$$(2, 2)$$$. The cursor could be at $$$(1, 1)$$$, $$$(1, 2)$$$, or $$$(2, 1)$$$:
The sequence 'RD' guarantees that we find the cursor regardless of its starting position:
- After moving 'R' (right):
- $$$(1, 1) \to (1, 2)$$$
- $$$(1, 2) \to (1, 2)$$$ (hits the border)
- $$$(2, 1) \to (2, 2)$$$ (FOUND)
- After moving 'D' (down):
- $$$(1, 2) \to (2, 2)$$$ (FOUND)
Thus, one possible answer is:
RD
In the second sample, the grid is $$$4 \times 4$$$:
One possible answer is:
LLR
Note that the actual sample images have sizes $$$2 \times 2$$$ and $$$4 \times 4$$$, respectively. The larger illustrations above include thin lines between pixels for clarity only.
Problem by Recraft
This is an interactive problem with partial scoring.
You are only allowed to make one submission every 5 minutes, so you are encouraged to test your solution locally before submitting.
Cloudius is an extremely innovative company that builds super-innovative data centers. In fact, the level of innovation is so high that it can rebuild an entire data center in seconds. Every so often, a data center is spontaneously rebuilt to upgrade its architecture, enhance security, and keep the less innovative competition on its toes.
There's just one tiny issue: servers in a data center often break down, and fixer robots keep getting lost in the labyrinth of regenerated data centers. You are tasked with creating a new algorithm for these poor things.
In each test, a hidden data center layout is generated by the official generator (provided in "problem-c-generator.zip"). The layout is an $$$N \times N$$$ grid with $$$N = 125$$$ and contains a repair point that the fixer robot needs to find. Some cells contain server racks, and some are empty. The repair point can only be located in an empty cell.
You may make at most $$$T = 10000$$$ queries. Each query is represented by a pair of integers $$$(r, c)$$$. For a query $$$(r, c)$$$, the interactor responds with:
- $$$-1$$$ if $$$(r, c)$$$ is a server rack.
- $$$0$$$ if $$$(r, c)$$$ currently contains the repair point. Your score increases by $$$1$$$, and then the repair point moves to a uniformly random empty cell. Any empty cell, including the current one, may be chosen.
- Otherwise, the length of the shortest path from $$$(r, c)$$$ to the repair point using only empty cells.
Your goal is to find the repair point as many times as possible in $$$T$$$ queries.
We have attached the generator in "problem-c-generator.zip" which uses a seed to produce the data center layout for a test. The official test set contains $$$50$$$ tests generated from random seeds fixed before the contest. Separately, we have attached "problem-c-example-tests.zip" with $$$10$$$ example tests generated as generator <seed> for seeds $$$1$$$ through $$$10$$$, so you can inspect them directly instead of generating them locally.
The repair point's positions are randomized independently for each run, so resubmitting the same solution may yield a different score.
At the start, your program should read two integers:
- $$$N$$$ — the size of the data center layout,
- $$$T$$$ — the number of allowed queries.
Then, repeat $$$T$$$ times:
- print a query "r c" ($$$1 \le r, c \le N$$$),
- flush the output,
- read the interactor response.
If the response is $$$0$$$, the repair point is found and immediately moves to a uniformly random empty cell.
Your number of points for a test is calculated as follows:
- If your program violates the interaction protocol or does not terminate correctly (e.g., exceeds the time or memory limit or produces a runtime error), your number of points for the test is $$$0$$$.
- Otherwise, it is the number of times the repair point is found during the interaction process.
Your total number of points is the sum of your number of points across all $$$50$$$ tests.
Your final score is calculated as $$$800$$$ times the ratio of your total number of points to the highest total number of points among all participants: $$$800 \cdot \frac{\mathtt{your\_total\_points}}{\mathtt{best\_total\_points}}$$$.
Note that the scoreboard will consider your best score among all your submissions.
Problem by Nebius