It's year $$$5202$$$ and the world famous artist Nonnel is going through her technostrawberry phase. Her canvas is a gigantic white field and her brush is a robotic arm. Nonnel spent a long time crafting it and perfecting the design. She recrafted, tested, recrafted again and after much recrafting the design is complete.
This arm consists of $$$k$$$ ($$$k \in \{2, 3\}$$$) sections, each with specified lengths $$$l_i$$$. The first section is anchored at the origin of the plane, which is the point $$$(0, 0)$$$, and it can rotate around this point. Its angle of position is defined relative to the positive $$$OX$$$-axis. Each subsequent section begins at the end of the previous section and can rotate around that joint. The angle of position for each following section is defined relative to the direction of the preceding section. Sections can coincide or pass through each other.
The position angles of the arm's sections determine its configuration. A position angle is defined as a real number within the range $$$[0, 2\pi)$$$. When the arm is deployed on a field, all initial position angles are set to zero, meaning that the joints are positioned at the coordinates $$$(0, 0)$$$, $$$(l_1, 0)$$$, $$$(l_1 + l_2, 0)$$$, and so forth. The end point of the final section is located at $$$(l_1+l_2+\dots+l_k, 0)$$$.
The arm can transition from one configuration to another. The cost of a transition is determined by the maximum difference between the current and next position angles across all segments. The difference between two angles $$$x$$$ and $$$y$$$ is defined as the minimum of the clockwise and counter-clockwise rotations: $$$\mathtt{dist}(x, y) = \min(|x - y|, 2\pi - |x - y|)$$$.
Consider an example. Suppose the arm has two segments, and their current position angles are $$$\frac{\pi}{3}$$$ and $$$\frac{\pi}{4}$$$, respectively. If the next position angles are $$$\frac{\pi}{4}$$$ and $$$2 \pi - \frac{\pi}{4}$$$, the total cost would be $$$\max(\frac{\pi}{12}, \frac{\pi}{2}) = \frac{\pi}{2}$$$.
The arm paints, and it only paints strawberries. It's an artistic choice, don't question it.
Nonnel wants to produce a series of gigantic strawberry fields. Each strawberry is identified by a pair of coordinates. Your task is to specify the order in which to paint the strawberries and to provide the corresponding arm configurations. The end of the arm's last segment should be almost aligned with the coordinates of the target strawberry: the absolute difference for each coordinate must not exceed $$$10^{-6}$$$. The arm will receive these configurations and will transition between them in the specified order, starting from the initial position.
In her work Nonnel wants to explore the concept of efficiency, so each field should be painted with minimal total transition cost.
You are given a zip-archive "problem-a-inputs.zip" with $$$12$$$ tests: 01, 02, $$$\ldots$$$, 12.
The first line of each test contains the number of sections $$$k$$$ of the robotic arm ($$$k \in \{2, 3\}$$$). The second line contains $$$k$$$ real numbers $$$l_1, l_2, \ldots, l_k$$$ — the lengths of the sections. The third line contains $$$n$$$ — the number of strawberries to paint. Each of the next $$$n$$$ lines contain two real numbers — the coordinates of the strawberries.
It is guaranteed that for each strawberry there exists a configuration that paints it.
Here is a short description of tests' parameters:
| Test | k | n |
| 01 | 2 | 8 |
| 02 | 2 | 100 |
| 03 | 2 | 100 |
| 04 | 2 | 15 |
| 05 | 2 | 100 |
| 06 | 2 | 100 |
| 07 | 2 | 100 |
| 08 | 2 | 1000 |
| 09 | 3 | 300 |
| 10 | 3 | 16 |
| 11 | 3 | 660 |
| 12 | 3 | 150 |
As an answer, you should submit a zip-archive with files 01.out, 02.out, $$$\ldots$$$, 12.out. Some of the files may be missing.
Each of these files should contain $$$n$$$ lines. Each line should have the label of the painted strawberry (they are labeled from $$$1$$$ to $$$n$$$ in the order of input) and the configuration represented with $$$k$$$ real numbers: the position angles of the arm sections in the respective order. The angles should be in the range $$$[0, 2\pi)$$$.
Let the configuration $$$i$$$ in the output be represented as an array of angles $$$c_i[\cdot]$$$. And let the initial position be $$$c_0 = [0, \ldots, 0]$$$.
The checker iterates through the configurations one by one. Suppose the next configuration is $$$c_i$$$. At first, the checker verifies that the configuration indeed paints the strawberry in the target position. For that, it calculates the coordinates of joints one by one and compares the coordinates of the end of the last segment with the coordinates of the strawberry. Then, it calculates the cost of that move: $$$\max_{j = 1}^k \mathtt{dist}(c_i[j], c_{i - 1}[j])$$$. And adds it to the total number of points.
Your final score for the test is calculated as follows:
Note that the scoreboard will consider at the end your best score for each test among all your submissions.
Below is a visualization of the first test file 01.
 |  |
