Hello, Codeforces! ฅ(*`ω´*)ฅ

We are glad to invite you to take part in Codeforces Round #789 (Div. 1) and Codeforces Round #789 (Div. 2), which will be held on 08.05.2022 17:35 (Московское время).

The round will be **rated** for all participants from both divisions. Participants in each division will be offered **6** problems and **2** hours to solve them. Both divisions will share 4 problems.

The problems were written and prepared by funer, dark_light, FreshP_0325, Frank_DD, qsmcgogo, winterzz1, Heltion, TomiokapEace and me.

Thank to:

74TrAkToR for excellent coordination of this round! And translating the statements to Russian.

KAN for helping us to review and fix some statements.

TomiokapEace for helping us to translate

**all**the statements and tutorials to English.Heltion for giving valuable advice and helping us to fix some statements.

Elder_Giang, ddytxdy, volan.de.mort, kucipendik, Olly_Z, arseny.__., MichsSS, playf, TeaTime, gojira, lox123, AlexLuchianov, kpw29, Huah, Yzm007, Duck_sajin, Operation27, Venn, Nephry, Heltion, errorgorn, Um_nik, TadijaSebez, Prokhor08, Grigoreva-Irina, Dragonado, lunaTu and MiracleFaFa for testing this round and giving good advice.

MikeMirzayanov and his Codeforces team for amazing systems Codeforces and Polygon!

Here are some things I personally want to say. This is my second round. Three years have passed since the first round round 573 I held. Now I have graduated and worked. I like codeforces very much. Though I have already participated in work, haven't trained for a long time, my ability has degraded a lot, I will still come to codeforces to participate in the contest in my spare time. This time I also prepared some problems to propose a round, but for some reasons, most of them were rejected. In particular, one of my favorite problems was rejected because "many testers don't like it". I'm a little frustrated, but I also understand that the coordinator's job is to make the round better and more people like this round. I think it's a great honor to prepare round on codeforces and let so many people around the world try to solve the problem I prepared. I will accumulate some more interesting ideas for the next round and try to make more people like the problems I prepared.

I'd like to express my great gratitude to my friends for preparing this round with me, I don't think I can prepare this round alone without them. I really appreciate having the support of my good friends in my round.

In addition, the three naughty cats mentioned in the statement.(*=｀ω´=)ﾉ I understand that I shouldn't post pictures irrelevant to the statement, so I post it here ↓

**meow 0w0**

Finally, I hope you like the problems in this round, good luck and have fun!(≧ω≦)/

The score distribution will soon be published.

**UPD1: Although our coordinator allows to post the PDF of Chinese statements in the contest material, it seems that codeforces does not allow it. We are only allowed to post something after the round. So we will still post Chinese tutorials after the round.**

**UPD2**: List of contributors is a bit changed, and the score distribution will be:

Div.2:

**500 — (750 + 1000) — 1250 — 2000 — 2000 — 2750**Div.1:

**500 — 1250 — 1250 — 2000 — 2500 — 3500**

**UPD3: Note that the score of the last problem of Div.1 has changed, 4000 → 3500.**

**UPD4**: Editorial is out, and Chinese Tutorial will soon be published.

**UPD5**: Chinese Tutorial is out.

**UPD6**: Congratulations to the winners!

**Div.1**:

**Div.2**:

Sofa~ Enjoy the round.(By the way, kitty lemon is so cuuute>w<).

Maybe only Chinese know what does “sofa” mean here(XD).In Chinese, “sofa” has the similar pronunciation to “the first one to post a comment”.

Thanks for explanation~ Now you got sofa's sofa;)

Commonrain！orz！

sjfyyds!

sjfnb！！！

sjfnb!

sjfnb!

Chinese statement！Wow

So is this the first CF round contains Chinese statement? TBH in these recent days I'm also thinking about if it will be allowed to offer Chinese statement in my next round (if I will finish my problemset lol), and now surprisingly find your new round does it earlier.

Our coordinator said he was told not to do this. Maybe the standard rules of codeforces round prohibit doing this kind of thing but we didn't notice it(

SJF YYDS！！！

I want to click on “Vote：I like it”，but I click on “Vote：I do not like it” by mistak。How can I change it？ qvq

Don't mind（＾ω＾）

love em catss <3

Can't wait any more, let's enjoy sjf's round.

So, what's the interesting chinese statements? Something like "Super Idol的笑容 都没你的甜 八月正午的阳光 都没你耀眼 热爱 105 °C的你 滴滴清纯的蒸馏水"?

A cat round. Excited to read the problem statements of the round.

〜(￣▽￣〜)

There is only one statement that mentions cats, so it probably doesn't count as a cat round =^•ω•^=

I see meow, I upvote.

Thank you (ฅ'ω'ฅ)♪

I hope this round came easier than the last one

Don't expect chinese rounds to be easy ╥﹏╥

TraumaHope i will get my ratings top up (.-.*)

BTW the meowsmeowsmeows are really cute!

≧ω≦it is a nice cat .. I wish the round be good like the latest one ..I'll have a cat sooner or later! QAQ

Cats are cute ฅ(*`ω´*)ฅ

