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

Автор ICPCNews, 3 года назад, По-английски

text

Hello, Codeforces!

ICPC World Finals Moscow will begin on October 5, 2021 at 8:30 (UTC+3). We are thrilled to invite you to join the live broadcast of the main event of the year in the world of sports programming!

For the very first time in October 2021, Moscow will host the world’s most prestigious competition for young IT talents, the ICPC World Finals Championship. The last International Collegiate Programming Contest has hosted over 60000 students from 3,514 universities in 115 countries that span the globe. October 5 more than 100 teams will compete in logic, mental speed, and strategic thinking at Russia’s main Manege Central Conference Hall.

Some useful links:

All available broadcast:

EN RU AR CN ES Snark

We wish good luck to all competing teams to have a great time spending, and to do the best to get amazing results!

  • Проголосовать: нравится
  • +552
  • Проголосовать: не нравится

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

We will continue questioning the three-computers rule.

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

It's so sad...I am under 18 so I can't enter.

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

    Grow up ?

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

    I know someone that went to WF at 16.

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

    Not sure what you guys are talking about here... My teammate is 15.

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

    If you are really good at this you could first participate in IOI...

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

      Yes, that's what I am aiming for. I really want to take part in 2023 IOI in Hungary representing Australia. Which means I need to be in the top 4 finalists next year.

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

    Is there a rule that people cannot enter it until 18 years old? I never heard that... Or it's the rule in your country?

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

      Maybe...I don't really know. When I wanted to register, it said you must be 18 years old or above.

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

        what a pity... but I'm 15 years old and I just register The 2021 ICPC Asia Shanghai Regional Contest in Nov.28 in icpc.global Are you a undergraduate or a high school student? In China, only undergraduate can be contestant.

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

Three-computers rule sucks.

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

I expect there will be some teams AK this match owing to the three-computers rule. They are really powerful, and sometimes they are limited by the rule that only one can use the computer.

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

They should have used 3 screen sharing monitors with a 3 common keyboard and mouse on same CPU.

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

AFK long time from Programming Contest, is anyone could explain to me what is going on? Is this WF2020 or WF2021? Is the contest hosting onsite or online? What about those teams that can't be onsite? Is anyone could make a brief sum-up to me? Thanks a lot.

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

    This is WF 2020. The contest is onsite and online, teams that are online aren't eligible for medals etc (Idk if it's a different problem set, don't remember).

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

Will there be a live scoreboard?

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

What is three-computers rule that everyone is talking about?

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

glhf to all teams. But mostly to MIT and sqrtdecompton

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

А вот это смешно!

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

scoreboard link isn't working!

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

where I can see the list of participants, with their nicknames etc?

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

It seems that the scoreboard is not working now.

UPD: now it's fixed

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

For those who didn't find Chinese teams on the scoreboard.

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

    so sad. They could literally be champion. Same goes for University of Tokyo!

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

    In fact, the isolation period is shorter than waiting for the next flight from Moscow to China(And such ticket exists.)

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

      This is true (international transits are forbidden and land borders are closed so the only way to return to China is essentially SU208/CA910/some other charter flights; the flights are regularly suspended due to the number of covid+ cases on board).

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

Go go Um_nik team

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

Um_nik wins!

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

Hooray for Um_nik!

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

anyonE knows when scoreboard Will be unfrozen?

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

Um_nik, KAN and Ekler wins!!!

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

It seems Nizhny Novgorod State University solved 12! Happy for them!

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

Um_nik wins!!!!!!!!!!!!!

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

Um_nik wins!

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

Is there any upsolving for this finals? Or when and where would it be published?

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

Where's the closing ceremony broadcast?

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

Чо, Бангладеш?

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

Wait, so did our university win any award from the invitational division? I thought our team failed to get into top 50% (rank 31/57), but then we are not in the honorable mention list (bottom 50% that solve at least 1 problem).

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

Orz ukraine

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

Um_nik team won !!!

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

Congrats, Ekler!

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

GAP

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

tourist was that u with itmo in the stage (°o°)

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

Moral of the Story —

Congrats Um_nik

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

Um_nik OTZ !

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

Credit: ICPC Live Stream, steven.novaryo for capturing the moment

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

