Hello, Codeforces!
I would like to invite you to take part in the 10th jubilee edition of the international programming marathon Deadline24. During the contest, the teams of three tackle algorithmic problems.
Registration will last until February 22 and it is possible through the form available on the website: www.deadline24.pl/register
The qualifying round will take place on Sunday, February 25. During it the registered teams will struggle to solve tasks for 5 hours and this will be verified by server. This part of the competition is carried out remotely. In the last year a record number of competitors registered for the first phase — 1950.
For the final — which lasts for 24 hours — 30 teams with the best scores obtained during the elimination will be invited. The final will take place on 7- 8 of April in Poland. This year the best teams will win: Oculus Rift, iPad and Kindle Oasis 2.
Don't forget that the registration ends on February 22! Good luck in the qualifying round :)
If you are interested in the previous years' tasks, you can find them here.
Special thanks to Mike Mirzayanov for his help in promoting the competition on CF.
How can we register a team, not only one member ?
To create your own team, you must log in on www.deadline24.pl and go to “My menu” -> “Create your team”.
To join an existing team, you must go to “My menu” -> “Join an existing team”. Then, choose a team from the list and click the button “Join team”.
Each participant must register himself and choose a team or create his own. Team captain (a person who created a team) can remove team members but cannot add anyone.
Thank you !
Anybody still looking for a team member?
Any special solutions except manual answer build for B?
What was the expected author solution for it?
Formulated integer / linear program : find the flow between K sources and sinks, with additional exclusion constraint (each node could be used in at most one flow) and defined the height of each node with the constraint of decreasing on the flow path: (|hi - hj| < = 1 × fij + ∞ × (1 - fij)). Target is to maximize the total height of all sources. Used black box solver, solved first 2 cases, but probably given more time could have solved more.
P.S. Pretty sure could have done more with the following heuristic: find any flow between K sources and sinks (that could possibly include closed loops), then merge together loops and paths, until only paths remain.
Which black box solver did you use?
I used Gurobi. Pretty sure CPLEX would have worked too.
I solved it up to B4 (B5 after the contest) by CSP Solver(Sugar+minisat). Applied usual Flow Free solutions, the solver outputs result which consists of valid paths + extra cycles. However extra cycles can be merged easily with valid paths in the most cases. I did it by hand. I don't think this method can solve all the cases in time.
Lol. 32nd place, alone after I woke up 20 minutes late. Now I only need to hope 2 teams can't participate.
...and it seems like I can't participate in the finals anyway. On the other hand, at least I'll be able to compete awake in Yandex R3.
Sorry bro downvote for you!
My solution for C (4th place, 459.28 pts):
We always start in (0, 0). Let's split a grid into rectangles 4x4 and 4x5 (we split each side into segments of size 4 and 5, this naturally produces a splitting of the entire grid). Now we move from one rectangle to another in Z-order:
For each rectangle, there are several entry points and several exit points. To find optimal path inside the rectangle we run a O(2m·m2) dp, and we need one more linear dp to combine answers for all rectangles. The value of the dp is simply the largest number which is possible to achieve at the moment (this is not optimal, but simple).
Any other approaches?
For B, we tried searching for existing solvers (the problem resembles a game 'Flow Free'), but, unfortunately, each of them found suitable paths but didn't cover the entire grid.
So do you know how to solve the problem when you don't have to cover the whole grid?
No. We have examined a couple of solvers (3000 lines of C code, I wish I could unsee it), they use some heuristics to solve the game for 15x15 board. We strongly suspect that the problem is NP-complete even if you don't have to cover the whole grid.
Tests were quite special, with many pairs having start and end close to each other, so it was easy to solve it without the "cover the whole grid" condition. I sorted pairs by Manhattan distance and greedily chose any shortest path for every pair. This instantly solved 90% of tests (e.g. it solved everything in input 4). Manually fixing remaining tests is doable in maybe half an hour — it's just about telling your program to draw one or two paths differently. The hard part is to extend those paths to cover everything, sometimes slightly changing initially chosen paths to make it possible (e.g. all connected components of empty cells must have even size). I think the optimal approach is to write a program that in random order extends paths by 2 cells. Run that program many times, choose the best solution (with fewest empty cells) and fix it by hand. Or maybe it's still too hard, I don't know.
In B I found that there are many pairs (start, destination) that are adjacent. Therefore they can be assigned as a path and we use them only if we need and cover as much as possible. Probably that was intended by organisers to make participants write greedy covering.
I got 10th place on E with the following algorithm:
What I like Deadline24 for, is such simple algorithms getting top places.
I did the same with one small optimization: before printing agency hires, for each agency I merge time segments from all materials and print only the needed time intervals. This got 4th place in this task.
Simple algorithms getting top places is what I dislike most in such kind of contests. I'd rather see a simple task but with a clever algorithm needed. Where is the fun if all you need to do is implementation of input reading?
How to solve the problem B?