Автор MagentaCobra, 3 года назад, перевод, По-русски

Добрый день!

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

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

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

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

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

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

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

Авторы отборочного раунда: Tlatoani, golions, rabaiBomkarBittalBang, qlf9 и MagentaCobra! Спасибо 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
  • Проголосовать: не нравится

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

see you next banner

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

Note the unusual timings :)

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

challenging problems.

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

hoping for a good contest :)

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

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

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

Clash with Atcoder Beginner Contest :(

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

Damn 9 problems in 2:15 hrs

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

Can we participate without being from a Russian speaking country?

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

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

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

As a tester, good luck!

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

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

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

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

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

MAy the OOds be ever in ur favor

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

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

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

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

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

9 problems,so much!!!!

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

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

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

    Probably first few problems would be ez :) . Otherwise the time is very tight.

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

    for LGMSs it's not so tight, for Div2 it's not big difference to solve first 3-4 problems in 2:15 or in 2:45 for example

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

    I had only 10 minutes for the last three problems,so I just left and took a look at Atcoder Beginner Contest :(

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

great

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

May Mike be with us.

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

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

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

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

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

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

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

hoping for positive delta and also:

1 манул)

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

Looks like companies wanted to see each other clashes

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

:( Clashes with The International final

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

Accroding to tradition,This Contest might be delayed:(

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

Contest begin, my province: shut down the electricity.

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

Tree problem in B? why...

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

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

Div.1 + Div.2 = Div.1.5

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

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

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

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

Nice C I got it but too late

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

What could be the testcase 3 for C?

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

    Likely some mistake with not checking if cells which are $$$X$$$ could hypothetically escape if they weren't $$$X$$$. If that isn't the case you can't determine if it was initially $$$X$$$ or not. Forgetting to check that caused WA3 for me.

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

      I looked for patterns like: _X \n X. where _ is any character, Here [2,2] can be both X or . , so this subgrid is indeterminable. Did I miss something?

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

        You were supposed to look for the pattern

          X
        X _
        

        UPD: Oops, finding both patterns is the same thing, you are right

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

In problem C XX XX

query : can 1 2 is determinable ?

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

    Do you mean XX \n XX? Then it's not determinable.

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

      Y ?

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

        Because, we can't determine the state of (2,2) cell exactly without looking at the grid. Suppose, instead of

        XX  
        XX
        

        We're given,

        XX  
        X.
        

        Then, still none are exitable, but one cell in the latter is empty. So, undeterminable!

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

          Ok

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

          Thanks for putting me out of my misery. I spent around 2 hrs struggling with this problem. Now that I know, no one deserves that -100 more than me, I am at peace. Thanks again.

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

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

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

is this contest is for High-school ??

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

    It's Russian highschool level which is roughly the same difficulty as a U.S. post-doctorate program or a Chinese gradeschool contest.

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

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

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

    had the same idea, WA pretest 3 :(

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

    I did something similar but got WA on test 3.

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

    Maybe you did not handle if a blocked cell itself cannot exit the sub-graph if it was not blocked. In this case we will not be able to know if its N represents a blocked or an empty cell.

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

    Are you checking if cells which are $$$X$$$ would be theoretically exitable if they weren't $$$X$$$ as well?

    Suppose one of those cells is not exitable even if it wasn't $$$X$$$, then you wouldn't be able to differentiate between it being initially marked $$$X$$$ or not, so the grid isn't determinable.

    I forgot about this and got WA3 because of that.

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

      aah so you are saying that for n=2 m=2 XXXX query (1,2) should be NO instead of YES?

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

        That's correct, because it could also be
        XX
        X.

        Both situations are identical in the view of exitability, since all 4 cells are not exitable.

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

      I can't understand why I need to check If $$$X$$$ would be theoretically exitable if they weren't $$$X$$$.

      I am checking if there is empty cell is not exitable, if there is atleast one then I can't differentiate.

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

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

hint for B please

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

    $$$m<n$$$ (strictly less)

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

      I made edges a -- c for the given m restrictions. Then, to get the remaining edges I connected all separate components (checked using DSU) by an edge. Whats wrong with this? I kept getting WA2.

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

        Connecting all edges a-c may result in a cycle even when m<n. Consider the following: 1 4 2 2 5 3 3 6 1

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

        Consider this case,
        4 3
        1 2 3
        3 1 2
        2 3 1

        In your final answer, the third constraint will not be satisfied.

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

    Make b[i] leaves

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

    It's given 1 < m < n .

    So there will be at least one node that can be between any two nodes, make it root. Now just connect all the other nodes to it.

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

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

    its correct its my solution too u probably implemented it wrong

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

    Check if your bi is 0-indexed or 1-indexed. I had the same problem where I accidentally read in all bi's 1-indexed, and changing it to 0-indexed fixed it.

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

    I also did same.. May be you have done some mistake in implementation

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

Nice problem set.

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

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

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

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

Did someone see F before? ko_osaga?

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

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

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

(Deleted)

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

The parallel AtCoder abc223 had better quality of programming problems.

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

    well, the quality of the problemset does not depend on whether you can solve them or not.

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

Chinese problemsetting forces invading Russia lol

»
3 года назад, # |
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 :(

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

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

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

Is C a segment tree problem?

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

    More like dp-problem

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

    No, much simpler than that.

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

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

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +56 Проголосовать: не нравится
    Solution in 1 sentence
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -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
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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

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

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

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

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

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

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

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

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

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

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

  • »
    »
    3 года назад, # ^ |
    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 > n + 1$$$ (or $$$p_n + x > (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
  • »
    »
    3 года назад, # ^ |
    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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится
    My solution:
  • »
    »
    3 года назад, # ^ |
    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 :)

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

    I think, you should delete this line:

    $$$if(Grid[i][j] == 0){$$$

    EDIT: It still struggles with test 4, Idk what else is wrong.

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

      Oh , but if it's a X, then we can include that column rt?
      Like this,

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

        In such a construction of two diagonally adjacent 'X' cells, the cell between them will always be non-exitable, regardless of what is written in it. Thus, we can change its state and get a different initial table with the same set of exitable cells, so we have to consider the mentioned case too and include that column.

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

Alex_Wei it's Unsuccessful hack for a reason :D

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

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

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

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

    You are defining an array locally (inside of a function) rather than globally. The locally-defined array can contain anything at initialization.

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

    the array you defined is not global, if you didn't clear it then it just contain garbage :D

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

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

    Try to solve 3 problems.

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

      Thanks. I will try.

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

        Okay to be serious, here are some suggestions that may be helpful for you:

        1. Try to have a good format of code, this is helpful because it allows you to debug easier and code faster.(This means indentations and spaces)

        2. Try to think more before you code. Try to have an idea of what algorithm you will implement, and what are the details that may cause problems.

        3. Solve more problems in general. To be able to solve 3 problems, you need to be fluent in the language you code and be able to think logically to reach a solution. The third problem often needs some thinking, it isn't as direct, so it may need more practice.

        4. If you are sure that your algorithm is correct, and you fail to debug, try writing it over.

        Hope this may be helpful for you.

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

          Does it mean that the first two problems require no thinking at all? :)

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

            Jokes aside, seeing how many people here (even high rating ones) completely blacked out on B, nope.

            Sometimes those "easy" problems actually requires you to figure out a specific trick, you get the problem if you do and you don't get it if you don't. Which is exactly what B is.

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

          okay.thank you so much

»
3 года назад, # |
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 :(

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

    It is sad that I can solve D if 5 more minutes are given :D
    also 9 problems deserve way more than 2:15

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

issue solved

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

==

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

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

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

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

    if b is on path between a and c, than dist(a,b)+dist(b,c)=dist(a,c)

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

      And?

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

        this help's to check if the tree is valid

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

          Finding distance is not any faster than simply checking nodes on the way to the LCA.

          How is it relevant to the comment you replied to?

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

            If there are $$$m$$$ restrictions, we can check the validity of output in $$$O((n+m)logn)$$$. this is faster than $$$O(nlog^2n)$$$

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

              Can you elaborate?

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

                first, we precalculate LCA(binary lifting) for each node & dist from root to each node. this takes $$$O(nlogn)$$$ time&memory. next, for each of $$$m$$$ restrictions like $$$a \space b \space c$$$ we check if $$$dist(a,b) + dist(b,c) = dist(a,c)$$$. we do this in $$$O(logn)$$$ time by finding the LCA for each pair of nodes. if so, the output is invalid.

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

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

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

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    1. How could I cheat then you shared your solution.

    2. i didnt shared it any proof?

    3. it can't be coincidence, the solutions are very similar.

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

      Arey how could one prove that he/she didn't shared his solution. Its not possible na. Atleast I proved that I didn't cheat. Please help me. Else it will simply demotivate me from CP

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

        have you used an online editor like ideone?

        also for proving that you didn't cheat you need to prove that you didn't share any code, and that is almost impossible

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

          No I used vscode. Wow got -113 without any fault :).I am impressed by your team and judgements for simply disqualifying a participant for not cheating :) Very good.

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

            i am just a cf user not an admin or something else.

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

              So whom should I ask for this problem??

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

                no one.

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

                  You must be saying about the template.That is the xor function. I have a discord a server where I have shared my template with others. Many people use that

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

          also for proving that you didn't cheat you need to prove that you didn't share any code, and that is almost impossible. Thats what i am saying na, you just say what kind of proof u need from me that i didn't shared the code. I am giving you.

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

            There will be a person in charge in each round. You can go to 749 (div1+div2) comments to find out. One person said that he would launch a new ranking again within a few hours or days after the game. I think this person should be responsible for the ranking of the game.

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

            Hope it can help you

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

            just another indian cheater getting caught and still doesn't feel any guilt of it

            132234060 132242274

            It's amazing that he's still not ashamed of himself even with his EXACTLY same code.

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

              Yes that's because I didn't cheat. I was just explaining my solution to some of my friends in my hostel and one of them simply took the snap of it and wrote it as it is

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

                that's called CHEATING

                First of all there is no chance of my solution getting leaked to any one because i didnt shared it

                and you lied :) Anything else you want to say

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

                  That's simply because I solved the qs myself n I didn't wanna loose my ratings. Nyways I am guilty for what I did and paid it with my ratings down

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

              U better see the submission time and then decide who cheated