It is mentioned in the schedule that "The ceremony will be covered by ICPC Live. Invitational awards will be announced here". However, only the honorable mention awards are shown in the livestream. So, how do the contestants supposed to know which prize they have won?

PS: Somehow, I suspect that the rest of the awards were shown DURING the time the camera pan to the contestants attending the ceremony.

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

    Don't know what happened

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

    the awards were revealed during the live stream. I think in last 1 hr of the contest.

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

    I found the scoreboard resolving of the invitational contest here (in case the timestamp skip does not work, it starts at 24:53)

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

      There are only 52 teams in resolver.(For example, no UESTC in the resovler.) But in the honorable mention list in the closing ceremony, the last unviersity is UESTC.(which is 57 teams version.) And it seems that Honors "25~50%" teams are not shown in the resolver and the closing ceremony. What happened?

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

Congratulation Um_nik, KAN, and Ekler for winning the 44th World Finals. It was very entertaining to watch the stream/contest and you truly deserved it!

They did not start very good ("only" 2 problems in the first hour, I did not remember seeing them at the top on the first 2 hours or so), but they fought back amazingly in the mid and end game.

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

Congratulations to Um_nik, KAN and Ekler

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

Congratulations to Um_nik and team on being the ICPC Champion.

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

tourist could be the best champion in the ICPC finals, but Um_nik is the most badass champion!

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

it was so beautiful i hope one day i can participate in it thx for every one participate to make the contest so beautiful

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

Congratulations Bangladesh University of Engineering and Technology (BUET) for becoming Asia west champion.

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

What are the statistics on 1cpc vs i3pc teams' results?

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

Congratulations to the team Almost Retired for the win!

BTW, while everyone is expressing their congratulations, nobody is talking about the problems, so I want to leave some comments and ask questions. Note that I'm not a participant of this WF and don't take my impression too seriously. I would like to hear opinions from onsite participants, since their words would be much more convincing.

First of all, I'm not a fan of this year's problem set. Problems ACDEFGJMO are too standard to me (and to medalist teams, I suppose). Of course, they have played a role in distinguishing other teams, but I felt 9/15 is too much. I suspect it's a consequence of the 3-computers rule, and I won't discuss this point further.

Okay, so let's look at the remaining problems, which was the decisive factor for medals.

Problem B: This one is what I got stuck on during the mirror, and here goes my story. After reading the statement, I immediately came up with the $$$O(n^2)$$$ time solution. However, that solution needs to store $$$n^2$$$ 32-bit integers in memory, which is around 1.6GB ($$$n \leq 20000$$$) and doesn't fit in the ML. After spending more than an hour, my teammate read the statement and immediately pointed out that we needed to store only $$$n^2/2$$$ integers, then we solved the problem. I want to know whether there exists a better solution than $$$O(n^2)$$$. If the answer is NO, I'd say the constraint is shit. Even if the answer is YES, the author failed to distinguish a model solution from shitty solutions, so that's an issue of another kind.

Problem H: I found this problem the most interesting in the set. Since we solved it using a randomized strategy without proof, I want to know beautiful deterministic solutions (I believe a good one exists).

Problem I: I'm surprised that so few teams solved this problem. To me, the problem was yet another easy standard one, but perhaps I was just lucky.

Problem K: I'm sorry, I didn't read the statement during the contest, and I assumed that this is just a careful implementation or something. Now I read the statement, but my mind didn't change. Please let me know if this problem is interesting, and in that case, I'd apologize.

Problem L: If we have an ultra-precision (and super fast) floating number, this problem is not that hard. One may say that handling precision errors carefully is a kind of algorithm, but I don't like it. Since we couldn't solve this problem, there might be a good solution, though. (and again, if that's the case, I'd apologize.)

Problem N: I wouldn't say I like this problem, but it's my personal preference, so put this aside.

Overall, I feel (average CF Div.1)*3 would be a better problem set than this WF in terms of quality. I do know it's hard to make a lot of problems. However, since ICPCWF is the most famous and prestigious contest for university students, I can't help hoping that they have the most interesting and challenging problems.