| The initial position of the mechanical arm. | Strawberry #3 is painted. |
Problem by Recraft
As some of you may know, being a problemsetter is not an easy task. Coming up with a fresh idea, writing a creative problem statement and implementing the correct main solution is already quite hard. However, sometimes the real nightmare starts when it is time to create a test set. A problemsetter has to think about naive solutions, greedy solutions, slow solutions, and corner cases, and usually this is only the beginning... Ideally, a problemsetter should anticipate all the potential incorrect solutions that a participant might devise and create tests against each of them. This time, we have decided that it is time for you to get this indisputably valuable experience.
We consider a plain 0-1 knapsack problem. The inputs are: the knapsack capacity $$$W \gt 0$$$ and $$$N \ge 0$$$ items, where the $$$i$$$-th item has weight $$$w_i \gt 0$$$ and value $$$v_i \gt 0$$$. One needs to find the subset of these items such that the sum of all weights does not exceed $$$W$$$, and the sum of all values is the maximum possible. We are sure that most of you solved this problem at least once.
But this time you don't have to write a solution! Instead, we give you a solution, which looks as if it may be correct, but is expected to be too slow. Now it is your turn to be a problemsetter: you will need to create an input file that would make the solution run for as long as possible! Surely, creating a big enough file is cheap talk: you know that problems usually have some kind of constraints. But this time, they are quite relaxed. Your creativity is only limited by the file size: it should be at most 100 bytes long. You just have to submit this file to the testing system, which will run the solution on it. Of course, it should satisfy the format specified below.
For reproducibility, we do not measure the actual running time of the solution. Instead, we compute the cost, which is specific to the solution, and is believed to be roughly proportional to the running time. As you look into the solutions, you can see what these costs are, so challenge the solutions wisely!
You are provided with three progressively more complicated solutions. Their pseudocodes are given in the Notes section, and we are sure you can implement any of them in a reasonable time if you wish. We also provide these implemented in Python in "problem-b-solutions.zip". Please note that the Python implementations do not perform complete validation of the format of your files.
You should submit a zip-archive with files 01.out, 02.out, and 03.out. Some of the files can be missing. Each of the files should contain the test for the corresponding solution. Each test should follow the format below, and if it does not, it gets $$$0$$$ points.
All numbers in the file should be decimal integers.
The first line of the file contains the capacity $$$W$$$, which must be a positive integer.
Each of the following lines describes an item. Such a line contains two positive integers, $$$w_i$$$ and $$$v_i$$$, the weight and the value of the $$$i$$$-th item, separated by exactly one whitespace symbol.
For platform independence, the size of the file is validated as follows:
For example, the following input:
42
12 2
13 7
14 1
15 8
describes a knapsack with a capacity 42, and four items: $$$w_1 = 12, v_1 = 2$$$, $$$w_2 = 13, v_2 = 7$$$, $$$w_3 = 14, v_3 = 1$$$, and $$$w_4 = 15, v_4 = 8$$$.
The size of this file will be: $$$2+1=3$$$ bytes for the capacity, $$$2+1+1+1=5$$$ bytes for each item, so $$$3 + 4\cdot5 = 23$$$ bytes in total.
For each of the three outputs, scoring is done independently of others. Each solution will evaluate only the output with the corresponding name (for example, solution 2 will only evaluate file 02.out).
The number of points reported by the solution, divided (for technical reasons) by $$$10^3$$$, will be the absolute number of points for your submission, shown in the judgement protocol.
The final score will be the number of points for your output divided by the highest amount of points among all participants for this test: $$$400 \cdot \frac{\mathtt{your\_points}}{\mathtt{best\_points}}$$$. Note that the scoreboard will consider at the end your best score for test among all submissions.
For our own safety, the version of the solutions running in the testing system will stop once the cost reaches $$$10^8$$$. This is the maximum possible cost. Your local version of the program may return a higher cost, or (which we think is unlikely) will hang for too long, but in both cases the cost of the submission will be $$$10^8$$$ (and the absolute number of points will be $$$10^5$$$).
For all the pseudocodes below, the inputs are always the knapsack capacity W and the items. For an item i, i.w represents its weight, and i.v its value. Furthermore, drop means that we drop the corresponding items from the knapsack even if some items are not there. pick means that we take the corresponding items into the knapsack. Other notation should either be familiar to you, or can be easily understood.
Arrays are indexed from zero.
Pseudocode for solution 1.
function solve(W, items):
N = length(items)
bestV = 0
cost = 0
drop all items initially
function go(sw, sv, d):
cost += 1
if sv + (sum of items[i].v for i >= d) > bestV then
if d == N then
bestV = sv
save the current solution
else
if sw + items[d].w <= W then
pick items[d]
go(sw + items[d].w, sv + items[d].v, d + 1)
drop items[d]
end
go(sw, sv, d + 1)
end
end
end go
go(0, 0, 0)
return cost
end solve
Pseudocode for solution 2.
function solve(W, items):
N = length(items)
bestV = 0
cost = 0
drop all items initially
sort items by non-increasing item.v / item.w,
if equal, by non-increasing item.w
function heuristic(sw, sv, d):
rw = min(W - sw, sum of items[i].w for i >= d)
rv = bestV + 1 - sv
return items[d].v / items[d].w >= rv / rw
end heuristic
function go(sw, sv, d):
cost += 1
if d == N then
if sv > bestV then
bestV = sv
save the current solution
end
else if sv > bestV or heuristic(sw, sv, d):
if sw + items[d].w <= W then
pick items[d]
go(sw + items[d].w, sv + items[d].v, d + 1)
drop items[d]
end
go(sw, sv, d + 1)
end
end go
go(0, 0, 0)
return cost
end solve
Pseudocode for solution 3.
function solve(W, items):
sort items by non-increasing item.v / item.w,
if equal, by non-increasing item.w
pick items greedily left to right while they fit,
if all elements fit, return 0
b = the index of the item which did not fit
bw = items[b].w
bv = items[b].v
gw = sum of items[i].w for i < b
gv = sum of items[i].v for i < b
N = length(items)
bestV = gv
cost = 0
exceptions = []
for i in [b + 1; N) do
newV = gv + items[i].v
if newV > bestV and gw + items[i].w <= W then
bestV = newV
exceptions.add(items[i])
end
end
for i in [0; b):
newV = gv + items[b].v - items[i].v
if newV > bestV and gw + items[b].w - items[i].w <= W then
bestV = newV
exceptions.add(items[b], items[i])
end
end
link the items in a linked list:
items[i - 1].next = items[i] and items[i].prev = items[i - 1]
where out of bounds items are invalid
function go(sw, sv, left, right):
cost += 1
improved = false
if sw <= W then
if sv > bestV then
improved = true
bestV = sv
exceptions.clear()
end
while right is valid do
if (bestV + 1 - gv - right.v) * bw > (W - gw - right.w) * bv then
old = right
right = right.next
remove old from the linked list
continue
end
if (sv - bestV - 1) * right.w < (sw - W) * right.v then
return improved
end
if go(sw + right.w, sv + right.v, left, right.next) then
improved = true
exceptions.add(right)
end
right = right.next
end
else
while left is valid do
if (bestV + 1 - gv + left.v) * bw > (W - gw + left.w) * bv then
old = left
left = left.prev
remove old from the linked list
continue
end
if (sv - bestV - 1) * left.w < (sw - W) * left.v then
return improved
end
if go(sw - left.w, sv - left.v, left.prev, right) then
improved = true
exceptions.add(left)
end
left = left.prev
end
end
return improved
end go
go(gw, gv, items[b].prev, items[b])
for item in exceptions do
if item in knapsack:
drop item
else:
pick item
end
return cost
end solve
Midnight Cloud Computing (MCC) has asked you and your friend Grigory to prepare a problem for an upcoming programming competition. Unfortunately, you were on a business trip to Serbia and haven't had any time to contribute. Now, with just one day left before the contest, Grigory has mysteriously vanished and isn't replying to your increasingly desperate messages.
You open the problem drafts and gasp — even the problem statement is nowhere near ready! All that's there is a model solution and some input data. Looking closer, you discover that the solution is written in assembly for the JB (JunctionBoard) chip engineered by MCC. The solution file is included in the archive named "problem-c1-model.zip".
The competition is tomorrow, and your first objective is to generate model output data for Grigory's problem. It shouldn't take long — after all, you already have the model solution. Just remember: the JB chip operates modulo $$$2^{32}$$$, so your output data should also be modulo $$$2^{32}$$$.
You are given a zip archive, "problem-c1-inputs.zip" containing $$$10$$$ tests: 01, 02, $$$\ldots$$$, 10.
Each test file consists of a single line with three integers.
As your answer, submit a zip archive containing files named 01.out, 02.out, $$$\ldots$$$, 10.out. Some of the files may be missing.
Each file should contain a single integer — the result of running Grigory's code on the corresponding input. Since JB chip operates modulo $$$2^{32}$$$, your outputs should also be computed modulo $$$2^{32}$$$.
You will get 1 point for each correct output which will be transformed to the score of $$$60$$$ in the scoreboard.
Problem by JetBrains
Congratulations on picking up Grigory's work and making sure his problem is ready for the competition. Midnight Cloud Computing has been impressed by your determination and ingenuity, and has requested your help with one more task.
Once again, there's a model solution written for the JB (JunctionBoard) chip by your coworker—who mysteriously vanished while searching for Pafos Island. Her solution is included in the archive "problem-c2-model.zip".
The competition is happening today — please generate model output data for this problem as well. Once again, remember that the JB chip operates modulo $$$2^{32}$$$, so all outputs should also be computed modulo $$$2^{32}$$$.
You are given a zip archive "problem-c2-inputs.zip" with $$$10$$$ tests: 01, 02, $$$\ldots$$$, 10.
Each test file consists of a single line containing a positive integer.
As an answer, you should submit a zip archive with files 01.out, 02.out, $$$\ldots$$$, 10.out. Some of the files may be missing.
Each file should contain a single integer — the result of running the missing coworker's code on the corresponding input. JB chip operates modulo $$$2^{32}$$$, so your output should also be computed modulo $$$2^{32}$$$.
You will get 1 point for each correct output which will be transformed to the score of $$$60$$$ in the scoreboard.
Problem by JetBrains