ibra's blog

By ibra, 4 years ago, translation, In English,

In the very beginning of this post I would like to thank everyone who contributed to make this contest happen — both onsite and online versions. For many of us it was practically the first contest we really took part in preparing of — we all loved working on it and hope you liked it too.

I would also like to mention that 2864 teams (about 4k people!) registered to this contest, 1025 actually took part in it, 637 managed to solve at least one problem and there were 4 teams that solved all the problems before contest ended. Congratulations to everybody! Ok, so here is top 10 of Codeforces version of Bubble cup:

1tourist
2Nizhny Novgorod SU: mike_live, vepifanov
3SPb ITMO University 1: antonkov, enot.1.10, subscriber
4Dreadnought: TankEngineer, rowdark, AngryBacon
5nedrharmsw: AntiForest, gendelpiekel, izrak
6Orz!: zcz, KFDong, GyWXwshMy
7-XraY-
8Saratov SU Daemons: dans, homo_sapiens, kuviman
9Omogen Heap: Gullesnuffs, simonlindholm
10Bsuir_power: andrew.volchek, teleport

All of them will get T-shirst. But apart from them, as we promised, there will be 10 T-shirts more sent to randomly chosen teams, here they are:


For those who are interested here is a link to results of onsite competition.

Since editorial is pretty big I think it is more reasonable to share link to file here than posting it all here.

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

»
4 years ago, # |
  Vote: I like it +119 Vote: I do not like it

".docx" T_T ..........

There is a joke on UW that one particular of our professors has solved TSP problem, but he is ashamed to publish it, because he has written solution in .docx format

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

    thx for comment, changed to pdf-file

»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

When I read the first entry about competition, I read it wrong, so instead of "10 t-shirts will be handed out randomly to other participants of the top 100", I read something close to random 10 teams from top 100 will get t-shirts.

Later on, of course I realize my mistake, but now I'm very curious about implementation of this t-shirt algorithm. As far as I concerned, it's really hard to give 10 t-shirts to a random teams, that sum of team members will be equal to 10 and also satisfy the uniform distribution (of course you didn't said you will give t-shirts based on uniform distribution)

Could you reveal some information on your random generator?

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

    algo randomly picks a team and if we have enough T-shirts left we take that team, else trying to pick once more.

»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

H. Bots. It can be simply shown that the number of possible solutions is equal to . So it is needed to find

.

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

good problems! But most chinese students can't use dropbox, sad...

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

In problem H, can someone explain why most of the solutions include C(i, N) * C(i, N)?

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

H. Bots. What does "Number_of_duplicating_vertices_from_level" stands for? Is it number of vertices on level i each of which will produce two vertices on level i+1? Does C(i,N) stands for i choose N?

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

    yes

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

      ibra, thanks, it must be I don't understand here something. If I look at trie for N=3 there is 6 vertices on level 3 that produce duplicates. But according to PD definition PD(3) = 2 * C(3,3) = 2. What I missed?

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

        thanks for comment, it is a typo.

        PD is number of vertices that do not duplicate (because they already spent all 0s or all 1s),

        and of course then, Count[i+1] = PD(i) + (Count[i]-PD(i))*2

        will correct it now

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

In the editorial for problem F, when it says "If x_turn is shining, then pos' is shining as well, so we could have finished our turn there.", isn't that only true if x_closer2 <= pos'?

Also, how can we justify that it is optimal to stay at an endpoint when x_turn is not shining?

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

    Sorry if not clear enough, the only sentence about x_turn shining is "If x_turn is shining, then pos′ is shining as well, so we could have finished our turn there.". Other part of the paragraph is about x_turn not shining.

    And statement "If x_turn is shining, then pos′ is shining as well, so we could have finished our turn there." is always true. Take a look at the picture above that sentence. pos' and pos'' are the closest light-up endpoints to the x_turn, so the smallest interval of shining bulbs is at least [pos', pos'']. Rationale: if x_turn is shining and it is not the endpoint then one endpoint is left other endpoint is right...

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

      Right, I didn't notice that. Thanks for the explanation.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

For Tablecity I made a smaller version where you can do it yourself, I made it on a webpage, you can download it here