Блог пользователя NercNews

Автор NercNews, 4 года назад, По-русски

text

Всем привет!

После долгой череды региональных онлайн-отборов и ожидания, мы рады объявить, что в эти выходные 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, когда бы он не состоялся? Узнаем уже в это воскресенье!

  • Проголосовать: нравится
  • +363
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

По какому принципу выбирались команды, за которыми "будет особенно интересно" наблюдать?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

    В списке некоторые команды, которые хорошо показали себя на сборах и онлайн-этапе.

»
4 года назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

Как же здорово, что, наконец, проводится онсайт-мероприятие. Желаю удачи и командам и организаторам!

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

а как же команда MIPT Blackbirds?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится -125 Проголосовать: не нравится

.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    ah not really...

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Скажите, а текст задач будет на русском? Очень интересно, но у меня проблемы с английским языком(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    Официальный язык соревнований английский, условия задач будут на нём.

»
4 года назад, # |
  Проголосовать: нравится -54 Проголосовать: не нравится

Can anyone give this contest and will this be rated ?

»
4 года назад, # |
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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +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?

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

HOW TO SOLVE B?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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?

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

        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)

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
          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 !! :)

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

How to solve I?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +22 Проголосовать: не нравится

    No regret dynamics

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +137 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

How to solve G????

Thanks in advance!!!

  • »
    »
    4 года назад, # ^ |
    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.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

can't we upsolve it?

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve D?

»
4 года назад, # |
  Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится 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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How to compare using Log ?

  • »
    »
    4 года назад, # ^ |
    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.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

How many teams advance to finals?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

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

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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.

»
4 года назад, # |
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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Почему так мало команд прошло, всего 12? Есть ли вероятность, что квоту увеличат?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вроде бы за медали на предыдущем финале дают дополнительные места, так что вероятность большая.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Зайки: Бочка (tranquility), Кабан (Kaban-5), Гайка (nikgaevoy), поздравляю с долгожданной победой! Пожалуйста, не ударьте в грязь лицом, когда настанет время)

И удачи!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.