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

**UPD:** Editorial

Congratulations to the winners:

omg tourist round!

omg tourist round!

omg tourist round!

omg tourist round!

Me when I see an unoriginal comment chain:same here

yes

What about me?Very good, very good

SpoilerThis reminds me of "Don't use the same trick twice".

This reminds me of "Don't use the same trick twice".

This reminds me of "Don't use the same trick twice".

This reminds me of "This reminds me of "Don't use the same trick twice"."

XD..lol you got some -

OMG Tasir VaiOmG solved E

Another Spoiler?Interesting.

omg tourist round

omg codeforces round.

WORST CONTEST I'VE EVER SEEN

Why there isn't tutorial up to now?

note: the unusual duration for 6 problems

Candidate Masters in div 1 will be cooked

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

LOL.

omg tourist round:)

omg tourist round:)

omg lazy editorial round

omg tourist round

inb4 long wait for the editorial

dont worry, this time tourist will only need 10 days to post the editorial

you mean 10 years ?

It's a tourist round. Hopefully the problems are worth no editorial. :/

?????????????

shhh"All the problems are authored and prepared by me."

omg tourist round

Note the unusual time(⓿><⓿)omg lazy editorial round!

omg lazy editorial round

XD

omg tourist round!

omg tourist round!

Will you post editorial this time?

omg yet another lazy editorial round!

Also omg no score distribution round.

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

yay~

omg lazy editorial round!

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

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

I think Benq will not participate in this contest.

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

Let's go!

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.

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

God round again.

petition to change codeforces.com to tourist.com

DOWNVOTES motivates me!!

codeforce is the best!

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.

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.

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.

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.

That's exactly what happened :)

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

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?

Yes Sir.

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

Apparently Yes.

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

Great, Another Cock and ball torture!!!!!!!!

This round is going to be difficult)omg trash round!

not realy, It must be a good round!

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.

we are on the same boat

Do take note of the unusual time of the contest.YES!!

afk btw i'

ok

OMG, sir, do not mention sinful dangerous family-unfriendly word on Codeforce !!1!!!1!1!

6 problems 3 hours, so scare!

Yet Another tourist round

.

Will it be codeforces mode or ICPC mode?

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

5:30 pm for me Sir.

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

omg Lantern Festival round!

Happy Lantern Festival!

Happy Lantern Festival!

what about

Score distribution?!Dude thing that matters is "Codeforces Round".

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

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

Let us enjoy the contest without thinking much about ratings changes.Hoping to do atleast 2-3 problems.

Horrible meme ever

Candidate Masters in div 1 will be cooked

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.

No score distribution again!

Hoping for 18 plus points...

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

Guts Feeling, It will be a hard round.

same here i also got feeling it will be a hard round but I might just become pupil.

Nice!!!

Did you do it on purpose or accidentally?

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

BORING CONTEST I QUIT

Div 2 SpeedforcesSo, what tourist round has?

NOthanks to MikeMirzayanov for Codeforces and Polygon platforms.NOnoted unsual time.NOscore distribution.I know that sometimes being the best CPer allows you behave in such way, but please at least respect people.

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

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

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.

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

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

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

Same with mine.

(So I code like an IGM lol

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

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.

Thank you so much!

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

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

but there is a huge score difference, for example 750 points between D and C so it's kinda justified

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

just thought about problem B Seems like binary search but I still don't know why it didn't work and give me tle

I wonder if the complexity I guess is nlog(w — h) where the worst case is nlog(100000) I create coordinates by a[i] + w and a[i] — w, b[i] + h and b[i] — h. First I put the first cake and first dispenser on the same x first coordinate then move only the first dispenser and check all n other ones if it fits. If one dispenser needs to move on the right and one on the left, it would be a no. Otherwise, if only one dispenser needs to move right, "lo = mid + 1", if only one move left, "hi = mid — 1", if none move, then it would be a yes. Btw my Eng is not too good so hope you guys understand.

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

SpeedforcesorImplementation-forcesYES~ tourist probablySpent 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)Though my problems were comparatively easier but still I was able to solve only 1

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

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

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

Yang Chaoyue, a Chinese actress.

Finally -100 :-)

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

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

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

Yes

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.

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.

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.

Wow clean and smooth implementation

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

UPD: solved it

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

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

time for tourist to settle down.

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

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

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.

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

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

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

