Автор tourist, 22 месяца назад, По-русски

Привет!

VK Cup 2022 - Финальный раунд (Engine) начнётся уже скоро: 05.02.2023 15:05 (Московское время). Это соревнование предназначено для 16 лучших участников отборочного раунда VK Cup 2022. Раунд будет рейтинговым.

Остальных приглашаем на открытые для всех Codeforces Round 850 (Div. 1, основан на Финальном раунде VK Cup 2022) и Codeforces Round 850 (Div. 2, основан на Финальном раунде VK Cup 2022), которые начнутся в то же время и тоже будут рейтинговыми.

Все задачи финального раунда придуманы и подготовлены мной, а KAN придумал и подготовил две задачи для второго дивизиона. Также этот раунд стал лучше благодаря errorgorn, irkstepanov, qwerty787788, Merkurev, IgorI, PavelKunyavskiy, izban, Alexdat2000, ashmelev, Akulyat, mike_live, Ekler, Kalashnikov.

Вам будет предложено 6 задач и 3 часа на их решение.

Участники финального раунда поборются за призы:

  • 1-е место — 300 000 рублей;
  • 2-е место — 250 000 рублей;
  • 3-е место — 150 000 рублей;
  • 4-е место — 100 000 рублей.

UPD: Присоединяйтесь к видеотрансляции финала VK Cup 2022!

UPD: Разбор

Поздравляем победителей финального раунда:

  1. Maksim1744
  2. Ormlis
  3. never_giveup
  4. 353cerega

Также поздравляем победителей зеркала:

  1. ksun48
  2. maroonrk
  3. QuietBeautifulThoughts
  4. Mr_Eight
  5. ecnerwala
  • Проголосовать: нравится
  • +455
  • Проголосовать: не нравится

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

omg tourist round!

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

note: the unusual duration for 6 problems

»
22 месяца назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

omg tourist round:)

»
22 месяца назад, # |
  Проголосовать: нравится -99 Проголосовать: не нравится

omg tourist round:)

»
22 месяца назад, # |
  Проголосовать: нравится -96 Проголосовать: не нравится

omg tourist round

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

inb4 long wait for the editorial

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

is it rated for you?? :)

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

Note the unusual time (⓿><⓿)

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

omg lazy editorial round!

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

Желаю удачи финалистам

»
22 месяца назад, # |
  Проголосовать: нравится -73 Проголосовать: не нравится

omg tourist round!

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

»
22 месяца назад, # |
  Проголосовать: нравится -68 Проголосовать: не нравится

omg yet another lazy editorial round!

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

stO tourist Orz But I'm going to start school this Sunday.

»
22 месяца назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

omg lazy editorial round!

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

I don't know Russian but is it okay to participate and use google translation? Anybody doing it?

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

    All rated rounds have English problem statements, so you should not care about translation

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

Unfortunately,rating should be between 1,900 and 9,999 in order to register for the contest of div1.

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

orz tourist

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

Second time seen that there is no thanks to MikeMirzayanov for Codeforces and Polygon platforms,from the same author blog,hoping it never get repeated.

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

I am really afraid of tourist rounds. This is where my downfall starts

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

God round again.

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

1de71cc9b49c987a0179fed84b5acc9db9171a26

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

Hope problem C is solvable this time

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

Why this time seperated Div1,2 round though the elimination round was Div1+2? I guess Div1 and the final are the same problem set and some easier problems were added for Div2.

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

    Guess because there is no need to make combined round in this situation. On the contrary, elimination round should indeed be combined to allow div2 participants pass to the final stage.

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

      Not really. The only way to pass to the final stage was to make into top 16 of elimination round. Combined round #844 was just kind of mirror of elimination round for CF users and it has nothing to do with official tournament (except the same problems). And the question from physics0523 was why the author didn't repeat the same approach for today's contest, but decided to make two separate rounds based on finals instead of single combined round.

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

    Why this time seperated Div1,2 round though the elimination round was Div1+2?

    Final round problems are heavily focused on very strong competitors, so giving the same problemset as combined round fot both divisions didn't make any sense.

    I guess Div1 and the final are the same problem set and some easier problems were added for Div2.

    That's exactly what happened :)

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

Hope this won't be an overrated round again from tourist

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

