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.
Is it only me clicking on the link
www.deadline24.plwill direct to this blog?UPD Missing
//aftera href="should be the reason? It interprets as relative URL I think.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 riadwaw, slashes helped.
try
[www.deadline24.pl](http://www.deadline24.pl)otherwise it's relative link which goes to
codeforces.com/blog/entry/www.deadline24.plwhich gives an error and redirects to last visited CF pageShould be
[www.deadline24.pl](//www.deadline24.pl)?How the marathon problems are going to be scored in gym?
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.
What's the point of closing the registration 3 days before the qualification round?
We (I mean organizers) need those days to prepare the whole environment for the qualifying round.
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.
Congrats on becoming Top Contributor
I'm used to it but thanks.
How will the expense of travel be covered, in the rare case my team is qualified?
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).
Will I?
Good point, not really ;p
What is the max number of people a team can have?
3
https://www.deadline24.pl/assets/regulations/QualifyingRoundRules.pdf
In 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.
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
Thank you!
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
"I was too lazy to check the date, I asked you to do it, and you were too lazy as well."
Do you want to argue one more time, about who definitely isn't "the responsible one"?
:D
Because contribution is more important than teammates.
How to add a team member?
I just created team but i couldn't find how to add my friend.
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.
Got it. Thanks very much.
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.
Will contest be available after Thursday?
Yes, you can participate virtually later.
No link to participate in GYM replay.Where to look for the link
find it on the list of GYM contests (http://codeforces.me/gyms) and register
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!
Same here. My solution to B got AC on 7 testcases and shows partial points equal to 0.
Have a look at the questions on the contest and you'll find that only complete solutions get points (10 points).
Ok thanks :)
Any idea about B？
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 ?
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.
.
No, it isn't funny.
Does anybody else have a hart time getting to the problems page?
How to solve problem B from Deadline24 Quals 2017?
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.
Can you please explain construction of bipartite graph in more detail ?
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)
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.
This task is the same as "Cat vs Dog" from NWERC 2008, there are solution outlines on the web.
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)
When will be scoreboard unfrozen?
On the news page is written that they will be available at 7pm but I don't know in what time zone.
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.pl
After 2:15 pm, the "Add question" section will be unavailable. Please ask any further questions by e-mail: [email protected]
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?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.
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
How to get any valid answer in task D?
I only managed to solve tests 1, 6 and 9 using this pattern:
111111
222222
333333
123123
123123
123123
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.
When will we be able to see the final ranking?
/blog/entry/50851?#comment-348461
They are ready in the judge system.
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.
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.
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.
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?
From: https://www.deadline24.pl/bylaw/
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 :')
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 :)
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.
Russians need Schengen visa too.
Will the problems be added to Gym ? If not, then will the organizers public the test data ? I can't find it anywhere.