MikeMirzayanov's blog

ACM-ICPC World Finals 2015
By MikeMirzayanov, 10 years ago, translation, In English

Hello!

Only a few hours before the start of ACM-ICPC World Finals 2015!

The ACM ICPC is considered as the "Olympics of Programming Competitions". It is quite simply, the oldest, largest, and most prestigious programming contest in the world.

The ACM-ICPC (Association for Computing Machinery — International Collegiate Programming Contest) is a multi-tier, team-based, programming competition. Headquartered at Baylor University, Texas, it operates according to the rules and regulations formulated by the ACM. The contest participants come from over 2,500 universities that are spread across 100+ countries and six continents.

This year the best 128 teams in the world will meet face to face in Marrakech on World Finals. Video coverage will start on 09:00 (UTC), and the contest will start on 10:00 (UTC).

Good luck to all the teams!

UPD Added link to the text coverage on tumblr.

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

Comments Comments (105)
| Write comment?
»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Good luck everyone!

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

Is there any way to see the problem statements? i am curious

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

I hope the next year we participate in it

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

Will topcoder-style scoreboard be available? If yes, what link to this scoreboard is?

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

Good luck rng_58

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

While you are waiting for start you can sit back and read my review of LNU_Penguins.

Post on Medium

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

    I think it deserves a separate post here.

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

      I am not sure that one link deserves the separate post. Do you?

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

        However, the people will be more likely to notice it if it is mentioned along with other blog posts rather than when it is just a small comment here.

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

Go, Ukraine!

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

Best of luck Bangladesh , best of luck #SUST_DownToTheWire and #Ju_Assasins :)

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

30 min before time, when contest will starts, but tourist haven't solved any problem. why? :)

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

    He has already solved all problems, but submit solutions he can when contest will be start)

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

I'll use my twitter instead of my blog this time :)

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

gl & hf!

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

Is there is any translation in Russian?)

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

Why scoreboard is not available?

P.S. Fixed now :)

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

