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

Автор ibra, 9 лет назад, По-русски

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, enot110, subscriber
4Dreadnought: TankEngineer, rowdark, BaconLi
5nedrharmsw: AntiForest, rnsiehemt, JoeyWheeler
6Orz!: zcz, KFDong, ExfJoe
7-XraY-
8Saratov SU Daemons: danilka.pro, Edvard, 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.

Разбор задач Bubble Cup 8 - Finals [Online Mirror]
  • Проголосовать: нравится
  • +82
  • Проголосовать: не нравится

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

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

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

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?

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

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

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

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

.

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

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

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

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

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

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?

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

    yes

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

      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?

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

        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

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

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?

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

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

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

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

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

Was the solution file down? I can't open the Dropbox link. Can anyone upload a new one?