Cats will be with you sooner or later!

sjfnb！！！！ I hope everyone can have fun solving our interesting problems ~ o(*￣︶￣*)o

Wish you all a great rating gain.sjf nb

meow!

to tell the truth the problems we discarded can make up another contest

...on Codechef

Hope you can solve our interesting problems and gain high rating!

sjfnb!!!

znjjnb!!!

FreshP_0325 orz

Ready To Participate (づ｡◕‿‿◕｡)づ ❤.

sjfnb! I surely think that the problems will be wholesome and fun!

sjfyyds

As the fourth naughty cat no one talks about I am absolutely hurt. iN oRdEr To compensate for tHiS mIsTaKe I mUsT bE gIvEn +200

When I first registered for this round, my rating was below 1900. Now, I've registered again for the same round but in Div. 1 category. Which category am I supposed to participate in now?

Can I make submissions in both categories during the contest ( ಠ◡ಠ )?

You should cancel your registration for Div2, and even if you don't do it, Mike or other admins will remove participants in the wrong division before the contest.

I see, thanks.

sjfnb!

I hope that i will be a pupil

Я надеюсь что я стану учеником

Good luck for everyone!!!

Всем удачи!!!

I am curious about your favorite problem. As your favorite problem has got rejected, you can share it in chat

thank you codeforces!

Doin' upvote for the round & the MEOWs (^ω^)✧

meow! I upvote

Well, Chinese round, help me to be blue lol...

So when are you eating your cats?

my first div1 contest :D

any one pls tell that what does it mean (750+1000) in scoring distribution Div.2: 500 — (750 + 1000) — 1250 — 2000 — 2000 — 2750 does it mean that 2nd question will be off 1750 orr it will of 750 or 1000 i'm bit confussed

There will be two problem for B (B1, B2) Where score of B1 will be 750 and score of B2 will be 1000 And this two problem will be similar with different constraints

thxx buddy

sjf nb!!!

The cats look really tired after a long day of preparing the round.

what actually that 750+1000 mean (in div 2 scoring distribution)

2 very similar questions separated because of difference in difficulty levels.

Means number of questions are 7. Thanks

What about the wrong submission?

Permutationforces again

Problem C(div1) was really funny pretending to be a non-permutation problem.

How do you assign the values to each independent cycle? Because that's what the problem is about right?

$$$|a - b|$$$ is ultimately either $$$(a - b)$$$ or $$$(b - a)$$$.

