NercNews's blog

Northern Eurasia Finals 2020: Offline
By NercNews, 4 years ago, translation, In English

text

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!

ICPCLive broadcast Standings

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!

  • Vote: I like it
  • +363
  • Vote: I do not like it

Comments Comments (57)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it -125 Vote: I do not like it

.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    ah not really...

    if you change cf language to russian you can see there are more comments in this blog :)

    → Reply
»
4 years ago, # |
  Vote: I like it -54 Vote: I do not like it

Can anyone give this contest and will this be rated ?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    2020-2021 ICPC, NERC, Northern Eurasia Onsite ( Unrated, Online Mirror, ICPC Rules, Teams Preferred)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +71 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Can we publicly discuss questions now or is there some time before which we cant?

→ Reply
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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?

→ Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

HOW TO SOLVE B?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I used min cost max flow to solve the underlying weighted biparitte matching problem

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +21 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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/

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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)

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it

        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)

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          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 !! :)

          → Reply
»
4 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to solve I?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +22 Vote: I do not like it

    No regret dynamics

    Specifically, see theorem 3.8, and use with $$$\eta < 0.3$$$.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Woah fancy. I'll check it out, thanks!

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +137 Vote: I do not like it

    I solved I using Neural Network and it worked quite well. 112062623

    → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve G????

Thanks in advance!!!

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

can't we upsolve it?

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve D?

→ Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to compare using Log ?

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So I store like a pair, one for the log value and one for the previously used index.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yup, exactly. Just ensure you update the second whenever you update the first.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks man. This is a new thing that I have learnt, will surely be helpful in the following rounds.

          → Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +22 Vote: I do not like it

How many teams advance to finals?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    12 advancing teams were announced on the stream. More teams may join them later, when organizers decide on the final quota

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can read about Dilworth's theorem and I guess everything will be cleared after that why it yields answer.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For D, how to prove that "it is never optimal to remove more than 3 elements" as mentioned in the editorial?

→ Reply
»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a doubt about 1510I - Is It Rated?

There is my solution:

Do the following steps m times

  1. Maintain how many mistakes every people made.

  2. 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.

  3. If he predicted number x, val[x] <- val[x] + q, val[1 - x] <- val[1 - x] + p * c (c is a constant)

  4. And then we output the number which its val is bigger

  5. 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.

→ Reply