monsoon's blog

Second edition of Marathon24 team programming contest
By monsoon, 10 years ago, In English

Hello everyone!

Once again we invite you to participate in the 24-hour team programming contest Asseco Programming Marathon24 Gdynia 2014. Powered by CodiLime. The first edition in 2013 was quite a success: 243 teams of three from over 20 different countries were registered for the contest and 30 teams from 8 countries were qualified for the finals in Gdynia.

In the contest teams of three can participate. There is no limit concerning the age or education of contestants. Also there is no limit in equipment, programming languages or materials you can use during the contest.

The contest consists of two stages. You can check out problems from the first edition to familiarize yourself with the format. This year's tasks will also be prepared (among others) by Tomasz Idziaszek monsoon and Wojtek Nadara Swistakk.

The first stage are qualifications, which will start on 11th October 2014 at 9:00 CEST and will last for 5 hours. There will be 5 algorithmic problems, to which 10 test cases will be provided. You only submit outputs to the tests and you get immediate feedback on your score.

No more than 30 teams with the highest scores will qualify for finals. They will take place in Pomeranian Science and Technology Park in the city of Gdynia in Poland. Finals will begin on 29th November 2014 and will last for 24 hours. There will be 3 problems, which will require you to write a program communicating with the contest server through the TCP/IP protocol.

For three teams with the highest scores in finals there are prizes amounting to over 30 000 PLN in cash. For more information visit our site: marathon24.com. The registration closes on 9th October 2014.

Update: Also be sure to take part in Codeforces Round #270, for the top 25 participants of this round will get Marathon24 T-shirts!

Good luck and have fun!

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

Comments Comments (48)
| Write comment?
»
10 years ago, # |
  Vote: I like it -50 Vote: I do not like it

Please No Difficult Questions :)

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

where i can register ?

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

Ah. If only qualification would not coincide with Running City event

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

Can we participate as a team?

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

    The contest is prepared for teams made of 3 coders

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

Were problems interesting :)?

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

    They were!

    The last video for beads was amazing :)

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

    I'm not sure about problem "Beads", but other problems were really nice! The only exception: as for me, problem "Passing" was tiring a bit. Sometimes it was hard to deal with output like "Wrong Answer: switch with a car, line 69" or "Wrong Answer: Trains intersection, line 52111" :) Anyway, it was very interesting!

    Also, I enjoy limit s >= q/10 to accept solution in problem "Rainfall". Due to some bug we have only about 700 correct answers of 6663 in output for test 7 submitted in last 5 minutes.

    Thanks a lot for the contest!

    BTW, what is the reason for such delay in publishing the final results?

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

    They were much better than the last year. Especially beads with movies. Correcting your rank-to-score function (adding optional weight) was also a nice improvement over the last year, although IMHO it should have been included in the problem description.

    I hope that the onsite problemset will get a similar improvement :)

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

For how long the standings will be frozen and how can I know the result of a last hour submission without waiting for overall results?

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

    I want to know the same thing. You said that the last video of beads was amazing.Does it meens that you made the problem?In that case, could you tell me how can i read a jpg in C++?

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

      We didn't use any programming tools for this problem, but got pretty good points for it. For the pictures one can count them in mind using Adobe PS or even simple Paint to color counted beads. It was quite easy for all the pictures except the last one. For the videos we computed the output by simply watching them :) However, for the last one we had to assume that there were only RGB colors and that the number of beads of every color was equal. So the task was to get a good approximation of the overall number of beads. 100 100 100 0 0 0 0 gave us 5.3 points or something like this.

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

        Didn't assume that numbers are equal. )
        Openen video in VLC, set speed to very slow and got 6.5 with 84 101 78 0 0 0 0. =)

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

    Here is the answer of our question : "You can check out the results after 4 hours of the competition. The official results will be published next week" :)).It was published on the main page.

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

How the last one is solved?

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

    RAI :D? Definitely the most painful code I have ever written. I was almost sure that nobody will solve that, how I was surprised when I saw accepted code after 2,5h :O! But I coded O(nlogn) solution, but in the end limits were lowered such that solutions in O(n2) could pass them freely, so my code needed to be even more complicated.

    That will be a really rough sketch of rough sketch of solution, because there are so many details that we need to take care of, but I hope that this will be helpful:
    It can be seen that whole mountain can be treated as binary tree, where its vertices are trapezes, which could be filled with water. Vertex v is a son of vertex w iff v denotes trapeze which is directly under trapeze denoted by vertex w. We can construct that tree using some stack.
    Water is always draining to leaves of that tree. Each leaf corresponds to an interval of x coordinates such that when we have rainfall in this interval water drains to that leaf. Those intervals create a decomposition of interval [x_1, x_n]. We can maintain those intervals in for example set. When water fully filled a vertex we need to update drain intervals, delete that vertex from tree. We need to individually cover cases when that vertex had a sibling or not.
    We surely needs some geo to count height of a water in a trapeze. That can be done using solving quadratic equation on a paper or binary search.
    We need to be able to answer queries. In order to do that we need to keep track also of a height of a mountain on a particular x and of fully filled vertices such that they have not fully filled sibling.

    I will leave improving that solution into O(nlogn) as interesting exercise.

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

      I was terrified by that problem, it's the only problem we haven't submitted to. I had some trouble understanding the statement too, but really loved the rest of the problems :)

      P.S. Had lots of fun counting marbles by all kinds of methods since none of my team knew how to parse a .jpg to color grids :P

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