Ahh yes a short announcement concisely thanking all people responsible for the betterment of the contest and that amazing chad energy coming off from the announcement. Is it possible this is a tourist round?

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

Tourist round = the hardest round

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

If no mention of interactive problems is made, does it always imply that they will not be present?

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

my first div2 contest. hope to solve at least 2 problems

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

Omg tourist round!

»
22 месяца назад, # |
  Проголосовать: нравится -44 Проголосовать: не нравится

omg trash round!

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

omg editorial after 10 days round

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

First time to take part in div1 only round, in which problem A could be as hard as problem D in div2. Perhaps I'll not be able to solve any problem.

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

Do take note of the unusual time of the contest.

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

afk btw i'

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

6 problems 3 hours, so scare!

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

Yet Another tourist round

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

Will it be codeforces mode or ICPC mode?

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

HERE WE GO...
»
22 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Finally a contest on a convenient time. It will be at 5pm for me.

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

I forgot the unusual start time, I guess this will be a no-sleep-forces round for me :')

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

omg Lantern Festival round!

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

what about Score distribution ?!

»
22 месяца назад, # |
  Проголосовать: нравится -51 Проголосовать: не нравится

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

Note the unusual timing.It is 17:35 IST (UTC+5.5).

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

I don't know about tourist, but one piece is real!

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

The time of the round is perfect for Chinese participants. Usually the codeforces rounds start at 22:35 CST (UTC+8), and I have to stay up late to participate. This round starts at 20:05 CST, which is much better.

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

No score distribution again!

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

Hoping for 18 plus points...

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

Yup it's Tourist round and i have accepted my fate here (Don't have good past experiences despite of problems being too good).

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

Guts Feeling, It will be a hard round.

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

Did you do it on purpose or accidentally?

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

While attempting problems you can feel that this is tourist round.

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

Div 2 speedforces

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

Div 2 Speedforces

»
22 месяца назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Requesting for codeforces feaure to contest as event when registered (Add to calender like leetcode,codechef)
»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится -77 Проголосовать: не нравится

So, what tourist round has?

  • Stupid Div 2's problems that are just about reading English.
  • NO thanks to MikeMirzayanov for Codeforces and Polygon platforms.
  • NO noted unsual time.
  • NO score distribution.

I know that sometimes being the best CPer allows you behave in such way, but please at least respect people.

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

I don't like the round anyway... huge work for 1B and 1C

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