So, for each independent cycle, after opening $$$|.|$$$, some numbers would have a coefficient of $$$+1$$$, some would have a coefficient of $$$-1$$$ and some would have $$$0$$$ (as they'd have both $$$+$$$ and $$$-$$$).

To maximize this, you'd need to take the largest possible values for $$$+1$$$ coefficient and smallest values for $$$-1$$$ coefficient.

So, if cycle has $$$k$$$ elements, we can mark $$$k/2$$$ suffix elements as $$$+1$$$, $$$k/2$$$ prefix elements as $$$-1$$$ and depending upon whether $$$k$$$ is odd, we can mark the first unused prefix after all operations as $$$0$$$.

server is tooo much fast guys :D

The memory in problem C is very annoying

Ya, like declaring 2 2-D arrays of O(5000^2) is giving runtime error !

I really don't see what's the point of that restriction. I ended up spending ~5 more mins and also got an extra penalty.

Dang, that problem B though :P

I think it should be swapped with C (looking at point distribtuion)?

Ugh! Headache from that B2 I'm done

Solved 4 again including E . I wonder what would they say now . All they wanted was to bully me and downplay me

Context

B2 to E in 20 minutes. Uhhh what would we say? You cheated again? Don't worry buddy, if you failed to solve div3 a,b,c and a week later solved E (with 92 ACs in div2) in 20' you would be famous in India as a genius soon, and you would be known. Until then we all assume you are cheating.

Can you even see the code for E another DSU and Maths problem ? It is even smaller than B1 and problem C is very similar to this. If you can solve this problem then C is cakewalk unless you make stupid mistakes like I did otherwise it is 5 minute problem

solved Problem C but didn't solve Problem B2 :(

Finally solved a FFT problem during contest. POG

Edit: I just overcomplicated Div 1D like a bot. Ignore this comment

what ?????

Maybe Im just stupid but I used NTT to solve Div 1D.

you can do it in O(n)???I did same :D. I was shocked seeing so many AC's so I thought a bit more later, and realized there was no need of FFT/NTT.

FFT is a tool for (sometimes sneaky) polynomial manipulation. However, not every polynomial manipulation is FFT. If you can simplify until you work with pointwise multiplications instead of convolutions/inverses/etc, it's faster.

I noticed the connection too, considered FFT but happened to write a solution without it.

Apologies, my earlier comment might have come of as slightly rude because I did not know that you can solve the problem by thinking about the operations in reverse so I really curious how FFT appeared.

Anyways, I just remembered that $$$n=10^6$$$ was the limit so I thought FFT couldn't pass since it was actually $$$O(n \log^2 n)$$$ even (I couldn't even get $$$O(n \log n)$$$ to pass 1548C - The Three Little Pigs when I tried it). I've hacked you with test like

I've tried to hack IntoTheNight but his NTT imple too strong... 1886ms

Edit:

Thinking about how your solution and the solution in the editorial becomes the same, I have realized that your solution can be simplified to $$$O(n)$$$ without much difficulty. So you are calculating the polynomial $$$P(x)$$$ where $$$[x^i]P(x)$$$ is the number of final arrays with $$$i$$$ zeros in the range $$$[1,n-k]$$$.

The number of initial arrays that can produce a final array is with $$$i$$$ zeros is $$$(k+1)^i \cdot k!$$$. Notice that taking the sum over all $$$i$$$ is same as finding $$$P(k+1) \cdot k!$$$ (we are evaluating $$$P$$$). We $$$P(k+1)$$$ without using NTT and solve in $$$O(n)$$$ using your method and this gives the exactly same calculation as the editorial

Rubbish round

C was easier than B2 :/

Hints for

Div2E/Div1CSolve a simpler problem first. You are given $$$k$$$ boxes numbered from 1 to $$$k$$$. Assign unique values to them from the set $$$1, 2, 3, \dots n$$$ such that $$$\Sigma_{i = 1}^{k} |val[i] - val[i + 1]|$$$ is maximized.

Answer:

`2*(Suffix sum of k//2 elements - prefix sum of k//2 elements)`

.Now, get rid of the 2 arrays to construct an array

`c`

where`c[i] = index of b[i] in a[i]`

.Array $$$C$$$ is a permutation, and will have several disjoint cycles. The answer for each cycle can be computed from the formula above. In the end, we need to assign a sign, $$$+, -, 0$$$ to the array $$$[1, 2, \dots n]$$$. Each disjoint cycle would contribute

`cc_size/2`

to the answer, for both the suffix and prefix.What was B2? Can someone provide me some testcases?

6 101000

and

4 1011

Bruh, solution to E is somewhat tedious and straightforward, but requires you to solve "sum up the total area of rectangles in a rectangle" queries. I spent the whole contest implementing it. Seems to pass pretests, but since it is the only problem I submitted, maybe I shouldn't have submit it at all when I was done...

