cgy4ever's blog

By cgy4ever, history, 9 years ago, In English

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

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

| Write comment?
»
9 years ago, # |
  Vote: I like it +41 Vote: I do not like it

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

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

    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 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

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

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Editorial Link

Thanks for the fast editorial, cgy4ever and rng_58

»
9 years ago, # |
  Vote: I like it +23 Vote: I do not like it

4 russians and bmerry, heh :)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    And 9 Russians in the semifinal out of 12 participants :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +91 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +28 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it +21 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +45 Vote: I do not like it

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 years ago, # |
  Vote: I like it +64 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it +23 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it -29 Vote: I do not like it

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.