Блог пользователя Errichto

Автор Errichto, 7 недель назад, По-английски,

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
  • Проголосовать: не нравится  

»
7 недель назад, # |
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.

  • »
    »
    7 недель назад, # ^ |
    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.

    • »
      »
      »
      7 недель назад, # ^ |
      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

    • »
      »
      »
      7 недель назад, # ^ |
      Rev. 3   Проголосовать: нравится +20 Проголосовать: не нравится

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

»
7 недель назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 недель назад, # ^ |
      Проголосовать: нравится 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.

»
7 недель назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 недель назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 недель назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I think this is Deadline24 2017 — Qualifying Round and GYM replay of previous edition ? is it bood?

»
7 недель назад, # |
  Проголосовать: нравится +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.

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Congrats on becoming Top Contributor

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 недель назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
7 недель назад, # |
  Проголосовать: нравится +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

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to add a team member?

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

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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.

»
6 недель назад, # |
  Проголосовать: нравится +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.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
6 недель назад, # |
  Проголосовать: нравится +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!

»
6 недель назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Any idea about B?

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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 ?

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится +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.

»
6 недель назад, # |
Rev. 2   Проголосовать: нравится -43 Проголосовать: не нравится

.

»
6 недель назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
6 недель назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve problem B from Deadline24 Quals 2017?

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        6 недель назад, # ^ |
          Проголосовать: нравится +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)

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +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)

»
6 недель назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

When will be scoreboard unfrozen?

  • »
    »
    6 недель назад, # ^ |
    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.

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +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.pl

    After 2:15 pm, the "Add question" section will be unavailable. Please ask any further questions by e-mail: contact@deadline24.pl

»
6 недель назад, # |
  Проголосовать: нравится +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?

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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.

»
6 недель назад, # |
  Проголосовать: нравится +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

»
6 недель назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    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.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will we be able to see the final ranking?

»
6 недель назад, # |
  Проголосовать: нравится +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.

  • »
    »
    6 недель назад, # ^ |
    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.

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +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.

»
6 недель назад, # |
  Проголосовать: нравится 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?

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.
    
  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 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 :')

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +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 :)

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится +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.

»
4 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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