My solution to E is: for each number, find its factorization (it is of $$$O(n \log n)$$$ for all numbers jointly) and also find closest numbers $$$L,R$$$ to the left and to the right of it that are larger than the number. Now let $$$i,j$$$ be the positions of $$$p_i \cdot p_j = p_k$$$ for the current number. Any segment $$$x,y$$$ such that

is valid. These equations define one of possible rectangles for allowed $$$(x,y)$$$ segments and your queries are like "find the area of the union of rectangles within a rectangle", which is doable with segment tree and sweepline in $$$O(n \log^2 n + q \log n)$$$ time overall.

Can you elaborate a bit on how to "find the area of the union of rectangles within a rectangle" ?

You can also use a segment tree with range set to value and range historic sum. That data structure is pretty easy to implement.

Basically, if the queries are $$$[a_i, b_i]$$$, loop over $$$b$$$ in increasing order, and maintain a segment tree such that at position $$$a$$$ we have a $$$1$$$ if the range $$$[a, b]$$$ is good, and $$$0$$$ otherwise. Then you can answer the queries with range historic sum queries.

To maintain the segment tree, you maintain in a stack the current suffix maximums (ignoring all numbers in positions after $$$b$$$). When you pop the stack, set the corresponding range in the segment tree to 0.

Next, you need to handle newly created pairs $$$i, j$$$ with $$$i \cdot j \leq n$$$. First, let $$$i = val[b]$$$ and loop over what $$$j$$$ is. If $$$i \cdot j = t$$$, $$$pos[t] < b$$$, and $$$t$$$ is the current suffix maximum in range $$$[x, y]$$$, set $$$[x, y] \cap [0, pos[j]]$$$ to $$$1$$$.

Finally, if $$$val[b]$$$ is the maximum in range $$$[x, b]$$$, and $$$i, j$$$ is the pair satisfying $$$i \cdot j = val[b]$$$, $$$pos[i], pos[j] < b$$$ that maximises $$$z = \min(pos[i], pos[j])$$$, we set $$$[x, b] \cap [0, z]$$$ to $$$1$$$.

Code: 156351162

What's the solution for B2, is it something to do with dp?

It can be solved without DP.

SolutionDivide $$$s$$$ into blocks of size 2. There are four different possible blocks: 00, 11, 01, 10. Let's notice, that we have to pay for each 01 or 10 block (because if the length of each segment is even, then we have only 00s and 11s). After noticing that, there is a simple solution. If there are no 00s and 11s then we can make all the characters equal (so the answer is n / 2 1). Otherwise, let's make all the characters before the first 00 or 11 equal to 0 or 1 respectively. Then pay if the last block $$$\ne$$$ current block. Implementation (perhaps, more clear than my words):

