On 26 November 2017 at 10:30 GMT, we'll run the online contest for the 2017-2018 North-Western Europe Regional Contest (NWERC). This year the live contest is held overlooking the idyllic city of Bath, United Kingdom.
The competition is 5 hours long. You can register for the online contest here:
https://open.kattis.com/contests/nwerc17open
After the online contest, solution sketches and the problem archives will become available for download on the official website. A couple of days later all of the problems will appear in the Codeforces Gym.
Update: contest now available in the Gym at http://codeforces.com/gym/101623. Strong teams should find it sufficiently challenging.
How was Problem A — Ascending Photo supposed to be solved?
There are slides here: http://www.nwerc.eu/news/nwerc2017slides.pdf
Summary: you can make an O(N^2) DP with O(N) items based on who with height H you put first in the final list. Each has O(N) transitions. Then you can optimise it by batching all the transitions for people with the same height together, since they're all very similar.
For the moment all the contest data seems to be hosted in the "news" section http://www.nwerc.eu/news
How to solve problem I — Installing Apps?
For each app we change the download size to max(di, si). Afterwards, order the apps by di - si in descending order and apply knapsack DP.
Can you explain that observation? Why it must be sorted by the difference? It does not seem that intuitive to me :'(
There are many such problems that can be solved by two steps:
1) Assume we know the optimal subset S of items (apps) that we should take (install). In what order is it always possible to take (install) those items (apps) without violating any constraints?
2) Sort all items in the found order and then apply knapsack DP.
Step 2) is usually trivial. The hard part is to come up with a correct order in step 1) and can usually be proven with an exchange argument:
Let us consider any valid order and consider any two adjacent apps (da, sa) and (db, sb) with da - sa ≤ db - sb. We will prove that after swapping those two apps the order will still be valid (b will be installed before a after swapping). Let X be the free space of the cell phone before installing app number a. Since the order is valid, we know that da ≤ X and sa + db ≤ X. After swapping a and b (elements before a and elements after b aren't affected by this swapping) we must only show that: db ≤ X and sb + da ≤ X.
So for any subset of apps for which we know that there exists an ordering to install them, we can always apply the ordering di - si (descending).
Still not sure how this db - sb ≥ da - sa came out of a sudden.
Essentially if you are going to install two apps with pre-install sizes A1 and B1, and post-install sizes A2 and B2, the total amount of space consumed by them afterwards will always be A2+B2.
However, they will have intermediate steps during installation where app A takes up A1 space, and then app B takes up A2+B1 space to (since A is already installed by this point).
We want to make sure that A and B are chosen so as to make sure the maximum intermediate size, which will be A2+B1 assuming that A1>=A2 and B1>=B2 (if not, you should adjust the inputs so that A1=max(A1,A2) and B1=max(B1,B2)), is decreasing as space becomes tighter.
So, we want to choose an assignment/ordering of A and B such that A1+B2 > B1+A2. You can rearrange this to get A1-A2 > B1-B2, which is why we sort by that.
Great, thanks!
This part was crucial.
Usually this kind of problem is easily approachable when we think it as a "scheduling" instance : Suppose I have a list of homework with deadline di and time ti. Like most problems in this kind, it's optimal to do in the ascending order of deadline (earliest deadline first).
Now, when we let deadline C - di + si and time si, then we can see that this is a scheduling problem.
Spent couple of hours reading the proof (in Russian) of this "scheduling" problem on and understood why it is so. Quite intuitive now! Thanks for such observation.
Why I see the length is 4 hours in Gym instead of 5?
Somebody with edit rights vandalised the contest: they changed the length from 300 to 240, set a start time where I hadn't set one, and removed 3 of the problems. This is not intentional and I did not do this.
Messaged MikeMirzayanov about it just under an hour ago about rolling back. No response yet.
I've removed the contest from the public list until there's a response from MikeMirzayanov about fixing the vandalism.
Some access controls to stop people doing this would be really nice -- I thought Coach mode was supposed to be some elite thing that was only given to trustworthy users.
I also encountered vandals but they just changed the name and start time, so that was not harmful.
I think contests should not be editable by anyone except author, and maybe except users with such privileges granted by the author. Coach rights should allow creating new contests and viewing solutions and tests in others' contests.
If you still want to modify a contest as these vandals did, you can create a mashup with your own set of problems and your own contest duration.
Any updates on the contest's status?
MikeMirzayanov said 8th December he'd look into reverting it and also adding something like the ideas dalex wrote in another comment. Hopefully it's back soon.
If you want to try the problems right now you can get the original contest archives from http://nwerc.eu/news or you can find them on https://open.kattis.com/contests/nwerc17open