Hi all.
This week's farm training contest will be held on 3.7 hours later. This week's writer is drazil and tester is me (dreamoon). This week's contest consists of 6 problems of difficulties (Div. 2 500-1000-1750-2500-2250-2500). We invite all who is interested to our contest. This contest will be held in our group gym. You can find the contest in our codeforces group.
Thanks!
UPD:
Hi all, Weekly Training Farm 21 has ended.
Congradulations to the winner W4yneb0t and the first runners up eddy1021, they are the only two who solved all six problems!!
Thanks to all who participated in the contest. We hope you enjoy the problems.
The editorial will be posted within a couple of days.
We wish to see you in the next week's training farm prepared by zscoder!
Auto comment: topic has been updated by dreamoon_love_AA (previous revision, new revision, compare).
I liked problem F. How to solve this? W4yneb0t eddy1021
Calculate DP[a][b][c]: the minimum number of times you deliver baggage with weight W-1, if you deliver or move only the first a items, and move b items of weight 1 and c items of weight 2 (the moved items aren't delivered, imagine you're placing them in some temporary storage).
For each b and c, look at DP[n][b][c] and place the remaining b+c items optimally: greedy works, place a 2 if it fits and a 1 otherwise. If the result is optimal, the answer is at most b+c.
O(n^3) time, O(n^2) space if you store the DP 2 levels at a time.
How to solve problem D, E and F ?
D: My approach was binary search with network flows checking feasibility (create O(n × Max_Time) vertices for every moment for each airport node, a solution exists iff a full flow can be achieved — building the flow graph can be done accordingly), but I suppose incremental on answer while adding vertices to the flow graph and findng augmenting paths also works.
E: Discretize the coordinates first, then the whole image becomes a 2n × 2n grid. Convert the segments into prefix-sum-like "events" and use these to find out where the walls are in O(n2) time. Then we can apply a floodfill to the graph to find all rooms.
F: Already described neatly above
Please share the editorial :)
dreamoon_love_AA Weekly Training Farm 22 passed. I forget. Please announce the contest
The announcement is here. These training are now always announce by me.