Codeforces Round #850

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 Sunday, February 5, 2023 at 12:05UTC. 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, I_Remember_Olya_ashmelev, Akulyat, mike_live, Ekler, Kalashnikov for making this round better.

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

• 7 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

  • 7 days ago, # ^ | ← Rev. 4 →   -244 The comment is hidden because of too negative feedback, click here to view it

    • 7 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

      • 7 days ago, # ^ | Me when I see an unoriginal comment chain:

        • 7 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

      • 7 days ago, # ^ | What about me?

        • 7 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

          • 6 days ago, # ^ | This reminds me of "Don't use the same trick twice".

            • 6 days ago, # ^ | This reminds me of "Don't use the same trick twice".

              • 6 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

              • 5 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

              • 5 days ago, # ^ | XD..lol you got some -

              • 4 days ago, # ^ | ← Rev. 2 →   0 OMG Tasir Vai

              • 2 days ago, # ^ | OmG solved E

          • 5 days ago, # ^ | Another Spoiler?

            • 5 days ago, # ^ | Interesting.

        • 5 days ago, # ^ | omg tourist round

• 6 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

• 5 days ago, # ^ | Why there isn't tutorial up to now?

• 7 days ago, # ^ | Candidate Masters in div 1 will be cooked

  • 7 days ago, # ^ | First div1 round in my life! Which happens to be a tourist round! Wish all of us good luck.

• 6 days ago, # ^ | omg tourist round:)

• 5 days ago, # ^ | omg lazy editorial round

• 7 days ago, # ^ | dont worry, this time tourist will only need 10 days to post the editorial

  • 7 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

• 6 days ago, # ^ | It's a tourist round. Hopefully the problems are worth no editorial. :/

• 5 days ago, # ^ | ?????????????

• 7 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

• 7 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

• 6 days ago, # ^ | All rated rounds have English problem statements, so you should not care about translation

• 7 days ago, # ^ | The comment is hidden because of too negative feedback, click here to view it

7 days ago, # |

• 7 days ago, # ^ | codeforce is the best!

• 7 days ago, # ^ | 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.

  • 5 days ago, # ^ | 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.

• 5 days ago, # ^ | 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 :)

• 7 days ago, # ^ | Apparently Yes.

• 6 days ago, # ^ | we are on the same boat

• 7 days ago, # ^ | OMG, sir, do not mention sinful dangerous family-unfriendly word on Codeforce !!1!!!1!1!

• 6 days ago, # ^ | 5:30 pm for me Sir.

• 6 days ago, # ^ | Happy Lantern Festival!

• 6 days ago, # ^ | Happy Lantern Festival!

• 6 days ago, # ^ | ← Rev. 2 →   +7 Dude thing that matters is "Codeforces Round".

• 6 days ago, # ^ | same here i also got feeling it will be a hard round but I might just become pupil.

• 5 days ago, # ^ | Downvoting me just because I stated some really bad FACT about tourist? You guys are really brainless...

• 6 days ago, # ^ | 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.

• 6 days ago, # ^ | So I'm really interested in how to solve 1B so fast.

  • 5 days ago, # ^ | This is my code for 1B 192297272, you may have a look.

  • 5 days ago, # ^ | I used six vectors to maintain the indices with a more and without a . An element in and an element in could be erased in one exchange. This type of exchange can be applied as much as possible. Then there remains only tuples shaped like , each of which can be erased in two exchanges. It's not so hard to implement =)

    • 5 days ago, # ^ | Same with mine. (So I code like an IGM lol

    • 4 days ago, # ^ | Hi, can you help me prove why this strategy is optimal regarding number of exchange times?

      • 3 days ago, # ^ | It is easy to see that we would only transform two elements shape like and into , or simply erase two elements and , where are different letters. One exchange will decrease the total number of elements by or . So one can just maximize the number of exchanges of and . If there are elements and but we don't exchange them, then we will exchange and to and , respectively. Obviously, it's worse than simply erase and with one exchange. So if there are elements and , we can just erase them. If there isn't a pair of elements shaped like and , there are the same number of elements . We can only transform into since are equivalent, and then erase and with one exchange.

        • 42 hours ago, # ^ | Thank you so much!

• 6 days ago, # ^ | but there is a huge score difference, for example 750 points between D and C so it's kinda justified

• 5 days ago, # ^ | Couldn't make it bc the contest was at 4am. Think I might have dodged a bullet there. :/

• 6 days ago, # ^ | you don't really need to find x, but just need to get hold of a range ie. l,r such that l<=x<=r and then if l>r then output no otherwise yes

• 6 days ago, # ^ | YES ~ tourist probably

• 6 days ago, # ^ | Though my problems were comparatively easier but still I was able to solve only 1

