gKseni's blog

ICPC World Finals 2018
By gKseni, 7 years ago, translation, In English

ACM-ICPC World Finals 2018 will begin on April 19, 2018 at 2:00 (UTC). This event is the main event of the year in the world of sports programming!

In the past 20 years alone, ICPC participation has increased by more than 2000%. Last year, ICPC Regional participation included 49,935 of the finest students and faculty in computing disciplines from 3,098 universities in 111 countries on six continents. A record 53,446 students and 5,411 coaches competed in ICPC and ICPC-assisted competitions last year, setting new records in participation.

Codeforces wishes the teams to show a vivid and interesting contest. We wish to find beautiful solutions, write without bugs and enjoy many accepted problems!

Links:

ACM ICPC World Finals 2018 English Broadcast:
ACM ICPC World Finals 2018 Chinese Broadcast:
ACM ICPC World Finals 2018 Arabic Broadcast:
ACM ICPC World Finals 2018, Split screen:
Broadcast from legends: Petr, tourist, Endagorion:
Watch the live translation on twitch.tv
Broadcast from legends: jqdai0815, rng_58, FizzyDavid:
Watch the live translation on live.bilibili.com
2018 ICPC World Finals, Closing ceremony:
  • Vote: I like it
  • +582
  • Vote: I do not like it

Comments Comments (78)
| Write comment?
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

ACM ICPC World Finals 2018 is been an amazing experience so far thanks to hard and good work of ACM!

Good luck to every contestant at the contest, hope we all can do our best!

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

Does the contest start at 1:00 UTC? The link shows that it starts at 2:00 UTC

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

    I think it starts at 2:00 UTC, since in the official schedule there is an entry like "Contestants enter contest area", from 1:20 UTC to 1:40 UTC

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

All Jordanians wish luck to you and your team Hiasat :)

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

ICPC is my aim, my destiny, my happiness...

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

Is it rated?

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

bilibili.com instead of Twitch because of Great Firewall of China?

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

    Twitch is not really blocked. It's just slow and maybe sometimes unstable, but that's true for almost all foreign sites. Also I think non-English streamers generally don't like to use Twitch.

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

May be someday I become live at of Olympics of programming :p

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

Will there be a mirror contest somewhere to try the problems?

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

    On http://online.acmicpc.org you can try this year's problems on a copy of the our submission system. It will be available 15 to 60 minutes after the start of the contest.

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

that feeling, when you suppose that battle between two teams of LGMs will be much hotter than the one among official contestants.

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

Is It Rated?

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Best of luck Dracarys and TeamX from BUET and SUST respectively. Hope you will do something special in ranklist. Bangladeshis eyes are on you.

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

I wonder if there are any online mirror contests today.

BTW, good luck to all the participants !

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

Watch the live translation on twitch.tv

PepeHands

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