1CIt's easy to see that every time you have to move all the points such that all the places from $$$1..m$$$ are filled and $$$m$$$ is minimum. Let $$$f(x)$$$ be the number of $$$a_i$$$ such that $$$a_i <= x$$$. Let's call a point $$$a_i$$$ useless if $$$f(a_i) > a_i$$$ and $$$cnt(a_i) >= 2$$$ because in this case, you need not move the point at position $$$a_i$$$ to any other point and more than one point is sitting at position $$$a_i$$$. So, adding an element iteratively will create at most one useless point (if you remove all the useless points previously) and remove the current useless point if exists. Now the answer will be $$$sum(remaining points) - m*(m+1)/2$$$. You can implement this idea using lazyseg tree and find the useless point by binary searching on lazyseg tree.

Thank you!

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

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

Which extension/website you use to get predictions? CF preictor extension is currently now working for me.

Which browser are you using?

Chrome

And a typo: not -> now

Yeah. You are right

what is FST?

Oh, didn't FST. So my rating won't drop too much.

why so worry about rating?

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.

Wait till the System Testing gets over.

very hard problems

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

It's graph problem

Really interesting div 1 contest, thanks!

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

Mistaken, ignore.

Div1E, not Div2E

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.

Yes that's it

C was too hard for me ;)

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

Please give some hint how to solve problem 2D.

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

why I am not able to submit solutions, it says contest is over even though 80 mins are left? Is it so that you have to participate in initial rounds so as to participate in the Final Round? It does display System Check is Pending.

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

The submissions are not public yet.

Is this is a implementation problem?

Same here, pretty much hardcoded everything only to get WA in the end for D

Especially liked Fdamn, nice to see you on cf wilo

My worst performance in a while T-TWhat programm do you use to see performance?

cf carrot extension

Thanks :)

well it's broken for me and i don't know why

i am also facing some problems, sometimes it works sometimes it gives error

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

So when will system test begin?

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

How t solve 1D?

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

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

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

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

where editorial?

Based on previous experience, will be after about 1 week.

Cool round!))

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

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"

Yes, that's what I did. see code

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.

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

My solution of D is a very ugly implementation

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

I counted all combinations and greedily matched those that benefit both people

After that greedily matches those that benefit only one of them

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?

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

It was submitted after the contest ended.

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

I couldn't finish the implementation during contest.

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

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

Any hints / elegant approaches on solving div2-d?

IdeaResolve cycles of length 2 then resolve cycles of length 3

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?

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.

Ok i understand now, thank you.

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

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

Problem

how it is similar, can you please elaborate sir

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

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

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

I don't get it.

the second testcase is

`4 1 5 4 1 1`

and rearranging it we get`1 1 4 5 1 4`

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

Guess I'm too Indian to understand this.

I can see some sums with 69 that's all

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

Heh, Heh, Heh, aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

Why i can't upsolve?

omg tourist round!!!

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.

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

How to solve the "Letter Exchange"?

my first div2. really good

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.

Agreed.

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

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

amazing round!

why my submission page is not loading? When I am opening the page it shows Your text to link here... . This happened after the contest.

Can anyone see their rating changes using any rating predictor?

No

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

Oh sorry I was talking about A2

why -ve at 3.8k rank?

Since participation is less

for

Problem : Div1B / Div2DMy 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?

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

Yeah this looked like an implementation heavy sum

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

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?

the point is to make suboptimal solutions tle

Editeded: thx I manged to find the error actually

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

tourist round! OMG!

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.

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

Thanks, I realized that a little after posting the comment

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

My brute force solution with less ugly code and less time :)

Is there any elegant solution for 1B/2D is present which handle all the cases without writing explicitly if else conditions?

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

$$$\color{black}{j}\color{red}{iangly}$$$ 's code is enlightening.

Upvoted just because of how painful that looks.

I was thinking my code is the ugliest code, but you proved me wrong :)

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.

Hello Friends!!!

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 meOh, by the way, this round put the ♰tourist♰ back in first place!

where is the editorial? i cant find it.......

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

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

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

can you explain your idea for 1C.

Nice D task, thanks

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

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.

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

When will editorial be released?

worthy of being tourist XD

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.com/contest/1786/submission/192349129

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.

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.

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.

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

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

couldput in the right part (which are in the range $$$[2, k-1]$$$), and there areactually$$$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:Then we can calculate them by FFT. The answer is

.

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

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:

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

Thanks a lot! I get it now.

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

Maybe you can look at this comment.

Still Waiting:(

Can anyone explain Div2D to me, please? Thanks.

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

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.

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

Does anyone know when the tutorial will arrive?

The last tutorial of the contest hosted by tourist hasn't arrived yet, so it might never arrive sadly.

I didn't paid attention to that. That's sad. Thanks for letting me know though.

Here it is:

Editorial to previous tourist round

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

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.

Thanks a ton