13 problems

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

    Strange World Finals... First problem solved on 5-th minute :(((

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

      A is trivial. F looks easy too, soon should be first AC.

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

        Problem difficulties according to broadcast: easy — A,D,I, medium — E,H,C,M hard — B,F,G,J,K,L

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

          Why F is hard? O(n*r*c) got TL? A lot of teams had solved it.

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

            Ok, that distribution seem to be wrong.

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

            Well the problemsetters and presenters were distributing them in categories and the problem setter said that F had some difficult corner cases which must be known beforehand.. So he put it in hard column!

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

The problemset has been posted: http://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf

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

problem set: http://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf

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

Go, Belarus, go, BSU, BSEU, BSUIR !

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

Kattis also has a second mirror for the scoreboard (which looks nicer): http://static.kattis.com/icpc/wf2015/

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

ahmad aly scoreboard works for you? freezed on prematch!

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

tourist started to code and ITMO got 4 accepted in about 20 minutes. :D

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

Is there any website where you can submit and check your code? I thought Kattis is going to do this.

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

Go MSU, go! :D

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

    Maybe MSU will destroy the spell and will win?

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

I think ITMO is going to win this year :D

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

Will screencasts be available during freeze? If so, no intrigue for spectators.

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

U of Tokyo submits K. Does they get a balloon?

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

Somebody, freeze Petr, please.

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

    Hah, requesting new rule at ICPC — frozen Petr for one hour before the end :)

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

Looks like ITMO submitted one more. B problem. Its from video stream. And looks like this is the win.

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

WoooooooW......
Moscow State University solved problem M....

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

I think result of FINAL is following: 1. St.ITMO 2. Moscow SU 3. Tokyo University

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

Will tourist solve the problem "Tours"?

→ Reply
»
10 years ago, # |
  Vote: I like it -137 Vote: I do not like it
  1. ITMO
  2. University of Tokyo
  3. Moscow State University
  4. Peking University
  5. Tsinghua University
→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    "These results are not final!"

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

      Lets wait and see how different this is from the final top 5.

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

        ITMO then MSU then TOKYO ... Check petr's twitter .

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

          this is what petr wrote "It looks like top 3 are"

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

        now we see your result distant to right result equals:4 you calculate 20% of answer :P

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

Congratulations to ITMO!!! guess this is the first time that a team has got 13 balloons in the world finals

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

Have any dates for 2016 World Finals been announced?

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

    The 2016 World Finals will be held in Phuket (Thailand) on May 15-20, hosted by Prince of Songkla University.

    Source: Wikipedia

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

I'm not getting sound on streams, are others getting it ?

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

    No, they failed the most important part of the video cast =(

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

      Right.

      I was eagerly waiting for top 10, and then they give no sound, I've tried twitch as well, it's odd, they should look into this issue fast(er).

      UPD: Even the video is now fumbling(dunno if it's my bad internet connection). Also, Twitch has less lag as compared to Youtube, people should switch to that...

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

      Sorry about that. Separate production team was working on that and we were to exhausted to make sure everything was ok

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

        I didn't know you were working on a video cast. Isn't it a duty of a technical committee?

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

          I was on ICPC Analytics and somewhat on ICPC Live team. Although live team was not responsible for closing ceremony stream (local contractors were) we should have monitored that

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

Unfrozen scoreboard anywhere?

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

    2014 results still on official site. Team is probably busy with the dinner preparations :)

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

Moscow again 2nd :P

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

Was the next host announced?

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

Will the problems be in the gym ?

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

Oh, miss that so much...

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

Scoreboard is still frozen so here's its snapshot from Youtube video for those who're eager to know the medalists:

  1. St. Petersburg National Research University of IT, Mechanics and Optics
  2. Moscow State University
  3. The University of Tokyo
  4. Tsinghua University
  5. Peking University
  6. University of California at Berkeley
  7. University of Zagreb
  8. Charles University in Prague
  9. Shanghai Jiao Tong University
  10. Massachusetts Institute of Technology
  11. Korea University
  12. University of Warsaw
→ Reply
»
10 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Where can we see problem solutions?

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

Can somebody tell please, how to solve C?

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

    Min cost max flow — Build a graph with edges from i to i + j with capacity=1, cost=c[i][i+j] (given weight in input). Add an edge from Source to Node 1 of capacity=K and cost=0, self edges with capacity=1 and cost=-INF and an edge from all N+1 request nodes to Sink with capacity=INF and cost=0.

    Source — Youtube Link: Solution for Problem C

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

      xennygrimmato can u explain why we are making capacities of self edges with very high negative value and why the capacity from N+1 request nodes as INF and not K ?

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

      Nice trick of using -INF cost self loops that will force the flow unit to visit all the nodes but how can we compute the min cost max flow now? I mean now we have negative cycles so how can we force bellman-ford algorithm not using each self loop more than once?

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

        We need to split each vertex into 2. That way there are no loops, just an edge

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

    EDIT: Got the solution accepted. Thanks fhlasek for helping :)

    I constructed the graph this way:

    1. Consider the N+1 locations as nodes. Construct an edge from Source to Location 1, with capacity=K, and cost=0. Construct edges from Source to Locations [2..N] with capacity=1, and cost=0. Call the Source as Layer 1, and this set of locations as Layer 2.

    2. Consider a Layer 3, with N+1 nodes. We can consider Layer 2 to be Input Nodes and Layer 3 to be Output Nodes. As per input given in the problem, construct edges from Layer 2 to Layer 3 with cost(i, i + j)

    3. Construct edges from Layer 3 to Sink with capacity=1 and cost=0.

    Perform min cost max flow on this graph.

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

      Each vertex from 1 to N+1 can and must be visited only once in the final flow. Since it can be visited at max once, the vertex must have a capacity of 1, so for every vertex in [1,N+1] you will need 2 vertices with an edge of capacity 1 and cost -INF between them. The -INF cost makes sure that each of them is visited and the capacity 1 makes sure that it is visited only once.

      → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it +17 Vote: I do not like it

So tourist, VArtem and Enchom's sorry_dreamoon wins! :D

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

Now tourist = sorry_rng_58
:)

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

can some one explain how to solve problem C ?

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

tourist dancing :D

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

    Firstly better show us how you dance before posting such videos :P.

    → Reply