Implementationoh.. I was so stupid :(

...(nothing)

I want to know what's the intended solution for Div2C, cuz I just wasted 30 mins optimizing my original solution.

O(n2) using prefix sum .I also used seg tree before O(n2logn) but got TLE.

I use seg tree too, TLE too. qwq

my seg tree passed pretest using c++20 (TLE using c++14) but then i changed to prefix sum.

Iterate over B and C, with B from the front and C from the back. Use 2 fenwick/segment tree to find # of numbers small than B and C on the prefix and suffix. Edit: AC Submission

Let $$$D[i][j]$$$ be the count of pairs $$$(x, y)$$$, $$$x \leq i$$$ and $$$j \leq y$$$ such that $$$P_x > P_y$$$. This can be computed in $$$O(N^2)$$$ using dynamic programming.

Then for each $$$a < b$$$ such that $$$P_a < P_b$$$, add $$$D[b - 1][b + 1] - D[a][b + 1]$$$ to the answer.

The following thing works fine in terms of time: firstly for each $$$i$$$ and $$$m$$$ calculate $$$M(i, m)$$$ -- the number of elements of permutation, which are not greater than $$$m$$$ and have an index not greater than $$$i$$$, it's $$$O(n^2)$$$

Then we can iterate for $$$b$$$ and $$$d$$$, but for each $$$d$$$ also remember $$$M(b-1, d)$$$, so if we find $$$d$$$ s.t. $$$p_d < p_b$$$, it will add to the answer sum $$$\sum\limits_{i=b+1}^{d-1} M(b-1, p_i) $$$. It's also $$$O(n^2)$$$

anyone pls tell me what was the intuition and how you've solved div2 2 (b harder version )

Dynamic programming for both B1 and B2.

can you tell me what was your intuition in dp solution of B:/

Did anyone tried solving B2 with Binary search I tried but it failed on pretest2

Permutation Forces

Div 2 is too unbalanced

Wow, I made the last "pretests passed" submission in the whole Div.1 round, at 01:59:46.

My heart was beating soooo fast!

For me Div2 B2 >>> Div2 E

So,When will the editorial/tutorial be posted?A greenhand in codeforces....

F = this + this + this.

C was easier than B2 :/

Would love to know the solution of B2.

Solved B1 literally by "guessing" with no complete proof, feeling uncomfortable. Feel B2 could be solved by guessing also, but have no time to write it down. This is a bad experience. Really want to see clean solutions for B1 and B2 with PROOFs in the editorial.

The solution in the editorial is indeed clean. During the contest I missed an observation and used a more complicated solution.

Ordered set giving TLE in div2 C sed life :-(

desperately waiting for the solution to B2

Can B2 not be solved with 0-1 Knapsack? I feel like it is just the total number of segments — knapsack, but I could be wrong.

I couldn't solve b2, just waiting for an editorial solution

If you solved B1, you should have noticed that you only apply operations to 01/10 pairs. We can think of the string as blocks of 2 successive characters. We can then solve the problem with DP. Let $$$dp[i][0/1]$$$ be the minimum number of segments if the current pair of successive characters is turned into $$$0$$$ or $$$1$$$. Then the transitions are: $$$dp[i][0] = min(dp[i - 2][0], dp[i - 2][1] + 1)$$$, $$$dp[i][1] = min(dp[i - 2][1], dp[i - 2][0] + 1)$$$.

if you have done B1 its obvious that a block of two elements should be same.Now lets consider a case 10101101010011. Here for first two elements it can be 11 or 00. for third and fourth element it can be again 11 or 00.So first four elemnts can be either 1100,0011,0000,1111.it is optimal to choose 1111 as the next two bits are 11.if the next two bits were 00,it was optimal to choose 0000.So we can say that if for a particular block, where first element == second elemnt==11,we can make previous all blocks of two elements like that particular block and can merge into one segment.But if a previous block found such that the block elements are 00,then we cant do anything but to count a new segment.but if a particular block found which is 11,then we can easily merge that too!

more intuition: ------11----00----11 the dashed spaces represents blocks where first element != second element those spaces can be filled by 1 or 0.but the remaining 11,00,11 will not be changed as first element == second element. As dashed spaces can be formed by 0 or 1 the only thing deciding the segment whether there is a 00 infront of 11 or 11 infront of 00.So the answer is,for every i%2 ==0 check whether s[i+1]== s[i].if its true append the value of s[i]to an array.Now for every array[i] check whether array[i] != array[i+1].if its true ans will be increased by 1 as we have found a new segment

My submission to pC

The time complexity should be O(n^2),but I got TLE. Can somebody help me?

You are initializing a $$$5000 \times 5000$$$ array in every test case so your complexity is $$$O(t \cdot MAXN^2)$$$. You should use a vector instead. The same happened to my first submission. Imho this problem would be better off with single tests and a more generous ML.

I have same feeling with you;) Thanks for your helping~

DanielChangTW, native array with custom initialization is also fine. You just don't need to use initialization like

`short pre[5001][5001]={}`

, because in this case memset is being called. Otherwise no initialization is performed.Ok,I get it now.Thanks!

The funniest thing is how div1D was named "and permutations". Because the rest isn't :^)

1D is ezer than 1B and 1C !!!

Had to rewrite my solution to D2C from python to c++ because O(n*n*logn) with Fenwick wouldn't pass otherwise /:

Failed to solve B

It wasn't a Fenwick :kappa: ...

Yet I solved it with Fenwick

It is quite obvious that Fenwick in D2C is not an intended solution

Yet it solves the problem

I think div2 C is easier than div2 B2. div2 B2 caused me to have no time to solve div2 D......

It's obvious that it's intended, because B1+B2's score is 1750 while C's score is only 1250.

Well, B1 is very simple

The actual time consumer is B2

I don't think "B1 is very simple" unless the solution is clean with a complete proof of correctness. In particular, solving it using "intuitive guessing" is not clean. I would like to see a clean solution in the editorial.

Well, I get your point, yet not like we always prove solutions during the contest

How do you solve B1? I spent a long time on it to prove greedy solution correct.

Consider the sequence of the lengths of subsegments. The number of odd lengths must be even since the sum is even. Each odd-length subsegment must be changed. In particular, the leftmost must be changed, which means all the even-length segments until the second-from-the-left odd-length (excluding it) must be changed. Continue this argument for 3rd-4th, 5th-6th, and so on.

That's why you should read all the problems and take scoring distributions with a grain of salt.

But usually the difficulty of the problem increases gradually

Usually but not always...

I should have expected that it will be a trash contest from the blog vibes.

Ah, I see. It is trash only if you under-perform.

Do you know my opinion about every other contest?

Nevermind, it is because merge sort tree queries runs in O(log^2n) :(

I think A is the hardest among first 5 problems in div 1.

Seriously?

Yet in Div2 it has more solutions than D2B which is not even present in div1

B stands for Balance

how you become a legendary grandmaster, in just 8 contests

A is similar to 1400D - Zigzags

How to write

Tokitsukaze and Meetingwithout much pain? I had seen there several complex loops, and every time I tried to write them, I had gotten confusion.You can check my solution, I think it's pretty easy, and the code is short.

My solution for C with ordered set in C++ with O(n^2*logn) complexity was failing. Then i tried solution using 2 arrays in which space complexity was o(n^2) as well as the time complexity. It was giving MLE on test case 5. After optimizing the space for one of the arrays to O(N) the solution passed. I noticed someone else solution after the contest who had also used 2 arrays with o(n^2) complexity but used int than long long as I had done. Do data types affect space so much that a whole test case failed because of it?

Using 32-bit instead of 64-bit ints roughly halves the memory requirement, which helps just as much as optimizing by using one array.

I have a fun solution for DIV2 B1, pretty much different from other people's solutions :

Div 2 B1 solutionSo for this problem, we don't care about the minimum number of subsegments. And so now, we notice an interesting property : If we have a block (same bits) of length (let's say 4), we can always divide it in 2 pieces (2 and 2). So, by repeating this operation, we get blocks of length 2. That means if we have a good string s, we can have a good string s with all subsegments of length 2. In other words, we have to make each {i, i + 1} (with i odd) bits same, and that is easy because the length is only 2 : if the bits are different, it's 1, and if it's equal, it's 0.

And by summing up all this costs for this subsegments, we can calculate the minimum number of operations required to make s good !

Is B2 DP?

I saw that one person used dp, but I am pretty sure that is not the intended solution

Yes, it's fairly standard dp once you notice that you only need to apply the operation to 01/10 pairs.

I thought of 0-1 knapsack DP as soon as I read the problem statement, but I didn't see anyone using it. I can't figure out what's wrong with using knapsack?

i solved it using DP

B1 and B2 can be solved with DP

states => i, parity of 0, parity of 1, last character parity

transitions try to make previous consecutive frequency even for any of the two elements at every recursion or just pass it with default values als note that at every point in recursion maintain either p1 == 1 or p0 == 1.

Solution

CodeFixed my bug on E 10 minutes after the contest, by just changing two chars. TaT

Seriously, I've never seen a problem more stupid than Div.1 E.

Man E is super easy. I think B1/B2 is harder than E. Why do we need to bring a super easy question like this to E?

I told you but you were busy with your agenda

Hi Naman, At how much cost did you sell your ID?

yeh MnC wala Naman Arora hai na?

My solution for $$$Div2$$$ $$$B$$$:

Easy part:First observe that any valid solution consists of even ones, even zeros, even ones, ... So, any $$$prefix_i$$$ of odd length with $$$a[i]\neq a[i+1]$$$ will require at least one operation, the lower bound on number of operations is the count of such prefixes.

The mentioned lower bound is achievable, as such odd prefixes appear in the form of, e.g., even prefix followed by odd ones (odd prefix), even zeros (odd prefix), even ones(odd prefix), odd zeros (even prefix). So just changing the last value in each odd prefix will make all the prefixes where the values change to be even.

Hard part:The objective here is to choose the values to change in a way to increase the connectivity of segments with the same value. From the previous proof, observe that any even $$$prefix_i$$$ ending with $$$2$$$ zeros or $$$2$$$ ones implies that in the final solution $$$prefix_i$$$ should end with the same value, otherwise more operations will be done.

So, we can greedily search for the next even prefix ending with $$$2$$$ zeros or $$$2$$$ ones and make the whole segment have the same value (starting from after the previous even prefix). When we cannot find any more such prefixes (reached the end of array), if the current segment we are working on starts from $$$i\neq 0$$$, we can choose $$$a[i-1]$$$ and use it in the whole segment, otherwise we can just choose any value.

Submission

That balance is 10 out of 10 basically, but you've tried)

at least this round is better than the last chinese one

Spoilerhttps://codeforces.com/blog/entry/95393

Why C does not pass with Ordered_Set but applying Fenwick Tree it does?

I think such things should not happen in future either both should or both should not.

I guess it's because ordered_set has a higher constant than fenwick tree.

Huh? Just don't use ordered_set when the TL is tight. The constant for it is way too big.

idk my order set solution passes with half of time limit 156302146

Thats because you have used one ordered set I used 2 and it failed.

156324323

can you explain your solution more ? thanks in advance.

we iterate over (a,c) pairs and keep track of (b,d) pairs, we go from left to right iterating over c, then a < c, when we move c we add to order set (all possible d) and when we move a we add it as b

This round let me feel that I sould give up

Dude if you were specialist at one point that should let you know that you have at least some level of talent.

Not untrue !

Thanks to the round authors for problem E, I liked it very very much. Unfortunately didn't have to implement it during the contest due to sucking too much at combinatorics >_>

for B1 just look at s[i] and s[i+1] if they are different then we have no choice other than to change any one of them.

for B2 just work in two length contiguious substrings if s[i] and s[i+1] are different then simply look at s[i-1] and make these equal. if s[0] and s[1] are different then once choose both of them 0,0 and find the values using above procedure, similarly for 1,1 and take the minimum of these two.

https://codeforces.com/contest/1678/standings/friends/true#

Waiting for usual YT editorials for last div2 problems :)