Present passed 1A and 1B for 30 minutes, then sitting for 2.5 hours. So painful tourist round.

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

    well I spent about 1.5 hours on 1B and when I saw 1D I thought I should solve that problem in the first place instead of 1B. My solution to 1B is horrible and I rewrote my code twice, once because of my algorithm is incorrect and the other because I got sick of the rubbish code I had written.

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

    So I'm really interested in how to solve 1B so fast.

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

      This is my code for 1B 192297272, you may have a look.

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

      I used six vectors $$$f_{i, j}$$$ to maintain the indices with a more $$$i$$$ and without a $$$j$$$.

      An element in $$$f_{i, j}$$$ and an element in $$$f_{j, i}$$$ could be erased in one exchange. This type of exchange can be applied as much as possible. Then there remains only tuples shaped like $$$f_{i, j}, f_{j, k}, f_{k, i}$$$, each of which can be erased in two exchanges.

      It's not so hard to implement =)

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

        Same with mine.

        (So I code like an IGM lol

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

        Hi, can you help me prove why this strategy is optimal regarding number of exchange times?

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

          It is easy to see that we would only transform two elements shape like $$$(i, j)$$$ and $$$(j, k)$$$ into $$$(i, k)$$$, or simply erase two elements $$$(i, j)$$$ and $$$(j, i)$$$, where $$$i, j, k$$$ are different letters. One exchange will decrease the total number of elements by $$$1$$$ or $$$2$$$. So one can just maximize the number of exchanges of $$$(i, j)$$$ and $$$(j, i)$$$.

          If there are elements $$$(i, j)$$$ and $$$(j, i)$$$ but we don't exchange them, then we will exchange $$$(i, j), (j, k)$$$ and $$$(j, i), (i, k)$$$ to $$$(i, k)$$$ and $$$(j, k)$$$, respectively. Obviously, it's worse than simply erase $$$(i, j)$$$ and $$$(j, i)$$$ with one exchange. So if there are elements $$$(i, j)$$$ and $$$(j, i)$$$, we can just erase them.

          If there isn't a pair of elements shaped like $$$(i, j)$$$ and $$$(j, i)$$$, there are the same number of elements $$$(i, j), (j, k), (k, i)$$$. We can only transform $$$(i, j), (j, k)$$$ into $$$(i, k)$$$ since $$$i, j, k$$$ are equivalent, and then erase $$$(k, i)$$$ and $$$(i, k)$$$ with one exchange.

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

        OK thanks.this is similar to my third implementation. My second one turns out to be too complicated.

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

This round was a bit unbalanced. At least for div2

When 766 participants solved C, D was solved by 1

When 143 participants solved D, E was solved by 5

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

    Couldn't make it bc the contest was at 4am. Think I might have dodged a bullet there. :/

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

Speedforces or Implementation-forces

»
22 месяца назад, # |
Rev. 10   Проголосовать: нравится +49 Проголосовать: не нравится

Spent 3 hours and only solved the problem A of div1. Game Over.

By the way, as a former HearthStone player, problem A and C are pretty familiar for me.

Update: Now I've find a easy solution for div1B/div2D (look at this comment ). Very easy to implement but I've not come up with this idea for 2.5 hours. Although it's logic is easy, I've used over 100 lines of code to implement it.

Code (Now this code has got AC)
»
22 месяца назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

I got a thousand of WA and I wanna kill myself!!!

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

Is D graphs or just super ugly implementation? Or both?

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

    Yes

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

    I used a super ugly implementaion with upto 30 lines hardcoded data.

    I don't want to solve problems like this again.

    It seems that here's a pretty good solution with graph theory:

    build a three-node graph. when it's 'wwi', link w to i, when it's 'www', link w to i and w to n. and so on.

    Finnally match edges with same endpoints but different directions firstly. then cycles with length 3 remain.

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

      I've simulated this approach for some example cases. Maybe we should add an adge pointing from a "extra" char to a "lack" char, for example, "www"-->(w->i),(w->n), "iiw"-->(i->n), where (char1->char2) is an edge pointing from char1 to char2.

      Then we would get a directed graph with nodes {w,i,n}, each node has equal in-degree and out-degree. We can regard a exchange as cancelling 2 edges with same nodes and different direction, like (w->i),(i->w) --> nothing; or merge a path of 2 edges into 1 edge, like (w->i),(i->n) --> (w->n). We need to store the index of people in edges. To achieve the minimun number of operations, we need to use as more the first operation as possible. Therefore, first we cancel every pair of (w->i),(i->w) until one of them runs out, similar for (i->n),(n->i) and (n->w),(w->n). Then if there're edges remained, by the property of in-degrees and out-degrees, they must form some cycles like (w->i),(i->n),(n->w), or reversely, (w->n),(n->i),(i->w), we need to do 2 operations for each cycle.

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

    The implementation may not be ugly if you organize your code well. Maybe you can refer to this code by jiangly. The code is neat and it only took him 10 minutes.

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

How to solve Div2B? I needed to solve it to become cyan.

UPD: solved it

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

I hate the ROUND.... Unusual and confusing 1B and 1C...

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

    "If there are multiple solutions, print any", this sentence was missing at the beginning in 1B, that was bad.

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

time for tourist to settle down.

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

Is Div 2 D just a case work or is there any other methods?

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

this was the first time i saw an easy version and a hard version as a different problem code (the letter thingy)

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

Is Div 2 D just a case work or is there a elegant method?

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

    I don't know if there exists some elegant solution (I've seen some simple-ish ideas by people but not full solutions), but I personally had to write (and copy-paste) over 200 lines of code (I believe there has to be something simpler) to cover all cases.

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

    See my comment Although it's not elegant, I think it's easy to understand.

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

wow, my first div1 round and I havent lost 100+ rating)))

btw could anybody please tell how to solve 1C & 1D?

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

    1D can be solved in dynamic programming and polynomial tricks in $$$O(n\times 2^n)$$$ time, but I've heard there exists other solutions which do not require polynomial or the modulo $$$998244353$$$.

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

Predictor: my $$$\Delta=-1$$$ (now). DON'T FST!!!

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

