Привет!
VK Cup 2022 - Финальный раунд (Engine) начнётся уже скоро: 05.02.2023 15:05 (Московское время). Это соревнование предназначено для 16 лучших участников отборочного раунда VK Cup 2022. Раунд будет рейтинговым.
Остальных приглашаем на открытые для всех Codeforces Round 850 (Div. 1, основан на Финальном раунде VK Cup 2022) и Codeforces Round 850 (Div. 2, основан на Финальном раунде VK Cup 2022), которые начнутся в то же время и тоже будут рейтинговыми.
Все задачи финального раунда придуманы и подготовлены мной, а KAN придумал и подготовил две задачи для второго дивизиона. Также этот раунд стал лучше благодаря errorgorn, irkstepanov, qwerty787788, Merkurev, IgorI, PavelKunyavskiy, izban, Alexdat2000, ashmelev, Akulyat, mike_live, Ekler, MagnusCarlsen321_alt.
Вам будет предложено 6 задач и 3 часа на их решение.
Участники финального раунда поборются за призы:
- 1-е место — 300 000 рублей;
- 2-е место — 250 000 рублей;
- 3-е место — 150 000 рублей;
- 4-е место — 100 000 рублей.
UPD: Присоединяйтесь к видеотрансляции финала VK Cup 2022!
UPD: Разбор
Поздравляем победителей финального раунда:
Также поздравляем победителей зеркала:
omg tourist round!
omg tourist round!
omg tourist round!
omg tourist round!
Very good, very good
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"."
This reminds me of "This reminds me of "Don't use the same trick twice"."
Interesting.
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 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. :/
?????????????
is it rated for you?? :)
Note the unusual time (⓿><⓿)
omg lazy editorial round!
omg lazy editorial round
Желаю удачи финалистам
omg tourist round!
omg tourist round!
omg yet another lazy editorial round!
Also omg no score distribution round.
stO tourist Orz But I'm going to start school this Sunday.
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
Unfortunately，rating should be between 1,900 and 9,999 in order to register for the contest of div1.
orz tourist
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.
codeforce is the best!
Hope problem C is solvable this time
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.
Tourist round = the hardest round
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
Omg tourist round!
omg trash round!
not realy, It must be a good round!
omg editorial after 10 days 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.
afk btw i'
ok
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!
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.
Nice!!!
Did you do it on purpose or accidentally?
While attempting problems you can feel that this is tourist round.
Div 2 speedforces
Div 2 Speedforces
So, what tourist round has?
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...
I don't like the round anyway... huge work for 1B and 1C
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
Couldn't make it bc the contest was at 4am. Think I might have dodged a bullet there. :/
Speedforces or Implementation-forces
YES ~ tourist probably
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.
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.
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.
Is Div 2 D just a case work or is there any other methods?
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?
It'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 \lt = x$$$. Let's call a point $$$a_i$$$ useless if $$$f(a_i) \gt a_i$$$ and $$$cnt(a_i) \gt = 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.
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
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?
What programm do you use to see performance?
cf carrot extension
Thanks :)
well it's broken for me and i don't know why
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
couldn'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.
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?
Resolve 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 1and rearranging it we get1 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 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!
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.
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
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 / 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?
Yup , I thought the same , sadly couldn't remove bugs in my code. This approach should work.
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
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://mirror.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.
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:
Oh, by the way, this round put the ♰tourist♰ back in first place!
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://mirror.codeforces.com/contest/1786/submission/192315809
I really like 1C. But 1E is just stupid implemention.
can you explain your idea for 1C.
I become A CM again!
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://mirror.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://mirror.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 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:
Then we can calculate them by FFT. The answer is
.
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)$$$
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
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
You might first try your best to read it, and if you have anything difficult to understand, you might contact me again.
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.
Can anybody help me find why am I getting WA on this submission for Div2-C.
I don't know maybe there is something silly that is escaping my eye, in which case I'm sorry. But, I just can't figure out where am I getting WA. (can't see the test case either).
when n == 1, the answer would be a[0]-1, not a[0].
Where is official editorial? I want to see solution of Div2-B
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
MikeMirzayanov It's been a week, I have even posted a blog about it. Can you please look into 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.
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; }