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

Автор monsoon, 10 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +121
  • Проголосовать: не нравится

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

Please No Difficult Questions :)

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

where i can register ?

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

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

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

Can we participate as a team?

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

Were problems interesting :)?

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

    They were!

    The last video for beads was amazing :)

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

    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?

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

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

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

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?

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

    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++?

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

      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.

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

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

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

    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.

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

How the last one is solved?

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

    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.

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

      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

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

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?

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

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

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

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

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

    n+m-2 to be precise :)

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

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

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

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.

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

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

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

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

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

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

      Anyway the first question is more important.

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

        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.

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

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

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

The final standings seem to have been published.

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

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

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

31st ...

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

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

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

      this one or that one?

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

        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!

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

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

          Good luck!

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

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

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

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

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

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