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:
- Official website of the ICPC
- Official world finals website
- Schedule of Events
- Live broadcast
- ICPC World Finals Mirror (Endagorion + Petr + tourist)
- Scoreboard
- Problem set
All available broadcast:
We wish good luck to all competing teams to have a great time spending, and to do the best to get amazing results!
We will continue questioning the three-computers rule.
Or it will be I-three-PC
I3PC looks much better.
T1duS
I copied from AC
I can confirm
You can simulate a one computer setup given three computers by ignoring the two computers; so you can apply your favorite one computer strategy with zero negative effect on your performance!
My team liked the setup, we solved 3 problems, 1 per computer!
It's so sad...I am under 18 so I can't enter.
Grow up ?
I know but for 3 more years????
I know someone that went to WF at 16.
Not sure what you guys are talking about here... My teammate is 15.
If you are really good at this you could first participate in IOI...
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.
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?
Maybe...I don't really know. When I wanted to register, it said you must be 18 years old or above.
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.
I am a high school student, ;)
Oh, so just work hard in OI and try to take part in IOI!
Three-computers rule sucks.
why?
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.
They should have used 3 screen sharing monitors with a 3 common keyboard and mouse on same CPU.
Yes, but... They didn't think about it.
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.
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).
Will there be a live scoreboard?
Yes, here: https://pc2.ecs.baylor.edu/scoreboard/
Its not working
Public scoreboard is unstable. I'm constantly getting [PR_END_OF_FILE_ERROR].
What is three-computers rule that everyone is talking about?
You can see this blog.
glhf to all teams. But mostly to MIT and sqrtdecompton
I love sqrtdecompton but I think the most good luck and having fun should go to SecondThread, Xylenox, and Harpae.
Sure, i like them too. They can have the luck. sqrtdecompton Can have the fun
https://docs.icpc.global/icpcMoscow.pdf
А вот это смешно!
scoreboard link isn't working!
where I can see the list of participants, with their nicknames etc?
https://codeforces.com/blog/entry/73791
It seems that the scoreboard is not working now.
UPD: now it's fixed
For those who didn't find Chinese teams on the scoreboard.
so sad. They could literally be champion. Same goes for University of Tokyo!
In fact, the isolation period is shorter than waiting for the next flight from Moscow to China(And such ticket exists.)
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).
Go go Um_nik team
Um_nik wins!
Common, the team wins! KAN and Ekler are also the champions!
seems like Um_nik's wife has won. Congratulations to her!
You remember right the last time u wrote this what had happened...
I do not care about downvotes man.
Congratulate them!
Hooray for Um_nik!
anyonE knows when scoreboard Will be unfrozen?
Um_nik, KAN and Ekler wins!!!
Congratulate to Almost Retired!
hmm. Is this the first time with female participant in top-1 team? Congratulations
Not the first time https://icpc.global/community/history-icpc-2011
It seems Nizhny Novgorod State University solved 12! Happy for them!
Please update problem ratings.
IMO this isn't a proper place to discuss it.
Um_nik wins!!!!!!!!!!!!!
other teams also have 2 pendings. How u r so sure that they won?
ps. i'v just finished rewatching live broadcast. UNN wins. Congrats.
How could um_nik win! He pretends he doesn't know anything :D :D.
Why anything. I know something.
Um_nik wins!
Is there any upsolving for this finals? Or when and where would it be published?
https://icpc.kattis.com/
Where's the closing ceremony broadcast?
https://www.youtube.com/watch?v=BPZQcGqmroE&ab_channel=ICPCLive
Чо, Бангладеш?
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).
Orz ukraine
Um_nik team won !!!
Congrats, Ekler!
Congrats, KAN!
Congrats Um_nik and KAN .
LMAO why my comment is getting downvoted? Errichto only congratulated one team member of the winning team, so I congratulated the the other 2.
Because you didnt get it
Her part in the win is the biggest!
Lol
GAP
tourist was that u with itmo in the stage (°o°)
Moral of the Story —
Grind Atcoder
Congrats Um_nik
Um_nik OTZ !
Credit: ICPC Live Stream, steven.novaryo for capturing the moment
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.
Don't know what happened
the awards were revealed during the live stream. I think in last 1 hr of the contest.
I found the scoreboard resolving of the invitational contest here (in case the timestamp skip does not work, it starts at 24:53)
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?
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.
Congratulations to Um_nik, KAN and Ekler
Congratulations to Um_nik and team on being the ICPC Champion.
tourist could be the best champion in the ICPC finals, but Um_nik is the most badass champion!
it was so beautiful i hope one day i can participate in it thx for every one participate to make the contest so beautiful
Congratulations Bangladesh University of Engineering and Technology (BUET) for becoming Asia west champion.
What are the statistics on 1cpc vs i3pc teams' results?
Wdym? Nobody competed with 1PC?
https://codeforces.com/blog/entry/94690
it didn't
Huh. Looked to me like it did. Nobody spoke against it in the comments, there were multiple teams committing under that condition... what was needed?
At least Seoul NU and MIT
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!
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)$$$.
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.
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.
An easy to code $$$O(n \log{n})$$$ memory solution B:
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.
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.
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.
How to do L?
One cell with probability $$$p_i$$$ is $$$((1-p_i) + x p_i)$$$. To answer the query it would be nice to have multiplication of these binomials for query set and its complement. The first one is easy to get in $$$O(s^2)$$$ per query, which is fine, so the issue is in calculating the second.
One obvious idea would be to calculate the product of all binomials first, and then divide the resulting polynomial by query set which is small. That would take $$$O(WH \cdot L)$$$ time to precalculate (if no FFT is used) and $$$O(Ls)$$$ per query, where $$$L$$$ is the degree of polynomial, which seems to be $$$WH$$$ obviously... but it isn't. This is a reasonable probabilistic distribution, so it is concentrated around its mean (Central limit theorem or something, I don't know probability), so if we only leave something like $$$10 \sqrt{WH}$$$ coefficients around the mean, all the rest are basically zeroes.
So that's what we have written. It doesn't pass. Multiplication is fine because all the coefficients are non-negative, but when doing division we will have to do subtractions, and this sucks. I can't really explain why, but it is too unstable.
I'm not sure about the next part, but in a nutshell instead of division we want to multiply everything but query set again. Let's do something like dynamic connectivity offline, with turning off query set and then turning them on again.
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:
First, as Um_nik noted, you can limit your distributions to a certain window around the mean, because Central Limit Theorem something something. :) The probabilities get exponentially small far from the mean.
Solution 1: In the Fourier domain, you can divide FFT(T)/FFT(S) to get the "deconvolution" FFT(T\S). However, because of the division, your distribution FFT(S) must be very accurate, even though the coefficients have small magnitude. So you can't actually apply FFT (which involves a lot of additions/subtractions) directly to S. Fortunately, the Fourier coefficients of a single-mine distribution are simple: $$$(1-p)+p\omega$$$ for roots of unity $$$\omega$$$. If you multiply those directly you'll get FFT(S) without the risk of catastrophic cancellation while subtracting. You can do the same for FFT(T) since it's only computed once. So you compute FFT(T)/FFT(S) directly, and the only FFT you actually end up running is to recover T\S, once per query.
Solution 2: Despite my best efforts, you can cheat and turn it into an offline problem. :) Put the queries into the leaves of a balanced binary tree; mark each node with the list of mines in its subtree; mark each edge with the mines present in the parent but not the child. Then you start with the distribution of mines appearing in none of the queries, and traverse from root to each leaf, adding in the mines marked on each edge. You'll end up additively producing all the distributions T\S, adding around log(q) * (# of mines across all queries) mines in total.
Yep, the second solution is what KAN proposed. It's a cool problem nevertheless, one of the better problems of this problemset, so thanks :)
The real source of H is a problem from Chapter 4 of Cormen's Introduction to Algorithms.
Interesting fact — problem I was considered by jury as 4th easiest in the set (after E, A and O)
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
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?
I'm 25. Yes, there is an age limit, but it was applied when the finals were planned for June 2020.
What is the age limit? 23? By the way, congrats. You're a legend.
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$$$.
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?
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".
Thanks! The confusion is eliminated.
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.
Any chance you can add the WF Invitational as well? (standings)
Yes, sure. I'm going to add it this week as well.
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.
Most problems solution outlines would be uploaded shortly to ICPC News YouTube channel
Cool thanks
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.
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)
Congrats to the winners!
There will be a mirror of WF here on Codeforces?
When will the test data be made public?
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?