If my solution failed for a HIDDEN PRETEST, (like Pretest 2), how much time after the contest can i see that testcase? Because the contest has ended, but I cant see the testcase which went wrong.

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

Does the problem 2D involves case work on bitmask? or this is graph problem?

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

Really interesting div 1 contest, thanks!

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

Why did you put a trivial 12D DP (= easy idea, looooong implementation) as Div1E? It's not funny.

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

Was Div1C a seg tree + binary search (based on the idea that after some time some numbers are fixed)? I could not come up with easier solution.

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

C was too hard for me ;)

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

    Even after that you completed the contest withing 2 and half hours , really appreciating.

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

Please give some hint how to solve problem 2D.

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

my suggestion after this,1782,1561: avoid vk cup rounds for boring implementation problems and random performance

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

I just wrote the ugliest code of my life for problem D (B for div1): 192346636 Didn't really like this problem, and C was too easy, it should have been B. Other that these, I enjoyed the contest, although I would have loved to have time for E :(

»
22 месяца назад, # |
Rev. 2   Проголосовать: нравится +27 Проголосовать: не нравится
Especially liked F
»
22 месяца назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится
My worst performance in a while T-T
»
22 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

My username is pretty much how i felt during the entire 3 hrs.Last tourist round for me.

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

So when will system test begin?

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

C, D and F are interesting, E is quite standard, and B is too hard for me.

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

    How t solve 1D?

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

      You do a dp of size $$$n \times 2^n$$$, where $$$dp[i][j] = $$$ number of ways that the number $$$j$$$ leads (is the highest value) a group of size $$$2^i$$$, and will lose all matches after this. Solve this dp top down.

      Here's a snippet of the solution

      Code

      couldn't get ac because coded too slow... :(

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

        Can you please explain the reasoning behind the transition between the states?

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

If problem setter is tourist, We expect better Contest, but I can say, this is the worst contest, I have ever given. Respect to tourist but Worst Contest ever seen... Mainly Problem D

»
22 месяца назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

where editorial?

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

Can anyone explain to me how to solve problems E and F on Div2? Thank you so much.

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

is this approach correct for B? align the first cake with the first dispenser, such that a1-w=b1-h, then for the rest of n-1 cakes check if you can move them to the left by less or equal to (a1+w)-(b1+h) so that they are aligned with their dispensers, if ever needed to move the cake to the right the answer is "no" otherwise "yes"

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

    Yes, that's what I did. see code

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

    For me, I shifted every cake by the same amount $$$x$$$. Note that $$$\forall i\ a_{i} - w + x \leq b_{i} - h \land b_{i} + h \leq a_{i} + w + x$$$. This means that $$$\forall i\ b_{i} - a_{i} - (w - h) \leq x \leq b_{i} - a_{i} + (w - h)$$$. So iterate over every $$$i$$$ and check that there is some $$$x$$$ that satisfies all the conditions for all $$$i$$$ by maintaining an overall lower bound and upper bound of the possible values of $$$x$$$. Clearly, if the lower bound required to satisfy the conditions is larger than the upper bound required to satisfy the conditions, then there is no such $$$x$$$, so the answer is no. Otherwise, the answer is yes.

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

Was div2D ugly implementation?? There was a huge gap no of solves for b and d. I have no idea how to even start approaching D

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

    My solution of D is a very ugly implementation

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

      Can you tell your approach? I thought this was similar to the question where we had to distribute equal number of ones among all rows, but just with 'w','i' and 'n'. But I had no idea how to implement it, if it even is correct in first place

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

        I counted all combinations and greedily matched those that benefit both people
        After that greedily matches those that benefit only one of them

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

      I tried using bit-masking (coding needs and excesses as bits, 64 possible states in total, the first 3 bits for needs of w, i, and n and the other 3 for excesses). The observation I made was that there can be only 2 kinds of moves, i-j and i-j-k.
      My implementation however got the better of me considering there were 9 unique cases in total, the code could have easily exceeded 600 lines if I had continued, lol.
      Could you share your approach?

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

        Indeed, my implementation uses 9 queues and 600 lines of code. 192373089

        It was submitted after the contest ended.

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

    My ugly implementation of div2D uses 9 queues and requires 600 lines of code 192373089

    I couldn't finish the implementation during contest.

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

    My implementation is so ugly that I had to use goto in c++.

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

