Всем привет!
После долгой череды региональных онлайн-отборов и ожидания, мы рады объявить, что в эти выходные 3-4 апреля состоится оффлайн-этап Финала Северной Евразии, полуфинала ICPC 2021!
Трансляция от ICPCLive Таблица результатов
Зеркало Условия задач Разбор задач
В декабре 2020 по результатам онлайн-тура чемпионата из почти 330 студенческих команд были отобраны и приглашены 50 (об этом мы подробно рассказывали здесь). Большая часть команд приедет соревноваться в Санкт-Петербург, но из-за ограничений перемещения между странами некоторые команды будут соревноваться на площадках в Минске, Тбилиси и Риге.
Будем внимательно следить за первенством и оперативно рассказывать о главных новостях. Ссылки на таблицу результатов, задачи контеста, зеркало и разборы постараемся размещать по мере их публикации на официальном сайте.
UPD на данный момент в финал ICPC 2021 выходят следующие команды:
- SPb ITMO: Insert your name (Budin, Korobkov, Naumov)
- HSE: Overtrained (Gorokhovskii, Safonov, Rakhmatullin)
- Moscow SU: Nonames (Koshelev, Chunaev, Kalendarov)
- St. Petersburg SU: LOUD Enough (Bochkov, Makarov, Gaevoi)
- Saratov SU: N (Petrov, Piklyaev, Meshcheryakov)
- SPb HSE 1: Lemon Tree (Makhnev, Surkov, Alferov)
- Belarusian SU: 3 (Klimasheuski, Paliukhovich, Filinovich)
- Moscow IPT: LinkCat (Zgursky, Gaponov, Surkov)
- Kazan FU: AJ (Ilikayev, Yagafarov, Kapralov)
- NNSU: 1 (Khlyustov, Ryabchikova, Emelin)
- Tolyatti SU: A (Zakharov, Sabirov, Panin)
- IITU: 1 (Baimukanov, Sardarbekov, Kyzyrkanov)
Также присоединяйтесь к традиционной онлайн-трансляции всех главных ивентов с площадки в Санкт-Петербурге, которая будет организована силами команды ICPCLive на нашем YouTube-канале. Расписание обоих дней можно найти здесь.
Мы составили список команд с их суммарным рейтингом, следить за которыми будет особенно интересно. Ваши прогнозы? Фавориты?
| Команда | Участник 1 | Участник 2 | Участник 3 | Рейтинг |
| HSE: Overtrained | Рамазан Рахматуллин never_giveup | Максим Гороховский Maksim1744 | Иван Сафонов isaf27 | 8672 |
| SPb SU: 25 | Егор Горбачев peltorator | Семен Петров Semenar | Дмитрий Беличенко Dmitriy.Belichenko | 7970 |
| SPb SU: Cheba Kings | Савелий Григорьев sava-cska | Андрей Ефремов receed | Михаил Иванов orz | 7967 |
| SPb ITMO: Insert your name | Николай Будин budalnik | Станислав Наумов josdas | Роман Коробков romanasa | 7863 |
| SPb SU: LOUD Enough | Иван Бочков tranquility | Владислав Макаров Kaban-5 | Никита Гаевой nikgaevoy | 7608 |
| MIPT: Malaya Bronnaya | Юрий Семенов SYury | Максим Мачула mHuman | Артем Комендантян komendart | 7529 |
| HSE: Sleeveless shorts | Филипп Грибов grphil | Фёдор Куянов Kuyan | Семён Савкин cookiedoth | 7410 |
| SPb HSE 1: Lemon Tree | Василий Алфёров platypus179 | Константин Махнев kokokostya | Максим Сурков maximumSHOT | 7370 |
| Belarusian SU 1 | Александр Керножицкий gepardo | Денис Ким kimden | Иван Лукьянов greencis | 7377 |
Делитесь с нами вашими впечатлениями и фотографиями в соцсетях с хештегом #NERC.
Кто станет финалистом и представит Северный Евразийский регион в финале ICPC 2021, когда бы он не состоялся? Узнаем уже в это воскресенье!
По какому принципу выбирались команды, за которыми "будет особенно интересно" наблюдать?
В списке некоторые команды, которые хорошо показали себя на сборах и онлайн-этапе.
Как же здорово, что, наконец, проводится онсайт-мероприятие. Желаю удачи и командам и организаторам!
а как же команда MIPT Blackbirds?
.
ah not really...
if you change cf language to russian you can see there are more comments in this blog :)
Скажите, а текст задач будет на русском? Очень интересно, но у меня проблемы с английским языком(
Официальный язык соревнований английский, условия задач будут на нём.
Can anyone give this contest and will this be rated ?
2020-2021 ICPC, NERC, Northern Eurasia Onsite ( Unrated, Online Mirror, ICPC Rules, Teams Preferred)
I know this might be an ignorant and insensitive question, but I took a look at the broadcast, and while the teams appeared to be spread a bit more sparsely than usually, some teams still were quite close to each other during the contest (at least to my feeling). And at the end of the contest, I definitely saw a few maskless people roaming the contest hall and chatting with other teams.
If I were a contestant, I would be a bit uncomfortable with that, but maybe the epidemiological situation in Russia/SPb is stable enough for the contest to be held fairly safely?
There are always maskless people if you don't penalize for it, and in general people don't care about each other. That's why this virus is still with us.
Now it looks like the half of Moscow / SPb is already protected from COVID. Still dangerous, but if you were a contestant and knew about the onsite, you could get vaccinated, it is available freely for 4 months already.
Can we publicly discuss questions now or is there some time before which we cant?
For some reason submitting is not possible even though system tests are complete.
Is there some place you can upsolve, or do we just have to wait?
HOW TO SOLVE B?
I used min cost max flow to solve the underlying weighted biparitte matching problem
You can also use regular bipartite matching $$$d$$$ times, adding all edges from codes with $$$d - i$$$ bits set in the $$$i$$$ th iteration (code).
just curious, will there be an editorial for this contest?
The official editorial is available on the NERC website
oh thanks, that was helpful
Is it min cost and not necessary max flow ? I pass it by stopping the process when the current cost is greater than zero .But I can't prove why it works :(
code: https://paste.ubuntu.com/p/XGVXpz3zPM/
Not sure, for my construction I think I can prove that the path(s) from source to target is always negative (by using the underlying model — if a path is found we always get rid of at least one reset button)
You can also try to add an edge directly from the source to sink with n capacity and zero cost, then you can just find min-cost max-flow directly without any modification in code.
thanks
The intuition is from Dilworth — I just converted the bipartite matching in the solution to dilworth to a weighted bipartite matching, and then recovered the chains.
Suppose I found the max anti chain using Dilworth's theorem, then how can I recover all the chains of minimum chain cover? Can you help me?
You should read this blog carefully, especially the part about calculating the width of a poset: https://codeforces.com/blog/entry/3781
In specific, one you make the bipartite graph, you just need to check which edges are matched — the nodes corresponding to the vertices of these edges belong to the same chain. Run a DSU to unite those in the same chain, then just topological sort the elements with the same parent and you're done. (In this problem, it was ok to just sort the elements, since that's a natural topological sort for submasks -> masks)
Actually I already upsolved this problem. I knew that last element of chain would be the ones with max bits set, so I started from those members and kept on following their parents(one on left side in the matching that points to the current element) and marked them as vis.
Your method is very nice (will work even if didnt know what are the ends of chain) and hence will help me in other problems.
Thanks a lot !! :)
How to solve I?
No regret dynamics
Specifically, see theorem 3.8, and use with $$$\eta < 0.3$$$.
Woah fancy. I'll check it out, thanks!
Oh wow, I knew there would be a proper idea describing the bound, but I didn't expect that good of a proof.
We just solved it on the intuition that's its probably a good idea to chase the leader. However we realized that choosing the option picked by the majority of leaders can be easily failed with something like a periodic repetition of $$$k$$$ players. After that it seemed logical that if $$$k$$$ people keep pace with the leader, choosing from them randomly with probability $$$\frac{1}{k}$$$ will result in you progressing at roughly the same rate. After that we just added weighting towards participants who were further ahead to get it to fit into the bound.
I solved I using Neural Network and it worked quite well. 112062623
Wow
Great job! Really impressed. Should we use adversarial training when preparing the test cases next time? :)
Amazing！
Our team solved question I using Gradient Descent and it did well too xD Solution
Incredible!
How to solve G????
Thanks in advance!!!
Consider a general path visting $$$k$$$ nodes. It will visit $$$2 \times k - l$$$ nodes, where for $$$l$$$ steps we go down the tree and not back up.
Its always possible to make this $$$l = \text {height of the tree}$$$ (though it may not be fully used for smaller $$$k$$$).
Let the $$$l$$$ nodes of this path be $$$a_1, a_2, \ldots, a_l$$$. Then for the remaining $$$k - l$$$ nodes (if $$$k \geq l$$$), we can just use the subtrees of the children of $$$a_1$$$ except for $$$a_2$$$, then move to $$$a_2$$$ and use the subtrees of the children of $$$a_2$$$ except for $$$a_3$$$, etc. Clearly we will never need to move back up from any $$$a_i$$$ to $$$a_{i - 1}$$$ and our total path length will be $$$\text{max}(2 \times k - l, k)$$$. Clearly as $$$l$$$ cannot be increased any further (and a path of $$$k$$$ nodes must be length at least $$$k$$$), this answer is optimal.
can't we upsolve it?
How to solve D?
In problem B, should
be
? The current statement implies that the "RESET" button can be pressed only once.
I tried to solve D using DP where $$$dp[i][j]$$$ represents maximum product upto index $$$i$$$ with last digit $$$j$$$. I used log to compare product. But I was not able to keep track of indices without TLE. What is wrong with my approach?
How to compare using Log ?
$$$log(xy) = log(x)+log(y)$$$, so whenever you multiply a number, just add their log to the product log.
112009578
Don't keep track of the indices explicitly. Keep track of where you came from in the best dp transition to this step, and whether that position was actually taken. Then you can recover the values at the end by iterating back through the dp array at the end.
Like say you set $$$dp[i + 1][k] = dp[i][j]$$$ then also set $$$from[i + 1][k] = j$$$ and $$$used[i + 1][k] = 0 \text{ or } 1$$$ depending on whether you actually used it. I think you can see how we can recover the values while iterating from $$$n$$$ to $$$1$$$ while doing something like this.
So I store like a pair, one for the log value and one for the previously used index.
Yup, exactly. Just ensure you update the second whenever you update the first.
Thanks man. This is a new thing that I have learnt, will surely be helpful in the following rounds.
We ran out of time debugging this approach on C at the end, is this correct / on the right track?
Erase all edges already part of a cycle. The graph is now decomposed into disconnected trees.
For each tree, find a node of $$$\text{degree} \gt 1$$$, if it exists, root the tree at that node (otherwise the tree is a single edge and can't have any cycles added to it without introducing multiple edges).
Now consider each node of this tree, from the bottom up. Let us suppose that each child of this node contributes exactly a single leaf. Then if a given node has $$$x$$$ children, it has $$$x$$$ leaves. We can clearly create edges between pairs of these leaves ($$$1$$$-st and $$$2$$$-nd, $$$3$$$-rd and $$$4$$$-th, etc) to form cycles. If the number of children are odd, we are left with one leaf, otherwise the current node becomes a new "leaf" on this tree, so the previous assumption holds. If we reach the root of the tree and the leaf remaining is not the root itself (or its direct child), add an edge to create a cycle between the root and this leaf. Clearly for each tree, each edge is a part of exactly one cycle after these operations, and therefore no more edges can be added without breaking the properties of a cacti.
The catch is that multiple edges are not allowed.
But otherwise you're on the right track, essentially it's removing cycles and matching odd-degree vertices with paths.
How many teams advance to finals?
12 advancing teams were announced on the stream. More teams may join them later, when organizers decide on the final quota
For G we initially thought a n*n*2 dp where dp[i][j][0/1] denotes the minimum length of path starting at vertex i to its subtree and we visit j distinct vertices, the last state indicates whether we return to the vertex i or not. Can someone suggest how to trace back this dp (or similar dp on trees) to create the answer ? The difficulty we faced while tracing back the answer was that once we see that a child of the subtree is part of the correct answer how to make sure that it doesn't reappear in lower states of its parent.
Store intermediate results. At every node $$$i$$$, instead of one array with indices $$$j, 0/1$$$, store $$$c_i+1$$$ arrays, where $$$c_i$$$ is the number of children of $$$i$$$. In the $$$0 \leq t \leq c_i$$$ th array, store what the DP looked like at $$$i$$$ after adding $$$t$$$ children.
You computed all of this in the original solution anyways, and we only use twice as much memory, so the time and space complexity does not change.
Thanks a lot.
I don't understand the editorial for B. Specifically, why is the path cover problem equivalent to a matching?
Edit1: I have found the source.
Edit2: Why are the paths need to be vertex-disjoint? I think any path cover is good.
You can read about Dilworth's theorem and I guess everything will be cleared after that why it yields answer.
Почему так мало команд прошло, всего 12? Есть ли вероятность, что квоту увеличат?
Вроде бы за медали на предыдущем финале дают дополнительные места, так что вероятность большая.
Зайки: Бочка (tranquility), Кабан (Kaban-5), Гайка (nikgaevoy), поздравляю с долгожданной победой! Пожалуйста, не ударьте в грязь лицом, когда настанет время)
И удачи!
Когда настанет время ударить в грязь лицом?
Спасибо, золотко мое!
For D, how to prove that "it is never optimal to remove more than 3 elements" as mentioned in the editorial?
Can any high-rated participant update the tags for Problem G (Since I don't have tag edit access), I think this is a nice tree problem and the following tags could be added.
1.dfs and similar
2.trees
3.shortest paths
4.Greedy
contest Link
I have a doubt about 1510I - Is It Rated?
There is my solution:
Do the following steps m times
Maintain how many mistakes every people made.
For each people, let p be the number of the mistakes he made and let q be the number of the right predictions he made.
If he predicted number x,
val[x] <- val[x] + q,val[1 - x] <- val[1 - x] + p * c(c is a constant)And then we output the number which its val is bigger
If there's too many mistakes the program made in some predictions at the beginning, we will use the random prediction to reduce mistakes.
Here is my submission: 125768206 (c = 1.5)
I think my solution might be wrong, and I would be very grateful for a data which can hack my solution.