19-го апреля 2018 г. в 05:00 (московское время) начнется главное событие года в мире спортивного программирования — финал командного студенческого чемпионата мира ACM-ICPC 2018!
Позади открытие и пробные туры. 140 команд со всего мира собрались в Пекине (Китай), чтобы определить — кто из них станет чемпионом мира, кто получит медали чемпионата.
Масштаб проведения чемпионата этого сезона поражает воображение. Всего во всех отборочных этапах чемпионата приняли участие 49935 студентов из 3098 университетов 111 стран мира 6 континентов! В этом году стран стало на 8 больше! В зависимости от региона команды прошли квалификации, четвертьфиналы, локальные отборы, региональные соревнования. Лучшие 140 команд приехали в Пекин для участия в Финале.
Болейте за своих земляков, любимые команды и просто сопереживайте участникам!
Codeforces желает командам показать яркий, интересный, полный борьбы контест. Желаем находить красивые решения, писать без багов и побольше радоваться решенным задачам!
Болеем по ссылкам:
- Текущие результаты
- Официальный сайт чемпионата
- ICPC News (фото, видео о Финале)
- ICPC Live (трансляции и не только)
Смотреть прямую трансляцию на twitch.tv
Смотреть прямую трансляцию на live.bilibili.com
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!
Does the contest start at 1:00 UTC? The link shows that it starts at 2:00 UTC
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
Полируем щиты, вспоминаем названия смайлов твича, достаем заготовки с гусями...
All Jordanians wish luck to you and your team Hiasat :)
Good luck Hiasat :)
ICPC is my aim, my destiny, my happiness...
Is it rated?
This is the first time i am upvoting this question :))
Respect to the originals.
http://mirror.codeforces.com/blog/entry/44943#comment-294851
bilibili.com instead of Twitch because of Great Firewall of China?
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.
Все ведь помнят, что континенты это Евразия, Северная Америка, Южная Америка, Австралия, Африка и Антарктида? Кто из последнего? =)
Все ведь помнят, что "континент" — это не "материк", и их можно делить по-разному =)
May be someday I become live at of Olympics of programming :p
Will there be a mirror contest somewhere to try the problems?
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.
that feeling, when you suppose that battle between two teams of LGMs will be much hotter than the one among official contestants.
Is It Rated?
?detaR tI sI
Best of luck Dracarys and TeamX from BUET and SUST respectively. Hope you will do something special in ranklist. Bangladeshis eyes are on you.
I wonder if there are any online mirror contests today.
BTW, good luck to all the participants !
PepeHands
Жаль, что из-за буйства РКН твич работает не у всех и не всегда.
Solutions analysis can be found in https://icpc.baylor.edu/finals-solutions-2018/.
I was just trying to rickroll everyone :(
Codeforces: Y U NO LET ME RICKROLL?!
Problem Set
Congratulations to Moscow SU!
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.
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.
i am wondering what colorscheme of msu's vim???
Moscow SU has solved 9 problems and it seems won the World Finals!
No more Moscow Secondplace University:)
Где можно найти ссылку на церемонию закрытия?
Вот она! И в пост добавлю, спасибо! https://www.youtube.com/watch?v=Q2tKpmsmhgo
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?
Nice catch
Any information about where next WF is going to be???
India
According to this blog post, it will be held in Kochi (India).
I heard it will be in Portugal, but it is not announced officially yet
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.
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).
So many issues with the system and in general, the ceremony. What a disgrace.
What kind of issues happened?
Breaking news!
Congrats UCF!!!
Which problems are set by SnapDragon, if any?
The ones nobody solved. :(
Are the problems' authors public information?
Go Moscow Go!
Congratulations Lomonosov University!
Sad for Warsaw University and ITMO.
where i can find a tutorial? Is there some available?
I will never understand the person who makes them all act like that in the video introducing the teams.
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.
Oh, so they have no justification for the awkwardness :D
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.
кто знает какой у Макеева рейтинг в дотке?
Where will be the next world finals ?
Porto, Portugal
did they actually declare that?
No, it is not official yet.
Told you
Sad for ITMO :(
There are no ups without falls..
Where's an Editorial of WF Tasks??
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. :)
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.
World Finals have comporatively open problem proposal stage
How does one participate in 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
So nobody sends them interesting problems, or they declined almost all of them in this year?
I do not think problems were bad or uninteresting, I think they are not so good as a set
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.
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
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.
The solution sketches and analyst solution videos have been posted.
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?
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.
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.
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.
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?
А нельзя в русскоязычную трансляцию поставить человека, который не будет оскорблять коллег-участников из своего же университета? Ну и, если получится, который хорошо разбирается в том, что комментирует?
Александр, я с удовольствием готов выслушать Ваши претензии, но агрументированные, чтобы я мог что-то подправить. Лучше сделать это в личку.
.
Я просто хочу отметить, что трансляции, в особенности неанглоязычные, предназначены не для участников, а для тех, кто хочет информированно поболеть. Если убрать из трансляции все эмоции, то она станет бесконечно скучна
Оскорбления и неверные-некорректные выводы =/= эмоции
Я не считаю "пролетели как фанера над Парижем" оскорблением. А неверные выводы, конечно, будут в любом случае
Где этот момент был? Мне просто лень весь видос просматривать
Я сам русскую трансляцию не смотрел, был в этот момент немножко занят :)
"Е лёгкая, все дебилы, что не решили" -- пусть комментатор и цитировал кого-то другого, всё же можно было бы сделать это и не дословно
Да, тут, пожалуй, жестковато. Но это вопрос стиля, и у Виталика он, безусловно, есть
Лично мне в трансляции не понравилось скорее то, что ведущий активно поддерживает команды из региона Northern Eurasia, а успехи других команд, наоборот, комментирует так, как будто это что-то нежелательное. Мне кажется, что ведущий трансляции должен быть более нейтральным.
Ну и называть в официальной трансляции мирового чемпионата Виталика Виталиком как-то несерьёзно.
Это было by design — участники языковых трансляций должны были болеть за своих. Английская студия была рядом с китайской, и мы чуть не оглохли, когда Пекин вышел в лидеры
Воспринимать Виталика серьезно вообще очень трудно.
В русскоязычной трансляции понравелись коментаторы. Только девушка не так хорошо коментировала. Классно, что трансляция вообще существует, и процесс кодирования показывают, и как команды ожидают вердиктов.
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:
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.
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.
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.