### Errichto's blog

By Errichto, 16 months ago, ,

Hi everybody.

Deadline24 is an international programming marathon, organized continually since 2009 by Future Processing. During the contest, the teams of three tackle algorithmic problems.

The marathon is composed of two phases. The qualifying round starts on March 12. For 5 clock hours, the teams will be solving tasks and generating responses assessed by the verification server. This stage of the competition is remote. Then, the best teams of the qualifying round will meet at the 24-hour finals held on April 22-23, 2017, in Katowice (Poland).

The teams can sign up until March 9, 2017 (23.59 CET). Registration is available on the contest website www.deadline24.pl.

You can get familiar with the type and difficulty level of the tasks in the Qualifying round by competing in the GYM contest on this Thursday and will last 5 hours (check your timezone here). It will be a replay contest of the Qualifying Round 2016. The contest will appear in Codeforces GYM soon. Because of technical limitations, the scoring and final ranking system of that replay contest is not identical to the one used during the qualifying round — don't forget to visit the contest website (www.deadline24.pl) to read full rules (e.g. submitting time matters and you submit output files instead of codes).

I'm not one of organizers but I competed in some of previous editions and I enjoyed finals a lot. Now I was asked to help a bit with the GYM replay. On behalf of the organizers, I want to thank Mike Mirzayanov for his help in promoting the competition on CF.

Don't forget that the registration ends on Thursday! Good luck in the qualifying round.

UPD: the GYM contest will start with the delay of 30 minutes. Sorry for the inconvenience.

•
• +161
•

 » 16 months ago, # | ← Rev. 2 →   +20 Is it only me clicking on the link www.deadline24.pl will direct to this blog?UPD Missing // after a href=" should be the reason? It interprets as relative URL I think.
•  » » 16 months ago, # ^ | ← Rev. 3 →   +7 Clicking on the link redirects me to the blog too. I used [www.deadline24.pl](www.deadline24.pl) to create a link — does anybody understand the issue?EDIT: thanks percywtc and AlexDmitriev, slashes helped.
•  » » » 16 months ago, # ^ | ← Rev. 4 →   +20 try [www.deadline24.pl](http://www.deadline24.pl)otherwise it's relative link which goes to codeforces.com/blog/entry/www.deadline24.pl which gives an error and redirects to last visited CF page
•  » » » 16 months ago, # ^ | ← Rev. 3 →   +20 Should be [www.deadline24.pl](//www.deadline24.pl) ?
 » 16 months ago, # |   +3 How the marathon problems are going to be scored in gym?
•  » » 16 months ago, # ^ |   0 Polygon allows for non-binary scoring, but it's impossible to use the score of the best team to compute others' scores. Either the best result from the last year or the best theoretically possible result (e.g. MST in TSP) will be used as a relative score — everything better gets 100 points, everything worse is scored linearly.
 » 16 months ago, # |   +3 What's the point of closing the registration 3 days before the qualification round?
•  » » 16 months ago, # ^ |   +11 We (I mean organizers) need those days to prepare the whole environment for the qualifying round.
 » 16 months ago, # | ← Rev. 2 →   0 I think this is Deadline24 2017 — Qualifying Round and GYM replay of previous edition ? is it bood?
 » 16 months ago, # |   +5 Last time I've checked, I saw it overlaps with AtCoder Grand contest 11. I guess it doesn't matter that much. Maybe they could try to move it one hour later, but as there was no post related to any of the contests, I didn't know how to inform anyone about this clash.
 » 16 months ago, # |   0 Congrats on becoming Top Contributor
•  » » 16 months ago, # ^ |   +40 I'm used to it but thanks.
 » 16 months ago, # |   0 How will the expense of travel be covered, in the rare case my team is qualified?
•  » » 16 months ago, # ^ |   +116 They won't be covered. On the bright side, you will be able to eat a lot of food and talk with Swistakk (if he will advance to the finals too).
•  » » » 15 months ago, # ^ |   +25 Will I?
•  » » » » 15 months ago, # ^ |   +33 Good point, not really ;p
 » 16 months ago, # |   0 What is the max number of people a team can have?
