Errichto's blog

Deadline24 2017 — Qualifying Round and GYM replay of previous edition
By Errichto, 8 years ago, In English

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.

  • Vote: I like it
  • +161
  • Vote: I do not like it

Comments Comments (71)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +7 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 4   Vote: I like it +20 Vote: I do not like it

      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

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it +20 Vote: I do not like it

      Should be [www.deadline24.pl](//www.deadline24.pl) ?

      → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How the marathon problems are going to be scored in gym?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What's the point of closing the registration 3 days before the qualification round?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    We (I mean organizers) need those days to prepare the whole environment for the qualifying round.

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Congrats on becoming Top Contributor

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How will the expense of travel be covered, in the rare case my team is qualified?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +116 Vote: I do not like it

    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).

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the max number of people a team can have?

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
8 years ago, # |
  Vote: I like it +38 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    "I was too lazy to check the date, I asked you to do it, and you were too lazy as well."

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      Do you want to argue one more time, about who definitely isn't "the responsible one"?

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +110 Vote: I do not like it

    Because contribution is more important than teammates.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to add a team member?

I just created team but i couldn't find how to add my friend.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Will contest be available after Thursday?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yes, you can participate virtually later.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

No link to participate in GYM replay.Where to look for the link

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Same here. My solution to B got AC on 7 testcases and shows partial points equal to 0.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Have a look at the questions on the contest and you'll find that only complete solutions get points (10 points).

      → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Any idea about B？

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

.

→ Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Does anybody else have a hart time getting to the problems page?

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve problem B from Deadline24 Quals 2017?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Can you please explain construction of bipartite graph in more detail ?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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)

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    This task is the same as "Cat vs Dog" from NWERC 2008, there are solution outlines on the web.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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)

    → Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

When will be scoreboard unfrozen?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    On the news page is written that they will be available at 7pm but I don't know in what time zone.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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: contact@deadline24.pl

    → Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +64 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    I can describe my solution.

    1. Forget about numbers in cube, just use them to calculate result, focus on getting valid answer. :D

    2. 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.

    3. 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.

    4. 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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will we be able to see the final ranking?

→ Reply
»
8 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    From: https://www.deadline24.pl/bylaw/

    § 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.
    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :')

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 :)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the problems be added to Gym ? If not, then will the organizers public the test data ? I can't find it anywhere.

→ Reply