Not trying to be mean, but I'm just wondering why will it take so much time to get the official results? I mean there was livescore the first 4 hours so computing the results obviously isn't hard and in this type of competitions there aren't any sources to check for cheaters, so why will the results be posted next week?

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

Thanks for the contest, I liked this kind of problems, especially BEA and PAP. We didn't have a lot of time for beads counting, but I enjoyed making some interesting computations with images. Finally I found this article which solves this task with a few MATLAB code lines. Did you know about this method when you decided to give this task to the contest?

Unfortunately, we didn't pay enough attention to the scoring system and thus started working on PAP not very soon and lost some points on easy inputs. I wonder how did other teams solve this task.

My solution was the following. First, let's take all points and sort them as pairs. Then take the sequence 1, k, 2, k - 1, 3, ... (k = nm) as a first approximation. The score of this route is min(n, m). It already gives optimal answers for tests 6-8.

Then let's do some local optimizations. If the distance d occurs most often then we take some points where the distance to the next point is equal to d and shuffle them. Repeat 100000 times. This way we got optimal answers for 1-3, good enough answer for 4 (score is 6; lower bound for score is 5, but nobody reached it, so I believe 5 is optimal), 14 for 5 (again, lower bound is 10 and the best known answer is 13) and some reasonable scores for 9-10 (9.9 points for both inputs and a ~10 gap with the first place). I wonder which solution did BSUIR_Power use for 9 and 10 inputs.

(btw, lower bound I used is calculated as because of the pigeonhole principle.)

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

    For tests 9-10 we done following: choose random start point, on each iteration check about 20 random points which we haven't visited yet, go to one distance to which we used fewer times(among such points choose one with greater distance).

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

    n+m-2 to be precise :)

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

    Solving beads with CV was a really bad choice, unless you use it in your every-day job so you're incredibly proficient in it.

    First of all, the detection was pretty hard, considering some of the beads were laying on top of each other. Also, some of them had different sizes. So you need to visualize your answer as well, and then double-check it and (most probably) further correct it by hand. And it was only useful for 4th and 5th test — first 3 were doable by hand and, well, good luck with the videos :)

    Edit: Oops, replying under wrong posts :)

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

By the way, not to steal credits for other people's work :P — I wasn't that into organization as I was last year. Last year I was an intern at CodiLime where I prepared all qualification problems and big part of final tasks, but this year I prepared FIL and RAI problems only (though the latter one demanded unexpectedly huge amount of effort from me), those with most standard formula.

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

Will some teams with place > 30 be invited to the finals in case some of top30 teams reject the invitation?

And how long are four hours in Poland?:)

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

    I think that you misunderstood "You can check out the results after 4 hours of the competition.". They wanted to say that you can view freeze time results. :) And final results will be published next week for unknown reason yet :/

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

      Oh! I accidentally read "of" as "after"...

      Anyway the first question is more important.

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

        Last year our friends were 37th at qualifications and they were invited to the finals later, so I guess they also will invite 30 teams in total this year.

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

    Current results are frozen and show the results 4 hours after the start of the competition, for some reason the results from the last hour will be delayed to next week..

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

The final standings seem to have been published.

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

Will detailed results for Beads be published? Now it is pointless to hide them (during contest such information may help to find correct answer — but now contest is over).

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

31st ...

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

    We are 31st too :D If one of the first 30 teams rejects the invitation, Which one of us will be invited, if any?

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

      this one or that one?

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

        Enchom [me], ha1vanka and DKarev are in team Untitled ( we didn't intend to be Untitled, we just really forgot to put a name :D ), and I suppose poopi is from team PMP_Forever. Both teams with exactly the same score being 31st place!

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

          Looks like you or poopi will be able to go! Unfortunately, our team can't make the finals because of Thanksgiving holiday.

          Good luck!

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

            Thanks, we received a mail that we are in the reserve list but nothing more than that yet :P

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

How do you think, guys, will nineteen teams reject the invitation to the onsite finals?))

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

How many teams will advance to the finals and when invitations will be sent out?

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

    It was written something about thirty teams.

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

      But in the formal rules it says "from 20 to 30 teams" that's why I'm asking.

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

    We received an official invitation several minutes ago. So, try to check your e-mail)

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

      I didn't receive official invitation yet but this document says that 30 teams will be invited and now I feel safer :)

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

        Ask your teammates, looks like messages were sent only to team captains.

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

          It's not true for your team, since all of us have received one.

          → Reply