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:
- each digit and each whitespace counts as a single byte;
- each newline also counts as a single byte;
- the newline at the end is assumed even if it is not present.
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
| Name |
|---|