•  » » 16 months ago, # ^ |   0 3
•  » » » 16 months ago, # ^ |   0 Thanks!
 » 16 months ago, # | ← Rev. 2 →   +5 https://www.deadline24.pl/assets/regulations/QualifyingRoundRules.pdfIn the 2.9 there is a point calculation, but I didn't find previous years tasks r and b value. Anybody knows where can I find it, or typically what are these values? Thank you.
•  » » 16 months ago, # ^ |   0 We have added those missing values to the package with last year's tasks. You can find them under dl24-elim-2016.zip/tasks/scoring.pdf
•  » » » 16 months ago, # ^ |   0 Thank you!
 » 16 months ago, # |   +38 For codeforces community you have even wrote a blog about deadline, but when I was asking you about when qualification round is and to make sure that we wouldn't miss it, then you weren't so eager to even check it. #bestteammate
•  » » 16 months ago, # ^ |   +24 "I was too lazy to check the date, I asked you to do it, and you were too lazy as well."
•  » » » 16 months ago, # ^ |   +32 Do you want to argue one more time, about who definitely isn't "the responsible one"?
•  » » » » 16 months ago, # ^ |   -10 :D
•  » » 16 months ago, # ^ |   +110 Because contribution is more important than teammates.
 » 16 months ago, # |   0 How to add a team member?I just created team but i couldn't find how to add my friend.
•  » » 16 months ago, # ^ |   0 Your team member needs to join the team.When your team member registers,go to the list of the teams,search for your team and then ask your team member to join your team.
•  » » » 16 months ago, # ^ |   0 Got it. Thanks very much.
 » 16 months ago, # |   +12 The GYM contest will start in 20 minutes and will last 5 hours. Sorry for the delay. Big thanks to Mike for his help with problems today.Consider competing even if you don't have time to spend all 5 hours for the contest. It's important to get familiar with the type of problems and the scoring.
•  » » 16 months ago, # ^ |   0 Will contest be available after Thursday?
•  » » » 16 months ago, # ^ |   +5 Yes, you can participate virtually later.
 » 16 months ago, # |   0 No link to participate in GYM replay.Where to look for the link
•  » » 16 months ago, # ^ |   0 find it on the list of GYM contests (http://codeforces.com/gyms) and register
 » 16 months ago, # |   +3 I submitted a brute-force solution for A and got 6 testcases accepted.But it shows that the partial points equal to 0.Please tell me if there are partial points.Thanks a lot!
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 Same here. My solution to B got AC on 7 testcases and shows partial points equal to 0.
•  » » » 16 months ago, # ^ |   +6 Have a look at the questions on the contest and you'll find that only complete solutions get points (10 points).
•  » » » » 16 months ago, # ^ |   0 Ok thanks :)
 » 16 months ago, # |   +1 Any idea about B？
•  » » 16 months ago, # ^ |   0 I precalculated the distance matrix using n number of dijkstra's. Then I used a 4 state dp[idx][pos1][pos2][pos3] -> when i am at city[idx] and the three people are at pos1 , pos2 , pos3. I used a map to store dp , but got tle in 3 testcases. Any idea how to optimise dp ?
•  » » » 15 months ago, # ^ |   +3 A 4-state dp isn't the best way to solve the problem.Since you're in city idx,one of the cars must be in the city idx,too.So it's not necessary to store pos3 in your dp.Then you'll get a 3-state dp.What's more,some of the cities aren't mentioned in the queries,so don't run Dijkstra on these cities,and it's enough to pass all the testcases in this way.
 » 15 months ago, # | ← Rev. 2 →   -43 .
•  » » 15 months ago, # ^ |   +79 No, it isn't funny.
 » 15 months ago, # |   +13 Does anybody else have a hart time getting to the problems page?
 » 15 months ago, # |   +4 How to solve problem B from Deadline24 Quals 2017?
