Gassa's blog

Codeforces Marathon Round 2
By Gassa, history, 6 years ago, translation, In English

Hi all!

I invite you to take part in Codeforces Marathon Round 2. The contest will start on Tuesday, July 24, 2018 at 15:00 MSK, and will last for 7 days. There will be one problem based on game mechanics of a couple of board games for children. The problem most likely does not have a fast and full solution. So the solutions will be given scores, and the winner will be the one who gets the highest total score.

The contest will be unrated because the problem is considerably different from the problems of rated rounds.

During the time of the contest, the solutions will be checked on examples and preliminary tests. After the contest is over, the final solution of each contestant will be checked on the final test set, and the total score for this test set will determine the final scoreboard. The contest will take place on Codeforces platform and is supported by the Community Of Master Programming at St. Petersburg State University (link in Russian) and 90.01 Group.

The Codeforces platform has seen only few marathons so far. So, if something breaks, don't be upset, just write about it, and we will try to fix it.

Good luck in the contest!

Announcement of Codeforces Marathon Round 2
  • Vote: I like it
  • +266
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Will it be allowed to participate in teams of 2 or more?

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

    As seen in registration option, I think they wont allow.

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

      But in previous Marathon Round participation in team was allowed. If this can be done in this round as well? Anyways it is unrated.

      Edit — Registration page allows team participation. It is just that it is not mentioned in announcement page.

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

    It is now possible to register either individually or in teams of 2 people.

    If you registered individually but now want to register as a team, you will have to find your previous registration and cancel it first.

    → Reply
»
6 years ago, # |
  Vote: I like it -39 Vote: I do not like it

Will hacking be there?

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

where I can see previous codeforces marathon contest?

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

Gassa, Will there be T-Shirt distribution just like Codeforces Marathon Round-1 ?

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

Previous marathons on Codeforces:

VK Cup 2012 Wild-card Round 2

VK Cup 2015 - Wild Card Round 2

VeeRoute Marathon

VK Cup 2016 - Wild Card Round 2

Codeforces Marathon Round 1

VK Cup 2017 - Wild Card Round 2

VK Cup 2018 - Wild-card Round 2

Codeforces Marathon Round 2

I hope that there will be more of them in the nearest future)

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

So there is only one problem in the whole contest? Sounds challenging.

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

Can someone please explain in a little more depth how exactly these problems differ from normal rated rounds? I would like to participate, and have not taken a round like this before.

Thanks :)

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

    See I'll try to explain hope you understand. :) There will be one question only and there is no fixed answer for it! It may vary, its a problem where you are given some data and you have to write a program which uses this data to give the best possible output lets say this output as your final score! Now different programs/algorithms will produce different final scores and based on this final score produced by your program you will get a points for your algorithm! so the better your program works the more points you will get and thus better rank!

    hope it is clear!

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

      So, basically its like the challenge problem of codechef long challenge?

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

        exactly! but i'm just guessing it will be a bit more challenging! (no offense to anyone! :))

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

Has the beginning time changed(+30 mins) ?

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

    I think so. The start time has changed few minutes ago. Maybe something went wrong.

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

    Yeah, some last-minute problem occurred. Everything seems fine now. Sorry for the delay!

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

Can someone tell me why the match delayed?

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

I know it's unlikely, but what will happen if a bottle of color c is thrown and there is no more squares of this color exists in the rest of the stripe?

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

    Since the stripe is infinite and periodic, that would mean there is no such color in the pattern.

    Such tests are not explicitly forbidden. Still, it would be a miracle if this happens when we pick a test uniformly at random. If the miracle does indeed happen, we'll think of something.

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

How many people will get T-shirt?

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

    Unfortunately, no T-shirts are planned for this round.

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

