### NercNews's blog

By NercNews, 2 weeks ago, translation,

Hello everyone!

After all online qualifiers, we are pleased to announce that the Northern Eurasia Finals and ICPC 2021 semi-final offline stage will take place this weekend on April 3-4!

In December 2020, we announced that 50 student teams out of 330 were selected for the Northern Eurasia Finals. Most of the teams will compete in St. Petersburg. Still, some teams will compete at Minsk, Tbilisi, and Riga sites due to travel restrictions between countries.

NERCNews is going to monitor the championship and report on the main events! We will post links to the results table, contest tasks, contest mirror, and analytics published on the official website.

UPD today were qualified for ICPC 2021 World Finals next 12 teams:

• 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)

Also, join the traditional ICPCLive team online broadcast from the site in St. Petersburg. The schedule for both days can be found here.

We have compiled a list of teams grouped by ratings, which will be especially interesting to follow. What are your predictions? Favorites?

 Team Contestant 1 Contestant 2 Contestant 3 Rating HSE: Overtrained Ramazan Rakhmatullinnever_giveup Maksim GorokhovskiiMaksim1744 Ivan Safonovisaf27 8672 SPb SU: 25 Egor Gorbachevpeltorator Semen PetrovSemenar Dmitriy BelichenkoDmitriy.Belichenko 7970 SPb SU: Cheba Kings Saveliy Grigoryevsava-cska Andrey Efremovreceed Mikhail Ivanovorz 7967 SPb ITMO: Insert your name Nikolay BudinNebuchadnezzar Stanislav Naumovjosdas Roman Korobkovromanasa 7863 SPb SU: LOUD Enough Ivan Bochkovgnomina007 Vladislav MakarovKaban-5 Nikita Gaevoinikgaevoy 7608 MIPT: Malaya Bronnaya Yury SemenovSYury Maksym MachulamHuman Artem Komendantiankomendart 7529 HSE: Sleeveless shorts Philipp Gribovgrphil Fedor KuyanovKuyan Semyon Savkincookiedoth 7410 SPb HSE 1: Lemon Tree Vasily Alferovplatypus179 Konstantin Makhnevkokokostya Maksim SurkovmaximumSHOT 7370 Belarusian SU 1 Aliaksandr Kernazhytskigepardo Dzianis Kimkimden Ivan Lukyanovgreencis 7377

Share your impressions and photos on social networks using hashtag #NERC.

Who will represent the Northern Eurasian Region in the ICPC 2021 Final whenever it happens? We will find out this Sunday! Stay tuned!

• +363

 » 13 days ago, # | ← Rev. 2 →   -125 .
•  » » 12 days ago, # ^ |   +10 ah not really...if you change cf language to russian you can see there are more comments in this blog :)
 » 12 days ago, # |   -54 Can anyone give this contest and will this be rated ?
•  » » 12 days ago, # ^ | ← Rev. 2 →   +4 2020-2021 ICPC, NERC, Northern Eurasia Onsite ( Unrated, Online Mirror, ICPC Rules, Teams Preferred)
 » 12 days ago, # | ← Rev. 2 →   +71 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?
•  » » 12 days ago, # ^ |   +51 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.
 » 12 days ago, # |   +20 Can we publicly discuss questions now or is there some time before which we cant?
 » 12 days ago, # |   +32 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?
 » 12 days ago, # |   +13 HOW TO SOLVE B?
•  » » 12 days ago, # ^ |   +8 I used min cost max flow to solve the underlying weighted biparitte matching problem
•  » » » 12 days ago, # ^ | ← Rev. 2 →   +21 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).
•  » » » » 12 days ago, # ^ |   0 just curious, will there be an editorial for this contest?
•  » » » » » 12 days ago, # ^ |   +21 The official editorial is available on the NERC website
•  » » » » » » 12 days ago, # ^ |   0 oh thanks, that was helpful
•  » » » 12 days ago, # ^ |   0 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 :(
•  » » » » 12 days ago, # ^ |   +8 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)
•  » » » » 12 days ago, # ^ |   +8 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.
•  » » » » » 12 days ago, # ^ |   0 thanks
•  » » 12 days ago, # ^ |   +22 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.
•  » » » 11 days ago, # ^ |   0 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?
•  » » » » 11 days ago, # ^ | ← Rev. 2 →   +6 You should read this blog carefully, especially the part about calculating the width of a poset: https://codeforces.com/blog/entry/3781In 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)
•  » » » » » 10 days ago, # ^ | ← Rev. 3 →   0 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 !! :)
 » 12 days ago, # |   +15 How to solve I?
•  » » 12 days ago, # ^ |   +22 No regret dynamicsSpecifically, see theorem 3.8, and use with $\eta < 0.3$.
•  » » » 12 days ago, # ^ |   0 Woah fancy. I'll check it out, thanks!
•  » » » 12 days ago, # ^ |   0 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.
•  » » 11 days ago, # ^ |   +137 I solved I using Neural Network and it worked quite well. 112062623
•  » » » 11 days ago, # ^ |   +1 Wow
•  » » » 11 days ago, # ^ |   0 Amazing!!!
•  » » » 11 days ago, # ^ |   +51 Great job! Really impressed. Should we use adversarial training when preparing the test cases next time? :)
•  » » » 11 days ago, # ^ |   0 Amazing！
•  » » » 11 days ago, # ^ | ← Rev. 2 →   +27 Our team solved question I using Gradient Descent and it did well too xD Solution
•  » » » 8 days ago, # ^ |   0 Incredible!
 » 12 days ago, # |   +6 How to solve G????Thanks in advance!!!
•  » » 12 days ago, # ^ | ← Rev. 3 →   0 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.
 » 12 days ago, # |   +8 can't we upsolve it?
 » 12 days ago, # |   +5 How to solve D?
 » 12 days ago, # |   +18 In problem B, should but there is a “RESET” button -- pressing it pops up all other buttons be but there is a “RESET” button pressing it pops up all buttons ? The current statement implies that the "RESET" button can be pressed only once.
 » 12 days ago, # |   0 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?
•  » » 12 days ago, # ^ |   0 How to compare using Log ?
•  » » » 12 days ago, # ^ |   0 $log(xy) = log(x)+log(y)$, so whenever you multiply a number, just add their log to the product log.
•  » » » 12 days ago, # ^ |   +1
•  » » 12 days ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 12 days ago, # ^ |   0 So I store like a pair, one for the log value and one for the previously used index.
•  » » » » 12 days ago, # ^ |   0 Yup, exactly. Just ensure you update the second whenever you update the first.
•  » » » » » 12 days ago, # ^ |   0 Thanks man. This is a new thing that I have learnt, will surely be helpful in the following rounds.
 » 12 days ago, # | ← Rev. 5 →   0 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.
•  » » 12 days ago, # ^ |   +10 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.
 » 12 days ago, # |   +22 How many teams advance to finals?
•  » » 12 days ago, # ^ |   +20 12 advancing teams were announced on the stream. More teams may join them later, when organizers decide on the final quota
 » 12 days ago, # | ← Rev. 3 →   +10 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.
•  » » 12 days ago, # ^ |   +15 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.
•  » » » 12 days ago, # ^ |   +6 Thanks a lot.
 » 12 days ago, # | ← Rev. 3 →   0 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.
•  » » 11 days ago, # ^ |   0 You can read about Dilworth's theorem and I guess everything will be cleared after that why it yields answer.
 » 12 days ago, # |   0 Okay so i'll support HSE Overtrained
 » 4 days ago, # |   0 For D, how to prove that "it is never optimal to remove more than 3 elements" as mentioned in the editorial?