Автор gotexans, 5 лет назад, перевод, По-русски

Добрый день!

В 17.10.2021 14:05 (Московское время) состоится Технокубок 2022 - Отборочный Раунд 1 олимпиады для школьников Технокубок 2022. Раунд будет длиться два часа 15 минут, участникам будут предложены X задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 13:15 до 16:20).

Зарегистрироваться на Отборочный Раунд 1 →
Соревнование открыто для всех в виде отдельного раунда.
Для всех участников обеих редакций этого соревнования будет пересчитан рейтинг.

Параллельно с Отборочным Раундом будет проведен открытый рейтинговый раунд для обоих дивизионов, в нем могут принять участие все желающие.

Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:

Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Авторы отборочного раунда: Tlatoani, malachi_toney_goat, rabaiBomkarBittalBang, qlf9 и gotexans! Спасибо antontrygubO_o, isaf27 и KAN за координацию.

Спасибо всем, кто тестировал наш раунд: 244mhq, AmShZ, dorijanlendvaj, Keshi, czhang2718, 2020akadaver, Magikarp1, Richw818, quantum8, RayLee234, SlavicG, Qualified, Monogon, smax, wxhtzdy, kassutta, namanbansal013, HackerMonk, Ari, PurpleCrayon, FieryPhoenix, Jellyman102, bWayne, H4ckOm!

Для тех, кто впервые на Codeforces: в таблице ниже вы можете найти примеры решений на всех поддерживаемых языках:

Группа языков Языки программирования / компиляторы Примеры
C GNU C11 10903473, 17029870
C++ GNU C++14, GNU C++17, GNU C++20, MS VC++, etc. 23794425, 5456501
C# Mono C#, MS C# 3195513, 3794163
D D 5482410, 2060057
Go Go 7114082, 21366098
Haskell Haskell 455333, 1668418
Java Java 8, Java 11 25491359, 23678167
JavaScript V8 35963909, 35681818
JavaScript Node JS 38344430
Kotlin Kotlin 1.4, Kotlin 1.5 25779271, 25204556
OCaml OCaml 6157159, 1281252
Pascal Delphi, FPC, PascalABC.NET 1275798, 1259434
Perl Perl 2519448, 1277556
PHP PHP 413942, 35875300
Python Python 2, Python 3, PyPy2, PyPy3 35883730 (Py2), 36179112 (Py3)
Ruby Ruby 1837970, 1289551
Rust Rust 25180002, 35652442
Scala Scala 35847980, 2456025

Удачи!

UPD1:

Разбалловка Технокубка: $$$500$$$ — $$$1000$$$ — $$$1500$$$ — $$$1750$$$ — $$$2250$$$ — $$$2750$$$ — $$$3000$$$ — $$$3500$$$.

Разбалловка параллельного раунда: $$$500$$$ — $$$1000$$$ — $$$1500$$$ — $$$1750$$$ — $$$2250$$$ — $$$2750$$$ — $$$3000$$$ — $$$3500$$$ — $$$4000$$$.

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

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

see you next banner

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

Note the unusual timings :)

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

challenging problems.

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

hoping for a good contest :)

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

Hoping to be back to cyan. working hard to become expert.

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

Clash with Atcoder Beginner Contest :(

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

Damn 9 problems in 2:15 hrs

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

Can we participate without being from a Russian speaking country?

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

May the force be with you. Good luck to you all :))

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

As a tester, good luck!

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

Почему-то некоторые из учеников говорят, что им не приходит письмо с подтверждением регистрации. Сталкивался ли кто-то ещё с такой проблемой?

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

    Да. А теперь пришло, но не удается верифицировать аккаунт на codeforces. Пишет: Verification has not been completed. Please, try again to start the verification process.

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

MAy the OOds be ever in ur favor

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

Looking forward to solve problems and see a hike in my rating.

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

The only bad thing is the time of the contest. There is another contest in atcoder at the same time.

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

9 problems,so much!!!!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -25 Проголосовать: не нравится

Solve 9 problems within 2 hours and 15 minutes... The time limit is too tight!!!

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

great

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

May Mike be with us.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится +40 Проголосовать: не нравится
lighthearted meme
»
5 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

This contest clashes with AtCoder Beginner Contest 223 at 17:30 (UTC+5.5)

»
5 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится +5 Проголосовать: не нравится

have you noticed these days less number of people participating compared to two months earlier.

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

daytime in China,finally dont't need to stay up late

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

hoping for positive delta and also:

1 манул)

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

Looks like companies wanted to see each other clashes

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