It looks a bit suspicious

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

    Please do NOT suspect that.

    We, Japanese participants, love marathon contests and have a lot of experience. See this. https://community.topcoder.com/longcontest/stats/?module=CountryRank

    There are many marathon and game AI contests in Japan. We are just getting used to them. Also, keep in mind skill-set for marathon is a bit different from one for ICPC. For example, hakomo is a red coder on Topcoder marathon matches.

    We know sportsmanship is the most important. We never share code, knowledge or observation during contests. I guarantee.

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

    I'm wondering why there are too many downvotes to this comment. Of course I think there is no cheating, but also I feel that the suspicion itself was natural if you didn't know about marathon matches.

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

      I think downvoting is justifiable. Yes having a suspicion of cheating is natural, but casting this suspicion without evidence is simply irritating.

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

      I agree on kobae964's opinion.

      This is just a problem of the manner. Nobody blames you feel something is suspicious. I also think the leader board is different from usual contests and the combination of the country distribution and no very high SRM ratings makes it unusual. However, when you say something which could be rude if your opinion is wrong, you need to be careful to post it.

      Which point was problematic? — He just pasted a screenshot saying nothing but "it's a bit suspicious". To me, it was just like he gave a seed of gossip a bit lacking respect to the competitors rather than raising an issue. That's because you don't need to use negative sentences if you really want to know the reason for some unusualness. I prefer positive sentences + reasons.

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

        I really don't understand which positive sentence would you like to see. Maybe: "Look, what a funny coincidence, all these guys in the top of the scoreboard are from the same country and have a not high rating in the regular contests. Well done! Keep it up!" Any message of this kind would be fucking hypocrisy, do not you think?

        My message was absolutely neutral as it describes the natural feeling, and it really has no a direct charge of cheating, and I did not want to blame anyone. Btw, I suspected more that you had some similar task in the local competition than they are cheating. Maybe you'd rather like the words "strange" or "unusual" (as you wrote in your comment) over "suspicious" in my sentence, but in my vision that doesn`t change the idea of the message at all. Sorry if that was rude for you.

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

          Thanks for replying.

          ... Any message of this kind would be fucking hypocrisy, do not you think?

          Of course, what you wrote is definitely not what I would’ve liked to see. It's like playing with sarcastic words.

          Btw, I suspected more that you had some similar task in the local competition than they are cheating.

          Actually, this is exactly what I would’ve liked to see. I think the reason brings a constructive discussion on the right track you intended. I understand your intent now and I'm sorry for misunderstanding. I've failed to guess your thought and I've supposed you were thinking those competitors were possibly cheaters.

          Now I realized I would've liked you to put the explicit reason why you felt so in order not to make someone like me misunderstand you, and "avoid" negative words if unnecessary. I think something like the following sentence doesn't have so many different interpretations: "I see many competitors from the same country on the leader board. Was there any similar competition before in their country?"

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

Gassa Thank you a lot for the round, really nice task.

May someone share ideas of your solution? :)

My final submit: https://gist.github.com/yarrr-ru/97361c5bca72bb3b5f0e549b811a510b

I'll describe my key ideas soon, sorry.

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

    Thanks! I've noted my (rather simple) ideas here, and encourage the contestants to do the same with theirs!

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

    I have in general similar to your solution, but new states are generated in a different way. I take several moves from the current state, that are the best by distance, and to get the score of new states I perform ~30 more greedy moves, and only then calculate score as a weighted sum of positions. That is 38900 if all moves are performed with only the last unit. But in last 10 minutes of the contest I thought: "What if it's not optimal to perform all the moves with the last unit?", so I added some hacks, and got +1000 points. Unfortunately, after that there was no time for adjusting the constants for the new algorithm and for TL. So it's 39900 in scoreboard, about 40900 after some local fixes, and 42000 with increased constants and 4xTL. Code (for 40900): https://www.ideone.com/UXF5B4

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

Is there a way to change which submission will be judge now? I forgot to resubmit the best one after some teste Q.Q

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

    Sorry, this process is automated.

    The alternatives are currently not feasible: the best solution on pretests (as opposed to the last one with positive score) might actually be just lucky with them, and there is no additional functionality for the user to mark which solution to judge.

    → Reply