•  » » 15 months ago, # ^ |   +11 Let's think on requirements as directed edge (u; v) — we took u and didn't take v. We should choose subset of edges, such there is no pair like (u; v) (v; k). Let's build biparate graph, where verices are edges (u; v) and there are edges between "bad" pairs. After that we just need to find maximal independent set. Graph can be large, but my solution using Kuhn algorithm with greedy initialization works quite fast.
•  » » » 15 months ago, # ^ |   +1 Can you please explain construction of bipartite graph in more detail ?
•  » » » » 15 months ago, # ^ |   +3 If u is from the faction F1, and votes for a candidate C, and v is from the faction F2, and votes against the same candidate C, we add edge (u, v) to the graph. Only one of {u, v} can be selected to the final answer. (that's how it's done in our solution)
•  » » 15 months ago, # ^ |   0 Not sure about this idea, it would be great if someone could validate it:This can probably be modelled as a matching/flow problem with each faction being a partite. If a member of first partite has a conflicting vote with a member of the second partite, we create an edge with infinite capacity between between them. Other edges can be source to each member of first partite with capacity = 1 and each member of second partite to sink with capacity = 1.No. of members whose choices can be satisfied would be N - max_flow.Don't know how to find the set of selected members for the panel though.
•  » » 15 months ago, # ^ |   +6 This task is the same as "Cat vs Dog" from NWERC 2008, there are solution outlines on the web.
•  » » 15 months ago, # ^ |   +1 Anyone else used an ILP solver for this one? The linear conditions are in the form 2*z[i] >= a[x] + (1-b[y]), we are trying to maximize sum of z. (z is boolean denoting whether or not both of the conditions of some person are satisfied; a and b are booleans of whether or not a person is elected in parties a and b respectively). So if either of the conditions are not satisfied, z[i] can only be false. It actually runs almost instantly :o Python code using Gurobi solver: http://codepad.org/a0Ldgh9W (I just noticed the na_var and nb_var do nothing, nevermind those :D)
 » 15 months ago, # |   +13 When will be scoreboard unfrozen?
•  » » 15 months ago, # ^ | ← Rev. 3 →   0 On the news page is written that they will be available at 7pm but I don't know in what time zone.
•  » » 15 months ago, # ^ |   +6 From the site itself:The results are going to be available at 7 pm on March 12, unless we encounter any unexpected requests.After that time also another testing server will be running for anyone eager to re-check their answers (with no influence on results): http://trial.deadline24.plAfter 2:15 pm, the "Add question" section will be unavailable. Please ask any further questions by e-mail: contact@deadline24.pl
 » 15 months ago, # |   +3 For Problem A, we can get number of rows by Dilworth's Theorem — length of the longest antichain.How do we find all required rows? Finding LISs greedily after sorting pairs (height[i], age[i]) fails. What's the correct way to find the rows?
•  » » 15 months ago, # ^ |   0 Just greedy. Let's call pos[i] the position of value i in age array. Then iterate through the first array, if an index P was not chosen, you take it as the first element of a new row. Now loops through the first array from P+1 to the end, if pos[height[i]] > last then you should push height[i] to the current row and update last = pos[height[i]]. Repeat these steps until all the elements are taken. Since this competition only requires the output, this quite-slow solution is enough.
 » 15 months ago, # |   +64 Deadline24 is an international team programming marathon. During the contest, the teams of three tackle algorithmic problems for 24 hours. Ah, so this is why my teammates showed up 4 hours after the contest start
 » 15 months ago, # |   +26 How to get any valid answer in task D?I only managed to solve tests 1, 6 and 9 using this pattern:111111222222333333123123123123123123
•  » » 15 months ago, # ^ |   +25 I can describe my solution. Forget about numbers in cube, just use them to calculate result, focus on getting valid answer. :D Cut cube in this shape: There are about 1/4 of cube unmatched 1x1x1 cubes, match them with random area. Note that regions sizes are similar. This approach is enough to pass tests 2, 4, 7 and 10, number of regions is exactly the same as we want. Unfortunately we have to do some merges in others tests. Handling with number of neighbors is hard, so I've just tried to make all regions' sizes close to average, the way in which I've cut the cube was helpful with making number of neighbors high. There are some ways of merging regions: a) Just sort proper merges using some various comparator (for example take merge which minimizes size of resulting region) and do them greedily, as long as number of regions is higher than wanted.b) Find Hamiltonian path in the graph of regions and use DP to cut it to intervals. We are interested in number of regions on prefix (first dimension of DP) and numbers of resulting regions (second dimension of DP). As we want to make all regions' sizes similar, we will try to maximize minimum size. So result for DP[i][j] will be maximum possible minimum size, if we'll merge first I regions into J regions.c) Select (randomly) representative for each of regions that you want to have. Now consider merging other regions to representatives, each time make merge in which (for example) there is representative with minimum size.d) In which way of course do some randomizations.e) Run algorithm until it finds answer for each test case.It was enough to get first place for this task.
 » 15 months ago, # |   0 When will we be able to see the final ranking?