WTF!!

link this problem is the same as problem C I replaced every < by == and got accepted

And the question of this link is weaker than the C.....

The pretests are so powerful that the issue occurred Runtime error on test 4 LOL

Problem C O(N*N*log) AC : 156339292

how is can fit when N up to 5000?

Codeforces servers are very fast, they can do ~1e9 operations per sec. so your solution fits nicely

I think this is also the same complexity O(N*N*log)? 156359874

yes, but the constant factor is bigger

Sorry for violating the rules of Codeforces, this account and OLFH are both my accounts and I just want to get higher rank for both of them. I didn't notice that my action violated the rules of Codeforces. I'm so sorry, I will not repeat this action again in the future. I promise

i was actually giving contest with my alternate account but i forgot that i have to give from the main account so i submitted the solution in the second account ,now i got a message that i will be punished for doing this please sir next time i will take care please give me rating for this contest :/

Tasks were so difficult. The last two contests were difficult and incomprehensible for me. Due to the last contest my rating has dropped. I think this will not happen again in the next contests and I can raise my rating again.

I agree with you

Guys who created this round, what do you think about Winnie the Pooh?

As a Chinese,exicted for Chinese statement!

It seems that I am the only person who FST on Div.1 B. :<

Achievement unlocked: "Perfectly Balanced": obtain 0 delta

OMG! The C is tooooooo annoying!!!!,QAQ

.....TLE or MLE(I know the reason is that Im tooooo weak)

A good contest!

Thank you for the Chinese tutorial.