Solutions analysis can be found in https://icpc.baylor.edu/finals-solutions-2018/.

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

    I was just trying to rickroll everyone :(

    Codeforces: Y U NO LET ME RICKROLL?!

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

Problem Set

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

Congratulations to Moscow SU!

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

It is a common knowledge that naive O(n3) algorithm for computing Voronoi diagrams in practice works in something like O(n2), but I've never heard any proofs. I managed to get OK on G with it. Does anyone know any proof of this fact? It seems very logical and intuitive, but I'd like to know a strict proof.

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

    A relatively simple voronoi diagram algorithm is just n^2 log n using a stack for everyone point and sorting the bisecting lines around it. I just used my Delaunnay triangulation code to build the voronoi diagrams in n log n then clip the polygon with it.

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

i am wondering what colorscheme of msu's vim???

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

Moscow SU has solved 9 problems and it seems won the World Finals!

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

They have a huge bug!

If a university appears more than once, it means that all but the last submissions are not correct (otherwise they don't show them in the list of pending runs).

Did anyone else notice that?

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

    Nice catch

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

      Any information about where next WF is going to be???

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

        India

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

        According to this blog post, it will be held in Kochi (India).

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

        I heard it will be in Portugal, but it is not announced officially yet

        → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it -27 Vote: I do not like it

        There has not been any official announcement during the closing ceremony. According to Bill Poucher, the most likely place is Porto, followed by Russia and the Black Sea.

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

        I had a quick chat with Bill Poucher. It is far from official, but Portugal, Russia, Jordan and Australia are all within the realm of possibilities (in no particular order).

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

So many issues with the system and in general, the ceremony. What a disgrace.

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

Breaking news!

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

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

Which problems are set by SnapDragon, if any?

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

Go Moscow Go!
Congratulations Lomonosov University!
Sad for Warsaw University and ITMO.

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

where i can find a tutorial? Is there some available?

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

I will never understand the person who makes them all act like that in the video introducing the teams.

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

    Teams are asked to be happy / celebrate something for a few seconds. It's supposed to be shown in the broadcast when a team solves a problem.

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

      Oh, so they have no justification for the awkwardness :D

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

        Well, some teams (including mine) got a description along the lines of: "Alright now do a goofy one, like move your hands around or something." Pretty much impossible not to be awkward with that description.

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

Where will be the next world finals ?

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

Sad for ITMO :(

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

Where's an Editorial of WF Tasks??

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

    I assume Per and Onufry will post their usual solution sketches soon, and hopefully ICPCNews will post videos. I put my solutions from test-solving up here, but note that they're not always optimal (or even good) algorithms. :)

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

      I would say the problem set was not that interesting as it could be. Do you consider adding new strong authors to judges? I think NEERC problemset, for example, was more interesting and balanced, although the world finals is a more prestigious competition.

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

        World Finals have comporatively open problem proposal stage

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

          How does one participate in it?

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

            Call for problems is sent around September, all TDs at the very least should receive it and are free to forward it to anyone

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

              So nobody sends them interesting problems, or they declined almost all of them in this year?

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

                I do not think problems were bad or uninteresting, I think they are not so good as a set

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

                  IMHO they should invite several experienced sp in judge team, not caring about suggested they problems or not. Current judges easily could add to problemset well-known problem or choose bad TL.

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

                  I would say Per Austin, SnapDragon and onufryw are experienced enough to name a few. I do not think there was a year recently where judge team had not included several well known names in community

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

                  I don't agree. Both of them are good as authors of problems, but they are not on the edge now. I am sure that they haven't seen recent opencup, codeforces, topcoder, codechef, hackerrank, hackerearth etc problems.

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

    The solution sketches and analyst solution videos have been posted.

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

      Problem C is very cool, but... Did someone expect C or J to be solved during the contest? If not, what's the point in making contest on 9 problems only?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 4   Vote: I like it +8 Vote: I do not like it

        C is actually not hard "merge-sets"-kind problem. I had correct solution idea during the contest, but with our problems with other tasks we had no chances to implement it (and we were a bit afraid of trying, because nobody did it).

        It seems that the editorial describes the same solution, but in a bit hard way. My idea was to keep pathes to the positive sources that are used, and are not used, in two multisets, with values equal to cost of using that sources or removing that sources. It's actually like a fast simulation of mincost-flow on the tree. The implementation is really simple: https://ideone.com/4NOAx0 . Btw, with Pairing Heap it will be .

        And I do not understand why none of the top teams solved it.

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

          Hm, yes, we had a similar idea, but didn't have time to think it out. Now the problem doesn't seem that hard. I think the reason top teams did not solve it is quite similar to yours — previous by hardness tasks required careful implementation and quite a lot of debugging.

          Btw, in Russian translation there was information from the judges, that two hardest problems would most probably remain unsolved — so it may have been done intentionally.

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

        We knew that Problems C and J were the two hardest in the set. I can't speak for all the judges, but I did expect some of the top teams would be able to solve C. Of course, the dilemma is always whether it's worth it to try a hard problem nobody else has solved when you've still got one of the 9 proven problems to work on.

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

      In explanation of J had volume up two times. Was it possible in J to bruteforce an answer by sending hundreds of solutions with different formulas?

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

Can someone please describe how they constructed the required tree for Problem K?

The solution video for problem K doesn't explain clearly how the resultant tree is supposed to be constructed.

I was thinking of an approach where we first add edges for vertices with degree 1, and then keep adding edges in increasing order of degree until the required sum of degrees is reached. We ensure that no cycles are formed using DSU. I don't have a proof for whether this would work or not.

Another approach that I had in mind was to iterate through nodes in decreasing order of degree and remove edges one by one ensuring that:

  1. the graph is connected
  2. sum of degrees is 2(N - 1)

I have no idea about how we should decide which edge to remove at each step. Petr, in his live stream, also seems to use a similar approach. He did not use DSU but said something like there is no chance of the graph getting disconnected in any case — but that part wasn't very clear in the stream.

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

    I would suggest looking at this.

    There are two ways to construct the tree that I know of.

    The first way: take a node with degree one and connect it to the node with the highest degree at the moment. Decrease the degrees accordingly and repeat n - 1 times. There are two observations that make this possible. The first is that if we are given that a tree can be built, then there is a node with a degree of one. That's because if there were no nodes with degree one then the sum of degrees would be at least 2n while any tree has degree sum of 2n - 2. The second is that after connecting that edge, we have a new degree sum of 2n - 4 = 2(n - 1) - 2 meaning that we reduced the problem to building a tree on n - 1 nodes which we assume can be done (the inductive argument should be made the other way round but I will omit it since it is of little relevance).

    The second way: sort the nodes in decreasing order of degree. Make the first one the root. Maintain a list of "available" nodes that can still have neighbors. On each step take the next node and connect it to a node from the list. Reduce the degrees appropriately, remove a node from the list, and add a new node to the list if necessary. It's not hard to see that after each step the graph on the processed nodes is indeed a tree. We are left to show that on each step the list of "available" is non-empty. Assume it is empty, that means that on the previous step we added a node with a degree of one since, otherwise, that last added node would have been added to the list of "available" nodes after reducing its degree by one. Since we sorted the degrees, that means the rest of the nodes that have not been processed have a degree of one as well. Let's say that we processed k nodes so far. Since those k nodes form a tree and there are no "available" nodes among them, the original sum of their degrees is 2k - 2. The sum of the rest n - k nodes is n - k because each of them has a degree of one. So the total degree sum is n + k - 2. Observe that n + k - 2 < 2n - 2 whenever k is not n. That means that the only time that the list of "available" nodes becomes empty is when k = n meaning that we have processed the whole tree.

    The first solution, in my opinion, is easier to understand. However, the second one is easier to code.

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

    My solution: Solve the case N ≤ 2 manually. Otherwise there is at least one non-leaf vertex and at least two leaf vertices. Take all non-leaf vertices and form a chain. Then, to each vertex in a chain, connect enough leaves to it to increase its degree.

    → Reply