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

Автор cgy4ever, история, 9 лет назад, По-английски

Hello everyone! Tomorrow we will know who is the TCO2015 Algorithm winner!

Do you remember misof did live coverage in previous years like this: http://codeforces.me/blog/entry/14753

This year he is not here at Indy. rng_58 and me (we coordinate TCO algorithm contest together this year) will do live coverage this time!

You will be able to read them here: https://www.facebook.com/TCO2015Algorithm

Today I will post some updates about Marathon contest to make sure I know how to post picture / video quicky, and you can get familiar with that facebook page.

Please let me know what you want to see beside the following:

  1. Problem Statements

  2. Simple editorial

  3. Live update (like: tourist submitted his Hard with 789.01 score / Petr start to write Medium, seems he is on the good track!)

  4. Photo of current scoreboard (is that needed?)

Thanks! See you tomorrow!

Update: We just heard that contestants have internet access during the contest. So we can't publish statements / solutions until the end of challenge phase. We will publish solutions after the end of challenge phase.

Update2: We will publish problem statements once all contestants opened it.

Semifinal:

Statement: https://docs.google.com/document/d/1D0WUDNeWWlpM7ixNMlW7K2FMSk2sXSuOKEyGT-7M3IA/edit?usp=sharing

Editorial: https://docs.google.com/document/d/15zjuih75vzK6VYyi4gSRXdn62lkT8zQiGcJT64qBNp4/edit?usp=sharing

Result (Top 5 advanced to finals):

Final:

Statement: https://docs.google.com/document/d/1putaFIk4OUVlJBzICaA8m7Znd2prVWwQj4P0F6SlsL0/edit

Editorial: https://docs.google.com/document/d/1oJlKlyr3HHKgDEH0sEawXsG31rnOBWaEWHbEq7wFqRk/edit

Winner

Petr and ACRush

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

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

Isn't it strange to post something like "his solution looks right!" when we know the results of the systest?

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

    Is there any concern that information could somehow make it to contestants? I do not know how TCO works but say spectator on site reading coverage of the contest on his phone, then knows things contestants should not know, and have to make sure this information can not accidentally or otherwise be transmitted.

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

    Well, we can say that when he start writing his solution.

    And of course we don't want to be spoiler.

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

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).

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

Hey,
Will there be any live broadcast on youtube or somewhere?

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

Мне кажется или на CF не так давно кто-то спрашивал как решать 1000 с этого полуфинала?

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

Ouch, it looks like tourist's med has failed system test causing to him be out of competition.

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

Editorial Link

Thanks for the fast editorial, cgy4ever and rng_58

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

4 russians and bmerry, heh :)

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

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).

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

What I am interested in, why Petr submitted the solution when some seconds left? Is he testing too much or he completed the solution that time? Whatever his next blog will be interesting and hoping for brief.

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

    If it is clear that you win even if you submit your solution at the last second, there's no reason to submit it earlier. It is better to test it/re-read the code/think of corner-cases/etc. Especially if you're not entirely sure in your solution, which was probably the case here.

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

      You are probably right. But does not petr took the risk of submitting in last minute or seconds. Because we all know topcoder arena, it might hanged for him only even if the load is pretty low. Does they monitor the finalist computer? I am not aware of.

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

Did tourist have a winning streak up till now? If so, C-C-C-COMBO BREAKER!!!1!

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

So, is the era of tourist over? Petr won the last two major contests (Mailru Russian Code Cup and TCO), and the last one — with a huge margin.

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

    I might have read somewhere in either Petr blog or in TC arena that rng_58 is leaving and cgy4ever is taking his place. Next year will then have more competition.

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

    Even so, 2015 will be remembered as the international year of the tourist.

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

    Such troll, much wow :)

    The "huge margin" seems to be referring to his 500 solution failing in the semifinal, which is just a random unlucky event.

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

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).

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

Interesting. A friend linked me to this: https://www.reddit.com/r/mathriddles/comments/2v6eaj/doubling_and_adding_1/

Of course I am not accusing the problem writers of copying. I'm just surprised that this problem appeared in two distinct places around a similar time.

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

When will the practice room open? I'm glad to see two Div I 1000pts 0AC....

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

There's a nice alternative O(nlgn) solution to Jumps (Final 250p) using the observations that if the original sequence is x0, x1, x2, ... then for i < j, lowestbit(abs(xj - xi)) = 2i, and that the latest occurring element (wrt to the original sequence) must be the minimum or maximum in the input sequence. This allows us to determine the positions of the given values in the original sequence to be 1 of 2 possibilities and then it is just a matter of checking if either works.

Dodgy Python Implementation

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

What is a strange rules of TCO Final? Why they use a semifinal to eliminate "12 -> 5"? Why they don't make a final with 12 participants?

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

    Why not? I think both 12->5->1 and 12->1 systems are good in their own right. The 12->5->1 system has a few benefits:

    1) It allows the competitors to showcase different strategies for different goals, as trying to get into the top 5 calls for a different approach than trying to win. This is great for spectators, as they can watch people engage in a strategy battle.

    2) It allows to hold sevreal rounds instead of just one, proving more interesting problems to solve for the competitors and more to watch for the spectators, while not having one long round that would be tiring both for contestants and for spectators.

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

      What would you think of approach with two rounds that everybody competes in and then the final results for everybody are the sum of the two rounds? It would seem that it would reduce variance, as failing one problem in the first round would not necessarily eliminate one from contention. On the other hand the strategy would probably be a bit less interesting I agree.

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

        I think this could work, too, but as you say it might be a bit different in strategy. We have this format in SN*S :)

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

      Different approaches in each stage.. exactly!
      Congratulations with a brilliant victory!

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

I think same people always win all competitive programming cups, it would be better put limit like acm — icpc. It's not interesting when same people one cup again.