• 6 days ago, # ^ | ← Rev. 2 →   +3 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

  • 6 days ago, # ^ | What dose "dp" stand for? I thought it cannot be "dynamic programming"

    • 6 days ago, # ^ | haha, yes i didn't ask for your dynamic programming, here Dp stands for actually display picture or account picture.

      • 6 days ago, # ^ | Yang Chaoyue, a Chinese actress.

• 6 days ago, # ^ | Me too!!Got stuck and got 9 WAs :(

• 6 days ago, # ^ | ← 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.

  • 6 days ago, # ^ | ← 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.

• 6 days ago, # ^ | 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.

  • 6 days ago, # ^ | Wow clean and smooth implementation

• 6 days ago, # ^ | "If there are multiple solutions, print any", this sentence was missing at the beginning in 1B, that was bad.

• 6 days ago, # ^ | 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.

• 6 days ago, # ^ | See my comment Although it's not elegant, I think it's easy to understand.

• 6 days ago, # ^ | 1D can be solved in dynamic programming and polynomial tricks in time, but I've heard there exists other solutions which do not require polynomial or the modulo .

• 6 days ago, # ^ | Which extension/website you use to get predictions? CF preictor extension is currently now working for me.

  • 6 days ago, # ^ | Which browser are you using?

  • 6 days ago, # ^ | And a typo: not -> now

    • 5 days ago, # ^ | Yeah. You are right

• 6 days ago, # ^ | what is FST?

• 6 days ago, # ^ | Oh, didn't FST. So my rating won't drop too much.

  • 6 days ago, # ^ | why so worry about rating?

• 6 days ago, # ^ | Wait till the System Testing gets over.

• 6 days ago, # ^ | It's graph problem

• 6 days ago, # ^ | ← Rev. 2 →   0 Mistaken, ignore.

  • 6 days ago, # ^ | Div1E, not Div2E

• 6 days ago, # ^ | Yes that's it

• 6 days ago, # ^ | Even after that you completed the contest withing 2 and half hours , really appreciating.

• 6 days ago, # ^ | The submissions are not public yet.

• 6 days ago, # ^ | Is this is a implementation problem?

• 6 days ago, # ^ | Same here, pretty much hardcoded everything only to get WA in the end for D

• 6 days ago, # ^ | damn, nice to see you on cf wilo

• 6 days ago, # ^ | What programm do you use to see performance?

  • 6 days ago, # ^ | cf carrot extension

    • 6 days ago, # ^ | Thanks :)

    • 6 days ago, # ^ | well it's broken for me and i don't know why

      • 6 days ago, # ^ | i am also facing some problems, sometimes it works sometimes it gives error

• 6 days ago, # ^ | How t solve 1D?

  • 6 days ago, # ^ | ← Rev. 2 →   +10 You do a dp of size , where number of ways that the number leads (is the highest value) a group of size , 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... :(

    • 5 days ago, # ^ | Can you please explain the reasoning behind the transition between the states?

• 6 days ago, # ^ | Based on previous experience, will be after about 1 week.

• 6 days ago, # ^ | ← Rev. 2 →   +1 Yes, that's what I did. see code

• 6 days ago, # ^ | For me, I shifted every cake by the same amount . Note that . This means that . So iterate over every and check that there is some that satisfies all the conditions for all by maintaining an overall lower bound and upper bound of the possible values of . 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 , so the answer is no. Otherwise, the answer is yes.

• 6 days ago, # ^ | My solution of D is a very ugly implementation

  • 6 days ago, # ^ | 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

    • 6 days ago, # ^ | I counted all combinations and greedily matched those that benefit both people After that greedily matches those that benefit only one of them

  • 6 days ago, # ^ | 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?

    • 6 days ago, # ^ | Indeed, my implementation uses 9 queues and 600 lines of code. 192373089 It was submitted after the contest ended.

• 6 days ago, # ^ | My ugly implementation of div2D uses 9 queues and requires 600 lines of code 192373089 I couldn't finish the implementation during contest.

• 5 days ago, # ^ | My implementation is so ugly that I had to use goto in c++.

• 6 days ago, # ^ | ← Rev. 2 →   +6 Idea

  • 6 days ago, # ^ | 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?

    • 6 days ago, # ^ | ← Rev. 4 →   +3 For cycle of length 2: If suppose person needs and it has an extra and if the person needs an and it has extra , 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 person needs and it has an extra and if the person needs an and it has extra , and if the person needs and it has an extra , we can first perform the swap between and person so now person needs and it has an extra , then we can perform the swap between and person. So all three will be satisfied in 2 operations.We can also do this for all possible combinations of letters.

      • 6 days ago, # ^ | Ok i understand now, thank you.