One of the most unbalanced rounds (Div. 2) in a while.

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

Any hints / elegant approaches on solving div2-d?

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

      If I understand correctly, all the people are nodes and an edge is connected between someone who needs and has excess of the same letter? In this case why can't the size of the cycle be more than 3?

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

        For cycle of length 2: If suppose $$$ith$$$ person needs $$$w$$$ and it has an extra $$$i$$$ and if the $$$jth$$$ person needs an $$$i$$$ and it has extra $$$w$$$, we can perform the swap and both will be satisfied in 1 operation. We can do this for all possible combinations of letters.

        For cycle of length 3: If suppose $$$ith$$$ person needs $$$w$$$ and it has an extra $$$i$$$ and if the $$$jth$$$ person needs an $$$i$$$ and it has extra $$$n$$$, and if the $$$kth$$$ person needs $$$n$$$ and it has an extra $$$w$$$, we can first perform the swap between $$$ith$$$ and $$$jth$$$ person so now $$$ith$$$ person needs $$$n$$$ and it has an extra $$$i$$$, then we can perform the swap between $$$ith$$$ and $$$kth$$$ person. So all three will be satisfied in 2 operations.We can also do this for all possible combinations of letters.

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

Here is a problem with same idea as today's Div1B/Div2D in case anyone is interested.

Problem

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

Problem D writing a perfect code, to getting RE on test 19

Reason: I wrote an assert statement to debug the TLE cause in the local machine Locking the problem and realizing I can't change this

My AC code

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