•  » » 15 months ago, # ^ |   0
•  » » 15 months ago, # ^ |   0 They are ready in the judge system.
 » 15 months ago, # |   +13 Would you mind sharing your approach to problem E. Rocks.Here is what I did. Let's fix some rectangle (x, y)... (x + n, y + n) and say that all cells of the figure will now stay on their places. Now we have some connected components outside the rectangle; I call them pieces. We process pieces from largest to smallest. For a piece, try every possible rotation and position and select the one which allows to place maximum number of cells. Among those cells which were not placed create new connected components and add them to the pieces queue.Some optimizations followed, most of them only decreased running time. First, a trivial cutoff: if an optimistic estimation on the answer is worse than the best answer achieved by now, we need no more calculations. Second, if a piece can fit the figure completely, we stop further computations as well. Next, I tried to put not only the piece with maximum size but every possible piece, if the test was small. Finally, to get at least any answer for testcases 9 and 10 I selected not every possible initial rectangle but only several with maximum number of cells inside, otherwise I couldn't wait for the code to finish.This approach resulted in 2-4 rank on each test by the beginning of the last hour.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +10 Our last approach (approximately the same rank):Let's add parts iteratively 1 by one. 1 step: Get first nonempty cell in input table, then bruteforce it's position in output(it has to be somewhere) and rotation. Now, using bfs add all the neighbouring cells we can to the same part (only those that are not used and their position in output is still free). Choose one that has biggest area.Now replace first by random and run 1000 times.
•  » » 15 months ago, # ^ |   +10 Pick a random cell of the container that has not been assigned yet. Iterate over every cell of the figure that contains the resource and has not been assigned yet. Fix that this cell will be assigned to the picked cell of the container with a fixed rotation. Now extend the assigned piece as much as possible with dfs. After computing the number of new cuts and the size of the component for every (cell, rotation) pair, pick the assignment that minimizes where C is some constant. Pick the best assignment and repeat the procedure until every resource cell has been assigned to the container. Repeat with different random seed and randomized C to get better results. The best choices of C seemed to be between 4 and 50 in the tests.We tried other heuristics than random for picking the cell from the container, but random seemed to be the best choice in all tests.Before the freeze we had rank 1 in tests 3-10.
 » 15 months ago, # |   0 The top 30 teams are qualified for the final rounds. Will the travel and hotel fee is covered by the organizers, and will we receive any support in applying for a visa?
•  » » 15 months ago, # ^ |   0 § 11 The Organizer shall not be liable for any costs incurred by the Participants in connection with their participation in the Contest, and in particular shall not provide accommodation for the duration of the Contest or refund the fare. The Organizer is not responsible for the Participant’s failure to apply to take part in the Contest or to transfer personal data for reasons beyond the Organizer’s control, in particular in the case of the legal representative's disagreement regarding the Participant’s involvement in the Contest. 
•  » » 15 months ago, # ^ |   0 I sent the committean email and yes, they said that travel and accommodation cost won't be covered by them. Not sure about the visa...It would be hard to find any sponsor in approx. a month :')
•  » » 15 months ago, # ^ |   +8 Even applying for a Schengen visa in my country in one month is a huge problem. It seems that I should leave my spot to someone luckier :)
•  » » » 15 months ago, # ^ |   +5 Lol, so there exists such thing as visa to Poland? I didn't know that for some people simple passport is not enough to enter my country ;p.
•  » » » » 15 months ago, # ^ |   0 Russians need Schengen visa too.
 » 15 months ago, # |   0 Will the problems be added to Gym ? If not, then will the organizers public the test data ? I can't find it anywhere.