• 6 days ago, # ^ | how it is similar, can you please elaborate sir

  • 6 days ago, # ^ | In both the problems you only need to resolve the cycles of length 2 then cylces of length 3.

• 6 days ago, # ^ | I don't get it.

  • 6 days ago, # ^ | the second testcase is 4 1 5 4 1 1 and rearranging it we get 1 1 4 5 1 4.

    • 6 days ago, # ^ | However personally I think this may just be a coincidence and could not prove anything.

    • 6 days ago, # ^ | Guess I'm too Indian to understand this.

      • 5 days ago, # ^ | I can see some sums with 69 that's all

• 6 days ago, # ^ | ← Rev. 2 →   +10 I have the same question. Maybe tourist also surf foreign websites? (wwwww

• 6 days ago, # ^ | Heh, Heh, Heh, aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

• 6 days ago, # ^ | Agreed.

• 6 days ago, # ^ | Oh sorry I was talking about A2

• 6 days ago, # ^ | Since participation is less

• 5 days ago, # ^ | Yup , I thought the same , sadly couldn't remove bugs in my code. This approach should work.

  • 5 days ago, # ^ | Yeah this looked like an implementation heavy sum

• 5 days ago, # ^ | the point is to make suboptimal solutions tle

• 5 days ago, # ^ | A single dispenser can never serve >1 cakes at a time without spilling (Given that w >= h)

  • 5 days ago, # ^ | Thanks, I realized that a little after posting the comment

• 5 days ago, # ^ | ← Rev. 2 →   0 My brute force solution with less ugly code and less time :)

  • 5 days ago, # ^ | Is there any elegant solution for 1B/2D is present which handle all the cases without writing explicitly if else conditions?

    • 5 days ago, # ^ | ← Rev. 3 →   0 Well, you can look at my submission https://codeforces.com/contest/1786/submission/192325004 It is still ugly though but at least solves this issue with ifs

    • 5 days ago, # ^ | 's code is enlightening.

• 5 days ago, # ^ | Upvoted just because of how painful that looks.

• 5 days ago, # ^ | I was thinking my code is the ugliest code, but you proved me wrong :)

• 5 days ago, # ^ | It was impressive that you were able to pull off this during contest. Whenever I try to write ugly code. I fail to submit it during contest.

• 5 days ago, # ^ | where is the editorial? i cant find it.......

• 5 days ago, # ^ | ← Rev. 2 →   +5 b'_i=b_i+x a_i-w<=b'_i-h a_i+w>=b'_i+h a_i-(w-h)<=b'_i<=a_i+(w-h) (a_i-b_i)-(w-h)<=x<=(a_i-b_i)+(w-h) if max(a_i — b_i) — (w-h) <= min(a_i — b_i) + (w-b) : "YES" else : "NO" i got idea from his code : https://codeforces.com/contest/1786/submission/192315809

• 4 days ago, # ^ | can you explain your idea for 1C.

• 5 days ago, # ^ | I also thought of binary searching for a value in range that we are going to add to every and see if every 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.

  • 5 days ago, # ^ | 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

• 4 days ago, # ^ | ← 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://codeforces.com/blog/entry/79024 since -Wconversion can be excessive sometimes.

  • 4 days ago, # ^ | Thanks mate my code worked because of this. Thanks for this detailed answer

• 3 days ago, # ^ | Could you please elaborate on how to set the coefficients of the polynomials to get the result after the convolution for each ? I'm struggling with the binomial coefficients, they seem too dependent on the pairs

  • 3 days ago, # ^ | ← Rev. 3 →   +3 In fact, , so you can rewrite the original formula like this: 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.

    • 3 days ago, # ^ | Thanks a lot! I get it now.

• 3 days ago, # ^ | I have similar formula, albeit no nested sum involved. Is it possible to calculate dp[n][k] without summoning monsieur Fourier?

  • 3 days ago, # ^ | Maybe you can look at this comment.

• 4 days ago, # ^ | ← 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

  • 4 days ago, # ^ | Thanks! That's quite the brute-force solution. I hope the tutorial can come out and provide a more elegant solution other than direct brute-forcing, but I don't think it'll happen lol.

• 4 days ago, # ^ | The last tutorial of the contest hosted by tourist hasn't arrived yet, so it might never arrive sadly.

  • 4 days ago, # ^ | I didn't paid attention to that. That's sad. Thanks for letting me know though.

• 3 days ago, # ^ | 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.

  • • 3 days ago, # ^ | You might first try your best to read it, and if you have anything difficult to understand, you might contact me again.

      • 3 days ago, # ^ | 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.

• 3 days ago, # ^ | when n == 1, the answer would be a[0]-1, not a[0].

  • 3 days ago, # ^ | I see, definitely a very silly error. Thankyou so much.