:( Clashes with The International final

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -12 Проголосовать: не нравится

Accroding to tradition,This Contest might be delayed:(

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

Contest begin, my province: shut down the electricity.

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

Tree problem in B? why...

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

    note that m<n, which means that there is at least one vertex never occurs as $$$b_i$$$ among all restrictions

    we can always find a such vertex and link all other vertices to it.

    so it's like a greedy problem more than a graph/tree problem to me.

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -25 Проголосовать: не нравится

Div.1 + Div.2 = Div.1.5

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

Div2 rounds based on some Russian contest for school kids are always harder than usual Div2 rounds.

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

Imagine wasting 30+ mins on D because you forget to assert the values of $$$a_i$$$ in a query and print $$$a_i = n + 1$$$ in a certain case T_T.

But my mistakes aside, absolutely brilliant contest, one of the best I have seen in a while — Not a single boring problem from A-E! (can't talk about the rest since I haven't solved them, though F does look interesting as well)

E is a really really really cool problem — it looks insanely complex at first but decomposes to pretty easy ideas through some cool observations.

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

Nice C I got it but too late

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

What could be the testcase 3 for C?

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

In problem C XX XX

query : can 1 2 is determinable ?

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -9 Проголосовать: не нравится

A was much harder than B. Really disapointed about not reading problem B first

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

is this contest is for High-school ??

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

Problem E is such a problem, where you know that the first thing that comes to your mind has to be correct [path does not matter], otherwise it will be NP-hard or something.

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

What is wrong in this approach for Problem C

I check the minimum answer for each column with BFS and for each query I get the maximum for each column $$$C_l$$$ $$$C_(l+1)$$$ ... $$$C_r$$$, If it's less than L, print "YES", otherwise print "NO"

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

Nice problems. Though it would be better (at least for me) to extend the duration of the contest... I just gave up when I finished reading problem G and found out that there was only 20 minutes left.

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

hint for B please

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

My approach for B: I basically checked which node is not present as bi in the restrictions, then i used this node to create edge to every other node. but this gives WA on pretest 2 Can anyone explain where i am going wrong??

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

Nice problem set.

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Anyone else getting RTE on pretest 25 on Problem E?

Update: Figured it out. Dumb mistake, I was trying to pick a starting point for the spanning tree by finding a vertex with a nonzero number of queries, but accidentally set the starting point to be the number of queries itself instead of the vertex id. In hindsight, could have just rooted the spanning tree at vertex 1.

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

https://mirror.codeforces.com/contest/1586/submission/132264873
can anyone help with finding bug in this solution for C?

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

Did someone see F before? ko_osaga?

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

I liked F very much, thanks for the round :)

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

(Deleted)

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -67 Проголосовать: не нравится

The parallel AtCoder abc223 had better quality of programming problems.

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

Chinese problemsetting forces invading Russia lol

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +8 Проголосовать: не нравится

Problems are great, but I personally think the duration is a bit short, especially for data structure problems like H. Sadly I wasn't able to debug my code in time :(

more sadly, I succeeded in debugging it 10 minutes after the contest ended :(

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

Did anyone else get WA on test 6 for problem E?

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

Is C a segment tree problem?

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

    More like dp-problem

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

    No, much simpler than that.

    Hint: Consider under what situations will a single cell not be determinable.

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

    It can be used (I used it) but not necessary

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +56 Проголосовать: не нравится
    Solution in 1 sentence
  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится -18 Проголосовать: не нравится

    Nope, its dp combined with a sliding window like idea.

    The core idea is that if a cell can't exit the grid due to being blocked by cells above / to the left of it, it would be non-exitable regardless of whether it was $$$X$$$ or not. So all cells in a subgrid with $$$1 \leq i \leq n$$$, $$$x_1 \leq j \leq x_2$$$ must not be blocked for the answer to be yes.

    Basically let $$$minrow_{i, j}$$$ and $$$mincolumn_{i, j}$$$ be the smallest row and column reachable from a cell $$$(i, j)$$$.

    Then the minimum $$$x_1$$$ for a given $$$x_2$$$ is $$$max(mincolumn_{i, j})$$$ where $$$1 \leq i \leq n$$$, $$$1 \leq j \leq x_2$$$ and $$$maxrow_{i, j} \gt 1$$$.

    This can be calculated quickly for all $$$x_2$$$ with an easy observation — Since the function is max, $$$x_1$$$ never decreases as $$$x_2$$$ increases. So we can just iterate first on increasing $$$j$$$ then on $$$i$$$ to calculate the answer in $$$O(n \times m)$$$ time.

    Code
  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +3 Проголосовать: не нравится

    My solution is if there's an empty cell on column i, and it is blocked, then it is bad.

    So I use dp to check the furthest left a cell could and store the max for all cell of that column, then use segment tree to check max(l,r) <= l

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

    I aolved with seg tree tho idk it was the only soultion that came into my mind

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

Does anyone have a rigorous proof why arbitrary spanning tree works for E?

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

    It suffices to prove that, for a given tree and $$$u,v,w \in V$$$, edges which appears in exactly one of the simple path $$$uv$$$ and $$$vw$$$ forms the simple path from $$$u$$$ to $$$w$$$. This should be verified easily.

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

    First let's think of it as a dfs tree after getting a dfs tree.

    what you can do if you have a range of edges of ones on this tree is that you remove this range and replace it with one edge with 1 which is a back edge this edge will also have a 1 and since this edge is mapped to a range of edges it's obvious that you can't make it into a 0.

    I think it's the same with spanning trees the difference is the edges are not back edges but they are still mapped to one range of edges.

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

    The existence of an example is equivalent to all nodes participating in an even number of paths as endpoints. => is trivial, <= can be shown easily to hold for any tree (consider any edge, if it is used an odd number of times, the sum of usages in one of the subtrees would be odd as well).

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

    path from u to v = (path from u to root) xor (path from v to root)

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

What is the solution for D? Best idea I got was a randomized algorithm with expected number of queries to be exactly 2*n(which didn't pass as expected)

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

    Suppose we can find $$$p_n$$$ in at most $$$n$$$ queries, then we can find all other values in at most $$$n$$$ queries by increasing $$$a_1, \ldots, a_{n - 1}$$$ or $$$a_n$$$ by the required amount for it to match each value $$$1 \leq k \leq n$$$, one at a time.

    As for finding $$$p_n$$$, suppose I set $$$a_1, \ldots, a_{n - 1} = 1$$$ and $$$a_n = x$$$, then we will only get $$$0$$$ as a response if $$$p_n + x \gt n + 1$$$ (or $$$p_n + x \gt (n - 1) + 1$$$ if $$$p_n$$$ is $$$n$$$). So we can just iterate on all values of $$$x$$$ from $$$2$$$ upward and see the first value for which the condition fails to hold to exactly identify $$$p_n$$$.

    Code
  • »
    »
    5 лет назад, скрыть # ^ |
    Rev. 3  
    Проголосовать: нравится +11 Проголосовать: не нравится

    Hint: Create an undirected graph with N vertices where edge u-v indicates abs(p[u]-p[v])=1.

    If you figure this out it's simple. All that is left is running a dfs.

  • »
    »
    5 лет назад, скрыть # ^ |
     
    Проголосовать: нравится -10 Проголосовать: не нравится
    My solution:
  • »
    »
    5 лет назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится +2 Проголосовать: не нравится

    You can also solve it with a tighter query limit using binary search:

    The idea is if you find the last element, you can find every other element in $$$n$$$ queries. We can find the last element by performing a binary search to find $$$p_n - min(p_{n - 1}, p_{n - 2}, ...)$$$. If this value is negative, it means the last element is 1. So we only end up consuming $$$n + logn$$$ queries :)

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

Alex_Wei it's Unsuccessful hack for a reason :D

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

    Its 99.99% purposeful unsuccessful hacks to get last place. I've done it in the past when I felt I was getting too worried about my rating to the extent where the nervousness was ruining contests for me.

    Its trivial to copy paste the same input and change 1 value (can't use the same input twice on the same person) and make 20-30+ hacks / minute to quickly send yourself to last place.

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

liked D very much ... though was'nt able to implement my logic in time , but felt really good after solving it! :D thnx authors for such good problems!

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

132242048 C isn't a multitest problem but why I don't clear the array it makes my code FST ? After I clear the array I got accepted.132265702. Why ? When I change C++20 to C++17 in my FST code I have wrong in test 19 instead of 16. Why ?? :>

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

I am able to solve only 2 problems in most of the div 2 contests. can anyone give me suggestions to become a specialist

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +7 Проголосовать: не нравится

The contest is nice ,problem D,E,F are interesting . It is sad that I can solve G if 5 more minutes are given :(

»
5 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится +6 Проголосовать: не нравится

issue solved

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

To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!

==

Рейтинги предварительно обновлены. Через некоторое время я удалю читеров и пересчитаю рейтинг снова!

»
5 лет назад, скрыть # |
 
Проголосовать: нравится -23 Проголосовать: не нравится

This contest, I got rank 1328th (my previous rating is 1531) and my friend got rank 1446th (his pre rating is 1650) but my rating increased 75 and his rating increased 95. Can someone explain me this??? Many thanks

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

I'm curious about the special judge for problem B.How to check an output is valid or not quickly(I can only thought about a data structure which is O(n log^2 n))?

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

I suspect that I read the C question incorrectly. Yesterday I wrote this question in a very complicated way, which always showed errors. Today I understood the ac code, but I entered what I was confused about yesterday, and something went wrong. https://codeforces.ml/contest/1586/submission/132311045 This is the code of my wa yesterday. https://codeforces.ml/contest/1586/submission/132313973 This is ac code. But I can't understand the ac code. 3 3 XXX XXX XXX one 1 3 NO

4 5 ..XXX ...X. ...X. ...X. one 4 4 YES I hope someone can help me.

»
5 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Sorry, i was going to write that on commentary of 748 div.3, but i chose the wrong contest.

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

Hello please help me out. Just now I received a mail that my solution of problem 1586B of Codeforces Round #749 (Div. 1 + Div. 2, based on Technocup 2022 Elimination Round 1) conicides with user 1928311. First of all there is no chance of my solution getting leaked to any one because i didnt shared it. Secondly, kindly see the submission time of his solution , I submitted that at 17:21 and he submitted at 17:45. How could I cheat then. Please help me regarding this.