Anyway, thank you for holding the contest, and I'm looking forward to participating in ICPCWF 2021!

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

    B is possible to do in $$$O(n \sqrt n)$$$ memory. Take an integer $$$B \approx \sqrt n$$$. Partition the nodes wrt depth modulo $$$B$$$ and precompute answers for the nodes in the smallest group ( it'll have size $$$O(\sqrt n)$$$) in reverse order of depths, and the recursion depth will always be $$$O(\sqrt n)$$$.

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

      That's what we did in the end as well. BTW 1,6GB was enough as the memlimit was 2GB, I think.

      According to bicsi, if you do this trick in a HLD-way, you can have n log n memory complexity.

      ICPC has a philosophy that sometimes you need to optimize to solve the problem, that not always it's crystal clear whether your solution passes or not. While in shortest contests it would be mildly annoying, I don't mind giving a challenge of this sort in a 5h icpcpcpc. Same applies to floating point manipulation. To me it sounds fair that many different skills are occasionally checked by icpc, especially to distinguish the good teams from the best ones. Same with epsilon hacking — I like when problems require deeper understanding of the underlying theory. Though it's a while since I last saw a problem like that, for example requiring mathematical analysis of epsilons and possible errors, and trying to figure out a way to fight against that.

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

    I am very happy with the problemset, perfectly balanced as all things should be. It favoured well-prepared, all-rounded teams. I don't think that 5 counting, 5 adhoc and 5 binary search problems would be a better one.

    Problem I was quite easy but probably the time of first solve determined how many accepts it had. Looked a bit hard at first glance and many teams thought of complicated solutions, I suppose.

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

    An easy to code $$$O(n \log{n})$$$ memory solution B:

    • The dp state is something like $$$dp_{v,w} = const + \min(\sum dp_{child, w}, c * deg_v$$$), you can compute sum over children first and then take minimum with the constant.
    • When we process the very first child, we add its $$$dp_{c,*}$$$ to virtually an array of zeros that we have in the current vertex at the beginning. But let's just tell $$$c$$$ to store its state directly in $$$dp_{v,*}$$$ rather then $$$dp_{c,*}$$$.
    • For the subsequent children we store data more or less like usual and add it to our $$$dp_{v,*}$$$.
    • We can implement it as follows: in dfs pass an index of $$$dp$$$ array to store the result to. Suppose we have index $$$k$$$ in $$$v$$$. Then for the first child we pass $$$k$$$, for the other children we pass $$$k+1$$$.
    • Now, if we always choose child with the largest subtree as the first one, the maximum value of $$$k$$$ that we will get is bounded by $$$O(\log{n})$$$.
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +71 Проголосовать: не нравится

    I agree with almost all of your points.

    It seems that authors were scared that with 3 computers we will be able to code a lot more problems, but it doesn't translate to "we will be able to read a lot more problems". 15 was waaaay too much, and yes, most of the easier problems feel like filler (for medalist teams). The problem is you have to write even filler problems, and you can be stuck in debug even in filler problems, and that's not great. First two hours we were just trying to write everything that was opened on the scoreboard, once in a while looking up on the wall (where the scoreboard was) and saying 'alright, there are 3 more open problems, let's read those'. Also the spectators were cheering for first AC in the first half an hour, that was a bit demoralizing, as we hadn't have written any code by the time 4 or 5 problems were opened. We haven't read any of the 5 "harder" problems till the middle of the contest, and we haven't even had time to discuss them properly. In the end, when we got I accepted, we have thrown away K and N just on basis of "they sound weird and complicated, and we don't have time to think about all the problems, while we have some ideas for H and L". Like, I don't even know the statement of K, I just looked at the picture and said NO.

    B: Yep, that was actually the first problem we discussed, as $$$O(n^2)$$$ seems obvious, I even started to write it, but then "wait, I need $$$O(n^2)$$$ memory, probably that's what the problem is about. And for some reason I thought that ML is 1 GB. Then I have come up with $$$O(n \sqrt{n})$$$ memory, while writing it I have come up with $$$O(n \log n)$$$ memory, but decided to stick with $$$n \sqrt{n}$$$.

    H: Cool problem, but... Grind AtCoder. WF version is harder, but I knew the main ideas, and the rest was some randomization and a bit of pushing.

    I: Just monitor effect. No teams found it early, and then everyone was trying to solve the problems that were already opened.

    L: SnapDragon said that our solution is way too unstable, so I don't think ultra-precision helps. KAN had a correct idea of what to do instead, but I dismissed it because of being too slow, and he did not prove me wrong, so that's my fault totally.

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

      Thanks for the reply. I'm relieved to hear that you feel similar things about the problems.

      BTW, Did B has 2GB ML onsite? Kattis said 1GB. Anyway, $$$O(n \log n)$$$ memory solution by egor_bb was nice, so it would have been better if the ML had been much smaller.

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

        I think there are no MLs on WF other than the actual memory of the computer, which was 2 GB onsite apparently, so it wasn't possible to set lower ML, but they could have set higher limitations and higher TL.

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

      How to do L?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Don't open if you plan to solve this WF in the future
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          Rev. 2   Проголосовать: нравится +62 Проголосовать: не нравится

          I was the author of L. The original intended solution was indeed to apply a "deconvolution" to the full set of mines T to get the distributions S and T\S. That's why the problem seems tailor-made for that kind of solution. Unfortunately, numerical stability is a huge issue for particular distributions. If we'd added a random-data guarantee like problem N, I think Um_nik's solution would have been fine.

          I doubt arbitrary-precision math would help, as it would be too slow. We know two ways to solve the problem with doubles:

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

            Yep, the second solution is what KAN proposed. It's a cool problem nevertheless, one of the better problems of this problemset, so thanks :)

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

      The real source of H is a problem from Chapter 4 of Cormen's Introduction to Algorithms.

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

    Interesting fact — problem I was considered by jury as 4th easiest in the set (after E, A and O)

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

    And yes, there is a very nice deterministic solution for H, but I do not have stamina to describe it again after describing it in Russian in comments on Um_nik telegram channel

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

How old is Um_nik? If anyone could tell me please. Also, Is there an age limit for participating in ICPC or we just have to be university students?

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

    I'm 25. Yes, there is an age limit, but it was applied when the finals were planned for June 2020.

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

      What is the age limit? 23? By the way, congrats. You're a legend.

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

        It's not exactly age limit, you should be born in a year not earlier than $$$X-C$$$ where $$$X$$$ is the year of the finals and $$$C$$$ is some constant. I'm pretty sure that was my last season by age, so $$$C$$$ should be $$$2020 - 1996 = 24$$$.

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

I saw "Utrecht — Leiden University" in the scoreboard representing two different universities: Utrecht University and Leiden University.

It confused me a bit first, but then I looked into the rules.

I see "A student may compete for only one institution during a contest year" (student -> one institution) and "Only one team from a given institution may advance to the ICPC World Finals" (institution -> one team) in the rules.

I don't see anymore in the rules something like "A team should always be affiliated with one institution" (one team <-> one institution) that would prevent to have a team representing two(three) universities.

Is it true that such behavior is allowed from now on?

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

    I was on a coaches' Zoom meeting with Bill Poucher in August, immediately after the WF formula was announced. If I recall correctly, the Dutch coach (responsible for both Utrecht and Leiden teams), said that because of pandemic-related issues only 2 people from Utrecht is able to go to Moscow, and only 1 from Leiden. He asked if a one-time merge of teams would be allowed. Bill's answer to that was something along "normally it wouldn't be, but this is an exceptional year, so we will allow it this one time".

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

World Finals standings are now available at Competitive Programming Hall of Fame: https://cphof.org/standings/icpc/2020
In case you find some errors there, please let me know.

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

Will there be an editorial (or is it already published somewhere)? It would be nice to check whether intended solutions are simpler for some problems.

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

Kinda off topic but they mentioned in the livestream that the next World Finals will be in November 2022. Anyone know the reason(s) behind this delay? You'd expect them to hold it sooner to try to catch up since that's technically the 2021 Finals.

Are the 2021 Regionals not over for everyone or are they planning to merge two years again? Hope not.

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

    As I understand Bill announced during RCD meeting that there would be double World Finals in 2023 (i. e. 2 contests in the same location one shortly after another, not a merged contest)

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

Congrats to the winners!

There will be a mirror of WF here on Codeforces?

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

When will the test data be made public?

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

ICPC world final mirror means Petr, tourist, Endagorion (1) also go to Onsite i mean Moscow ? and (2) solve problem with parallel to other finalist?