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!
Mirror Problems Problems solutions
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 Rakhmatullin never_giveup | Maksim Gorokhovskii Maksim1744 | Ivan Safonov isaf27 | 8672 |
| SPb SU: 25 | Egor Gorbachev peltorator | Semen Petrov Semenar | Dmitriy Belichenko Dmitriy.Belichenko | 7970 |
| SPb SU: Cheba Kings | Saveliy Grigoryev sava-cska | Andrey Efremov receed | Mikhail Ivanov orz | 7967 |
| SPb ITMO: Insert your name | Nikolay Budin budalnik | Stanislav Naumov josdas | Roman Korobkov romanasa | 7863 |
| SPb SU: LOUD Enough | Ivan Bochkov tranquility | Vladislav Makarov Kaban-5 | Nikita Gaevoi nikgaevoy | 7608 |
| MIPT: Malaya Bronnaya | Yury Semenov SYury | Maksym Machula mHuman | Artem Komendantian komendart | 7529 |
| HSE: Sleeveless shorts | Philipp Gribov grphil | Fedor Kuyanov Kuyan | Semyon Savkin cookiedoth | 7410 |
| SPb HSE 1: Lemon Tree | Vasily Alferov platypus179 | Konstantin Makhnev kokokostya | Maksim Surkov maximumSHOT | 7370 |
| Belarusian SU 1 | Aliaksandr Kernazhytski gepardo | Dzianis Kim kimden | Ivan Lukyanov greencis | 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!
.
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.me/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.
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.