Is div1-A's sample2 made by tourist himself?? I'm astounded him using Japanese internet meme how did he know that??(I know that it's well-known in Chinese...)

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

Why i can't upsolve?

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

omg tourist round!!!

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

In DIV2 C, the only observation is that we should perform the query of 2 as the last move, right?

**Proof : ** Let's suppose we make a "chain" of 1, 2, 3, .., x and we have some element remaining y(y > x + 1) then after the operation 2 we'll be left with only y — x and if we'll need y — x type 1 operations now but if had we made it x + 1 earlier then y — x — 1 type 1 operations would've been needed

lemme know if something seems wrong.

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

I liked the contest, thank you tourist for the problems!

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

my first div2. really good

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

1B's implementation is too horrible. I think there is no need to output the sequence of exchanges, it does no good but making this problem a lot more difficult to implement.

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

Tgod!!!i love you.This is my first time to reach the top 600.

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

Excellent Contest,Thanks for Tourist Cooperation For this Wonderful contest And especially for the first 4 problems

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

Can anyone see their rating changes using any rating predictor?

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

Why my solution for the problem B get tle is only O(2*n) I think is too closed time. The problem is that solutios work in real contest 192310034

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

why -ve at 3.8k rank?

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

for Problem : Div1B / Div2D

My idea is to first just ignore all strings that are perm of win. Then i tried to group the pair's that combindely take 1 swap (wwi <-> nni, wwn <-> iin, wnn <-> iiw). After this for all the strings that are left either 1 swap or 2 swaps required. On every iteration we can convert 2swap string to 1swap string and 1swap string to perm of win.

I didn't code this because of lack of time and implementation would be bigger but is my approach correct?

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

    Yup , I thought the same , sadly couldn't remove bugs in my code. This approach should work.

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

Finally! pupil. lot more to go, my goal is to become red. wish me luck!!!

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

What is the point of testcases where the same input is repeated 50000 times?

And how to deal with TLE arising in these test cases?

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

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

nice round. The problems are interesting that I didn't stop coding and thinking last night.

»
22 месяца назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

tourist round! OMG!

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

Can someone explain this testcase for div2 b to me?

1

3 3 1

3 10 25

7 23 27

The correct answer is NO but aren't all cakes getting chocolate and none is spilling over? The dispenser at position 7 gives chocolate to the cakes at position 3 and position 10 and the dispensers at 23 and 27 give chocolate to the cake at position 25.

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

    A single dispenser can never serve >1 cakes at a time without spilling (Given that w >= h)

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

      Thanks, I realized that a little after posting the comment

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

1B can be done by brute force.Here's my ugly code code

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

Short and easy implementation for div.2D, only 30 lines of processing needed, using the same idea of detecting cycles of length 2 and 3:

Press me
»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Oh, by the way, this round put the ♰tourist♰ back in first place!

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

Can someone please explain me Solution of B problem div2 , because I don't get the logic while seeing other code

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

I really like 1C. But 1E is just stupid implemention.

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

I become A CM again!

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

Nice D task, thanks

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

Am I the only person who did binary search in div-2 B ?

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

    I also thought of binary searching for a value $$$x$$$ in range $$$[-10^9, 10^9]$$$ that we are going to add to every $$$a[i]$$$ and see if every $$$i$$$ is OK. But it turned out that I don't know binary search so I started making another solution and wrote AC code 5 minutes after the end of the contest.

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

      I did bs on first cake's position ,

      then if for some i — i th cake is getting past i th dispenser then answer is on the left if it exists and right if no cake is getting past its dispenser and some haven't reached its dispenser

      otherwise I have answer

      192329929 Here's My Binary Search Solution

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

When will editorial be released?

worthy of being tourist XD

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

I keep getting runtime error of status access violation . I don't know what's wrong in my code, it runs fine on my compiler. https://mirror.codeforces.com/contest/1786/submission/192349129

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

    I don't know why it's not working but it seems to be working on cf if you use C++ 20. After trying to debug it for a bit it seems the problem is in this line.

    vector<pair<pair<char,ll>,pair<char,ll>>>
        while(a[i]<b[i])
        {
             cerr << a[i] << " " << b[i] << "\n";
             if(ab[a[i]].first != ab[b[i]].first)
    

    It seems the stderr is 0 4294967295 which is wrong, locally it gives me 0 1.

    3rd edit:
    This was the problem. Since ab, bc, and ac was empty 0 — 1 would equal 4294967295, casting it to int fixes this problem.

    b[0]=int(ab.size())-1;
    b[1]=int(bc.size())-1;
    b[2]=int(ac.size())-1;
    

    4th edit:
    If you want the compiler to warn you about this in the future add this flag on compilation -Wconversion.

    5th edit:
    I would recommend these flags https://mirror.codeforces.com/blog/entry/79024 since -Wconversion can be excessive sometimes.

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

      Thanks mate my code worked because of this. Thanks for this detailed answer

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

Solution idea of div1D/div2F:

First, WLOG we can assume we arrange the tournament in such way: In every matches, the left player wins. We can achieve this by doing the following operation to the binary tree of the tournament: for each non-leaf node of the binary tree, if the winner of this node is its right child, we "flip" this node by swapping its left subtree and right subtree. Since fliping doesn't change the winner of each match, this will not change the "wooden spoon", and after this operation, the "wooden spoon" is the right-most node. Since there are $$$2^{n}-1$$$ nodes in the binary tree, we can merge $$$2^{2^n-1}$$$ situations into one by this operation.

For example, we can do operation to this tree:

_________1

_____3_______1

-__5___3___1___2

__7_5_3_6_1_8_4_2

-->

_________1

_____1_______3

-__1___2___3___5

__1_8_2_4_3_6_5_7

Where $$$1$$$ (the left-most node) is the champion, and $$$7$$$ (the right-most node) is the "wooden spoon".

Then we assume the right-most node is k, and there's $$$dp[n][k]$$$ different arrangements (after operation). If $$$k$$$ is the $$$j$$$-th smallest element in the right half of the tree, then we have $$$\sum_{i=1}^{2^{n-1}}dp[n-1][i]$$$ ways to arrange the left half, and $$$dp[n-1][j]$$$ ways to arrange the right half (since $$$k$$$ is also the right-most node in the right-subtree). But in how many ways we can distribute $$$2^{n}$$$ elements into $$$2$$$ halves? Well, since $$$1$$$ is the left-most element, there are $$$k-2$$$ elements we could put in the right part (which are in the range $$$[2, k-1]$$$), and there are actually $$$j-1$$$ elements of them in the right part, so we have $$$\binom{k-2}{j-1}$$$ ways to choose them. Similarly, we have $$$\binom{2^{n}-k}{2^{n-1}-j}$$$ ways to choose elements from $$$[k+1, 2^k]$$$. Therefore, we can get such formula:

$$$dp[n][k]=\displaystyle \sum_{j=1}^{2^{n-1}}(\displaystyle \sum_{i=1}^{2^{n-1}}dp[n-1][i]) \cdot dp[n-1][j] \cdot \binom{k-2}{j-1} \cdot \binom{2^{n}-k}{2^{n-1}-j}$$$

Then we can calculate them by FFT. The answer is

$$$2^{2^{n}-1} \cdot dp[n][k]$$$

.

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

    Could you please elaborate on how to set the coefficients of the polynomials to get the result after the convolution for each $$$k$$$?

    I'm struggling with the binomial coefficients, they seem too dependent on the pairs $$$(k, j)$$$

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

      In fact, $$$\binom{k-2}{j-1}=\frac{(k-2)!}{(j-1)!(k-j-1)!}=(k-2)! \cdot \frac{1}{(j-1)!} \cdot \frac{1}{((k-j)-1)!}$$$ , so you can rewrite the original formula like this:

      $$$dp[n][k]=(\displaystyle \sum_{i=1}^{2^{n-1}}dp[n-1][i]) \cdot (k-2)! \cdot (2^{n}-k)! \cdot

      \displaystyle \sum_{\substack{j+j'=k \\ 1 \le j \le 2^{n-1}}} \frac{dp[n-1][j]}{(j-1)! \cdot (2^{n-1}-j)!} \cdot

      \frac{1}{(j'-1)! \cdot (2^{n-1}-j')!}$$$

      This formula contains a term of convolution. We can calculate the convolution part first, and for each terms of the convolution, we multiply the terms containing k on the left.

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

    I have similar formula, albeit no nested sum involved. Is it possible to calculate dp[n][k] without summoning monsieur Fourier?

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

Still Waiting:(

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

Can anyone explain Div2D to me, please? Thanks.

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

    First you count all the distinct characters in the strings of each individual. If all have 3 distinct characters then you print 0. Else then you see all the permutations of 3n characters possible among n people like they could have been www, iii, nnn, iiw, iwi, wii... and etc etc. Then for each such strings where you don't have 3 distinct characters you store them in a map<pair<char,char>, set> like in pair u store the characters to be replaced with what and in store you store the person who wanna exchange. Like mp['i', 'w'] will contain set of people who want to exchange 'w' with 'i'. Then after storing them you take two inverses together like mp['i', 'w'] with mp['w', 'i'] and inverse them until one becomes 0 and similarly for any another pair. Then you will see two types of cycle. Do same procedure in that cycle CW and ACW. Store them in a vector. And print the answer. You can see my submission for the reference. During contest I wasn't able to see the two cycles and only considered one. Have a good day:)

    My Submission

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

chronological order threw me off, i don't know why but i thought lexical order and kept on sorting my answer!

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

Does anyone know when the tutorial will arrive?

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

Can Someone please give an idea on how to solve Div2 E problem (Monsters: Hard version)

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

Where is official editorial? I want to see solution of Div2-B

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

Hey MikeMirzayanov I got a plag message for 1786B for my solution 192337404 but other than making an array of the differences I fail to see how it is similar to 192329389,192335667,192338432. Is there any other solution for div2B because this was just a simple code I did by seeing and analysing the test cases. Can you please look into it

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

I misunderstood problem B initially during the contest and I'm currently wondering if the "modified" version I understood can be solved.

It's the same problem but with a small twist, you can make any cyclic shift to the cakes assuming that the conveyor's length is not infinite (assume that the conveyor's length is at least $$$(max(max(a_i), max(b_i)) + w) - (min(min(a_i), min(b_i)) - w) + 1$$$

** $$$max(a_i)$$$ means maximum element over all elements in the array $$$a$$$, similarly $$$min(a_i)$$$, etc.

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

Can anyone please explain the solution of Problem B. Cake Assembly line. I tried to understand others solution but i can not figure out the logic, help me please. Thanks in advance. The code is given below.

include<bits/stdc++.h>

using namespace std; int a[100005],b[100005]; int main() { long long i,n,w,h,t; cin>>t; while(t--) { cin>>n>>h>>w; for(i=1;i<=n;i++) cin>>a[i]; for(i=1;i<=n;i++) cin>>b[i],b[i]-=a[i]; sort(b+1,b+n+1); if(b[n]-b[1]<=2*(h-w)) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }