Codeforces Round #850
By tourist, 21 month(s) ago, translation, In English

Hello!

Welcome to Codeforces Round 850 (Div. 1, based on VK Cup 2022 - Final Round) and Codeforces Round 850 (Div. 2, based on VK Cup 2022 - Final Round) that will start on Feb/05/2023 15:05 (Moscow time). Both rounds will be rated.

This round is a mirror of VK Cup 2022 Final — annual programming championship for Russian-speaking competitors organized by VK. VK Cup started in 2012 and has grown to be a five-track competition in competitive programming, Mobile, ML, Go, and JavaScript.

All the problems of Div. 1 round are authored and prepared by me, while KAN authored and prepared two problems for Div. 2. Thanks to errorgorn, irkstepanov, qwerty787788, Merkurev, IgorI, PavelKunyavskiy, izban, Alexdat2000, ashmelev, Akulyat, mike_live, Ekler, Kalashnikov for making this round better.

You will be given 6 problems and 3 hours to solve them.

UPD: Editorial

Congratulations to the winners:

  1. ksun48
  2. maroonrk
  3. QuietBeautifulThoughts
  4. Mr_Eight
  5. ecnerwala
  • Vote: I like it
  • +455
  • Vote: I do not like it

Comments Comments (265)
| Write comment?
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -232 Vote: I do not like it

omg tourist round!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

note: the unusual duration for 6 problems

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +122 Vote: I do not like it

    Candidate Masters in div 1 will be cooked

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +45 Vote: I do not like it

      First div1 round in my life! Which happens to be a tourist round! Wish all of us good luck.

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      LOL.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it -99 Vote: I do not like it

omg tourist round:)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -96 Vote: I do not like it

omg tourist round

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +53 Vote: I do not like it

inb4 long wait for the editorial

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +29 Vote: I do not like it

Note the unusual time (⓿><⓿)

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +78 Vote: I do not like it

omg lazy editorial round!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -73 Vote: I do not like it

omg tourist round!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +33 Vote: I do not like it

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -68 Vote: I do not like it

omg yet another lazy editorial round!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -34 Vote: I do not like it

omg lazy editorial round!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +21 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

God round again.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +62 Vote: I do not like it

1de71cc9b49c987a0179fed84b5acc9db9171a26

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      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.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it -10 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

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?

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -44 Vote: I do not like it

omg trash round!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Do take note of the unusual time of the contest.

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

afk btw i'

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

6 problems 3 hours, so scare!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Yet Another tourist round

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Will it be codeforces mode or ICPC mode?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +109 Vote: I do not like it 

HERE WE GO...
→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

omg Lantern Festival round!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

what about Score distribution ?!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -51 Vote: I do not like it

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

No score distribution again!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

Hoping for 18 plus points...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Guts Feeling, It will be a hard round.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Did you do it on purpose or accidentally?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -9 Vote: I do not like it

Div 2 Speedforces

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it 
Requesting for codeforces feaure to contest as event when registered (Add to calender like leetcode,codechef)
→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -77 Vote: I do not like it

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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    Downvoting me just because I stated some really bad FACT about tourist? You guys are really brainless...

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Same with mine.

        (So I code like an IGM lol

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

Speedforces or Implementation-forces

→ Reply
»
21 month(s) ago, # |
← Rev. 10   Vote: I like it +49 Vote: I do not like it

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)
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    For This, I guess my logic is same but there is actually no need to harcode stuff, though It is something very tedious. Here is my code 192350442

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      What dose "dp" stand for? I thought it cannot be "dynamic programming"

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        haha, yes i didn't ask for your dynamic programming, here Dp stands for actually display picture or account picture.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Me too!!Got stuck and got 9 WAs :(

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Yes

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +17 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow clean and smooth implementation

      → Reply
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

UPD: solved it

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

time for tourist to settle down.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it
    1C
    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

Really interesting div 1 contest, thanks!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +48 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +174 Vote: I do not like it

C was too hard for me ;)

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Please give some hint how to solve problem 2D.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +252 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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 :(

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +27 Vote: I do not like it
Especially liked F
→ Reply
»
21 month(s) ago, # |
  Vote: I like it +39 Vote: I do not like it
My worst performance in a while T-T
→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

So when will system test begin?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How t solve 1D?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      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... :(

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

        → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -7 Vote: I do not like it

where editorial?

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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"

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Yes, that's what I did. see code

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    My solution of D is a very ugly implementation

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

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

        It was submitted after the contest ended.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    I couldn't finish the implementation during contest.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Any hints / elegant approaches on solving div2-d?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it
    Idea
    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 4   Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

In brief solutions for all div2 (except B) problems and Div1 A-D

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Problem

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how it is similar, can you please elaborate sir

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      In both the problems you only need to resolve the cycles of length 2 then cylces of length 3.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +155 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I don't get it.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      the second testcase is 4 1 5 4 1 1 and rearranging it we get 1 1 4 5 1 4.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        However personally I think this may just be a coincidence and could not prove anything.

        → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        Guess I'm too Indian to understand this.

        → Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    I have the same question. Maybe tourist also surf foreign websites? (wwwww

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +110 Vote: I do not like it

    Heh, Heh, Heh, aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Why i can't upsolve?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

omg tourist round!!!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

my first div2. really good

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -22 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone see their rating changes using any rating predictor?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

why -ve at 3.8k rank?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -9 Vote: I do not like it

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?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    the point is to make suboptimal solutions tle

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +142 Vote: I do not like it

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it -28 Vote: I do not like it

tourist round! OMG!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I realized that a little after posting the comment

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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
→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice D task, thanks

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +14 Vote: I do not like it

When will editorial be released?

worthy of being tourist XD

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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://codeforces.me/contest/1786/submission/192349129

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    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://codeforces.me/blog/entry/79024 since -Wconversion can be excessive sometimes.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
21 month(s) ago, # |
← Rev. 4   Vote: I like it +22 Vote: I do not like it

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
→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Still Waiting:(

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain Div2D to me, please? Thanks.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know when the tutorial will arrive?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This Chinese guy has a super good explanation and drawing here. You can try to understand it using your smart brain and some translation tools.

    My implementation is based on his idea.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a ton

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You might first try your best to read it, and if you have anything difficult to understand, you might contact me again.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks, I have read that and understood the idea, but for the implementation part i will have to learn segment trees. Thanks a lot for your help.

          → Reply
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

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; }

→ Reply