### tokitsukaze's blog

By tokitsukaze, 2 weeks ago,

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:

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:

• +766

 » 2 weeks ago, # | ← Rev. 4 →   +25 Sofa~ Enjoy the round.(By the way, kitty lemon is so cuuute>w<).
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +13 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”.
•  » » » 2 weeks ago, # ^ |   +16 Thanks for explanation~ Now you got sofa's sofa;)
•  » » » 2 weeks ago, # ^ |   0 Commonrain！orz！
 » 2 weeks ago, # |   +2 sjfyyds!
 » 2 weeks ago, # |   +1 sjfnb！！！
 » 2 weeks ago, # |   +1 sjfnb!
•  » » 12 days ago, # ^ |   0 sjfnb!
 » 2 weeks ago, # |   +8 Chinese statement！Wow
 » 2 weeks ago, # |   +38 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.
•  » » 2 weeks ago, # ^ |   +21 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(
 » 2 weeks ago, # |   +3 SJF YYDS！！！
 » 2 weeks ago, # |   +3 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
•  » » 2 weeks ago, # ^ |   +30 Don't mind（＾ω＾）
 » 2 weeks ago, # |   0 love em catss <3
 » 2 weeks ago, # |   0 Can't wait any more, let's enjoy sjf's round.
 » 2 weeks ago, # |   +62 So, what's the interesting chinese statements? Something like "Super Idol的笑容 都没你的甜 八月正午的阳光 都没你耀眼 热爱 105 °C的你 滴滴清纯的蒸馏水"?
 » 2 weeks ago, # |   +1 A cat round. Excited to read the problem statements of the round. 〜(￣▽￣〜)
•  » » 2 weeks ago, # ^ |   +3 There is only one statement that mentions cats, so it probably doesn't count as a cat round =^•ω•^=
 » 2 weeks ago, # |   +13 I see meow, I upvote.
•  » » 2 weeks ago, # ^ |   +11 Thank you (ฅ'ω'ฅ)♪
 » 2 weeks ago, # |   +1 I hope this round came easier than the last one
•  » » 2 weeks ago, # ^ |   +3 Don't expect chinese rounds to be easy ╥﹏╥ Trauma
 » 2 weeks ago, # | ← Rev. 4 →   -7
 » 2 weeks ago, # |   0 Hope i will get my ratings top up (.-.*) BTW the meowsmeowsmeows are really cute!
 » 2 weeks ago, # |   +5 ≧ω≦ it is a nice cat .. I wish the round be good like the latest one ..
 » 2 weeks ago, # |   0 I'll have a cat sooner or later! QAQ
•  » » 2 weeks ago, # ^ |   +3 Cats are cute ฅ(*ω´*)ฅ
•  » » 2 weeks ago, # ^ |   0 Cats will be with you sooner or later!
 » 2 weeks ago, # |   +3 sjfnb！！！！ I hope everyone can have fun solving our interesting problems ~ o(*￣︶￣*)o
 » 2 weeks ago, # |   0 Wish you all a great rating gain.
 » 2 weeks ago, # |   +9 sjf nb
 » 2 weeks ago, # |   +20 meow!
 » 2 weeks ago, # |   +39 to tell the truth the problems we discarded can make up another contest
•  » » 2 weeks ago, # ^ |   +41 ...on Codechef
 » 2 weeks ago, # |   +23 Hope you can solve our interesting problems and gain high rating!
 » 2 weeks ago, # |   +8 sjfnb!!!
•  » » 2 weeks ago, # ^ |   0 znjjnb!!!
 » 2 weeks ago, # |   +2 FreshP_0325 orz
 » 2 weeks ago, # |   0 Ready To Participate (づ｡◕‿‿◕｡)づ ❤.
 » 2 weeks ago, # |   0 sjfnb! I surely think that the problems will be wholesome and fun!
 » 2 weeks ago, # |   0 sjfyyds
 » 2 weeks ago, # |   +3 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
 » 2 weeks ago, # | ← Rev. 2 →   0 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 ( ಠ◡ಠ )?
•  » » 2 weeks ago, # ^ |   +4 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.
•  » » » 2 weeks ago, # ^ |   0 I see, thanks.
 » 2 weeks ago, # |   +5 sjfnb!
 » 2 weeks ago, # |   +6 I hope that i will be a pupilЯ надеюсь что я стану ученикомGood luck for everyone!!!Всем удачи!!!
 » 2 weeks ago, # |   +4 I am curious about your favorite problem. As your favorite problem has got rejected, you can share it in chat
 » 2 weeks ago, # |   0 thank you codeforces!
 » 2 weeks ago, # |   0 Doin' upvote for the round & the MEOWs (^ω^)✧
 » 2 weeks ago, # | ← Rev. 2 →   0 meow! I upvote
 » 2 weeks ago, # | ← Rev. 2 →   0 Well, Chinese round, help me to be blue lol...
 » 2 weeks ago, # |   -35 So when are you eating your cats?
 » 2 weeks ago, # |   +3 my first div1 contest :D
 » 2 weeks ago, # |   +8 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
•  » » 2 weeks ago, # ^ |   0 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
•  » » » 2 weeks ago, # ^ |   0 thxx buddy
 » 2 weeks ago, # |   0 sjf nb!!!
 » 2 weeks ago, # |   +4 The cats look really tired after a long day of preparing the round.
 » 2 weeks ago, # |   0 what actually that 750+1000 mean (in div 2 scoring distribution)
•  » » 2 weeks ago, # ^ |   0 2 very similar questions separated because of difference in difficulty levels.
•  » » » 2 weeks ago, # ^ |   0 Means number of questions are 7. Thanks
 » 2 weeks ago, # |   0 What about the wrong submission?
 » 2 weeks ago, # |   +55 Permutationforces again
 » 2 weeks ago, # |   +14 Problem C(div1) was really funny pretending to be a non-permutation problem.
•  » » 2 weeks ago, # ^ |   0 How do you assign the values to each independent cycle? Because that's what the problem is about right?
•  » » » 2 weeks ago, # ^ |   +6 $|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$.
 » 2 weeks ago, # |   0 server is tooo much fast guys :D
 » 2 weeks ago, # |   +13 The memory in problem C is very annoying
•  » » 2 weeks ago, # ^ |   +4 Ya, like declaring 2 2-D arrays of O(5000^2) is giving runtime error !
•  » » 2 weeks ago, # ^ |   +5 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.
 » 2 weeks ago, # |   0 Dang, that problem B though :PI think it should be swapped with C (looking at point distribtuion)?
 » 2 weeks ago, # |   +4 Ugh! Headache from that B2 I'm done
 » 2 weeks ago, # |   -46 Solved 4 again including E . I wonder what would they say now . All they wanted was to bully me and downplay meContext
•  » » 2 weeks ago, # ^ | ← Rev. 4 →   +30 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.
•  » » » 2 weeks ago, # ^ |   -16 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
 » 2 weeks ago, # |   +9 solved Problem C but didn't solve Problem B2 :(
 » 2 weeks ago, # | ← Rev. 2 →   +8 Finally solved a FFT problem during contest. POGEdit: I just overcomplicated Div 1D like a bot. Ignore this comment
•  » » 2 weeks ago, # ^ |   -7 what ?????
•  » » » 2 weeks ago, # ^ |   +3 Maybe Im just stupid but I used NTT to solve Div 1D.
•  » » » » 2 weeks ago, # ^ |   -12 you can do it in O(n)???// Super Idol的笑容 // 都没你的甜 // 八月正午的阳光 // 都没你耀眼 // 热爱105°C的你 // 滴滴清纯的蒸馏水 #include #include #include #include using namespace std; using namespace __gnu_pbds; using namespace __gnu_cxx; #define int long long #define ll long long #define ii pair #define iii pair #define fi first #define se second #define endl '\n' #define debug(x) cout << #x << ": " << x << endl #define pub push_back #define pob pop_back #define puf push_front #define pof pop_front #define lb lower_bound #define ub upper_bound #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) #define all(x) (x).begin(),(x).end() #define sz(x) (int)(x).size() #define indexed_set tree,rb_tree_tag,tree_order_statistics_node_update> //change less to less_equal for non distinct pbds, but erase will bug mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); const int MOD=998244353; int n,k; int arr[1000005]; signed main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin.exceptions(ios::badbit | ios::failbit); int TC; cin>>TC; while (TC--){ cin>>n>>k; rep(x,0,n) cin>>arr[x]; int ans=1; rep(x,n-k,n) if (arr[x]>0) ans=0; rep(x,0,k) ans=ans*(x+1)%MOD; rep(x,0,n-k){ if (arr[x]==-1) ans=ans*(x+k+1)%MOD; else if (arr[x]==0) ans=ans*(k+1)%MOD; } cout<
•  » » 2 weeks ago, # ^ |   +23 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.
•  » » 2 weeks ago, # ^ |   +3 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.
•  » » 2 weeks ago, # ^ | ← Rev. 3 →   +13 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 1 1000000 0 -1 -1 ... I've tried to hack IntoTheNight but his NTT imple too strong... 1886msEdit: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
 » 2 weeks ago, # |   +17 Rubbish round
 » 2 weeks ago, # |   +14 C was easier than B2 :/
 » 2 weeks ago, # | ← Rev. 2 →   +15 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.
 » 2 weeks ago, # |   0 What was B2? Can someone provide me some testcases?
•  » » 2 weeks ago, # ^ |   0 6 101000and4 1011
 » 2 weeks ago, # |   +51 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...
•  » » 2 weeks ago, # ^ |   +10 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 $L < x \leq \min(i,j,k) < \max(i,j,k) \leq y < R$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.
•  » » » 13 days ago, # ^ |   0 Can you elaborate a bit on how to "find the area of the union of rectangles within a rectangle" ?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 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
 » 2 weeks ago, # |   +13 What's the solution for B2, is it something to do with dp?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +11 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): Implementation int n; string s; cin >> n >> s; char lst = '\0'; int ans1 = 0, ans2 = 0; for(int i = 0; i < n; i += 2) { if(s[i] != s[i + 1]) ans1++; else { if(lst != s[i]) ans2++; lst = s[i]; } } cout << ans1 << " " << max(1, ans2) << "\n"; 
•  » » » 2 weeks ago, # ^ |   0 oh.. I was so stupid :(
 » 2 weeks ago, # | ← Rev. 2 →   -64 ...(nothing)
 » 2 weeks ago, # |   0 I want to know what's the intended solution for Div2C, cuz I just wasted 30 mins optimizing my original solution.
•  » » 2 weeks ago, # ^ |   0 O(n2) using prefix sum .I also used seg tree before O(n2logn) but got TLE.
•  » » » 2 weeks ago, # ^ |   0 I use seg tree too, TLE too. qwq
•  » » » » 2 weeks ago, # ^ |   0 my seg tree passed pretest using c++20 (TLE using c++14) but then i changed to prefix sum.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 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
•  » » 2 weeks ago, # ^ |   0 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.
•  » » 2 weeks ago, # ^ |   +1 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)$
 » 2 weeks ago, # |   +1 anyone pls tell me what was the intuition and how you've solved div2 2 (b harder version )
•  » » 2 weeks ago, # ^ |   0 Dynamic programming for both B1 and B2.
•  » » » 2 weeks ago, # ^ |   0 can you tell me what was your intuition in dp solution of B:/
 » 2 weeks ago, # |   0 Did anyone tried solving B2 with Binary search I tried but it failed on pretest2
 » 2 weeks ago, # |   0 Permutation Forces
 » 2 weeks ago, # |   +15 Div 2 is too unbalanced
 » 2 weeks ago, # |   +62 Wow, I made the last "pretests passed" submission in the whole Div.1 round, at 01:59:46.My heart was beating soooo fast!
 » 2 weeks ago, # |   +2 For me Div2 B2 >>> Div2 E
 » 2 weeks ago, # |   0 So,When will the editorial/tutorial be posted?A greenhand in codeforces....
 » 2 weeks ago, # |   +263 F = this + this + this.
 » 2 weeks ago, # |   +3 C was easier than B2 :/
 » 2 weeks ago, # |   +6 Would love to know the solution of B2.
 » 2 weeks ago, # |   +15 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.
•  » » 2 weeks ago, # ^ |   0 The solution in the editorial is indeed clean. During the contest I missed an observation and used a more complicated solution.
 » 2 weeks ago, # | ← Rev. 3 →   +7 Ordered set giving TLE in div2 C sed life :-(
 » 2 weeks ago, # |   0 desperately waiting for the solution to B2
•  » » 2 weeks ago, # ^ |   0 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.
•  » » » 2 weeks ago, # ^ |   0 I couldn't solve b2, just waiting for an editorial solution
•  » » 2 weeks ago, # ^ |   0 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)$.
•  » » 2 weeks ago, # ^ | ← Rev. 6 →   +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
 » 2 weeks ago, # |   0 My submission to pCThe time complexity should be O(n^2),but I got TLE. Can somebody help me?
•  » » 2 weeks ago, # ^ |   +3 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.
•  » » » 2 weeks ago, # ^ |   0 I have same feeling with you;) Thanks for your helping~
•  » » » 2 weeks ago, # ^ | ← Rev. 4 →   +1 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.
•  » » » » 2 weeks ago, # ^ |   0 Ok,I get it now.Thanks!
 » 2 weeks ago, # |   +19 The funniest thing is how div1D was named "and permutations". Because the rest isn't :^)
 » 2 weeks ago, # |   +1 1D is ezer than 1B and 1C !!!
 » 2 weeks ago, # |   +3 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
•  » » 2 weeks ago, # ^ |   +3 It wasn't a Fenwick :kappa: ...
•  » » » 2 weeks ago, # ^ |   +3 Yet I solved it with Fenwick
•  » » » 2 weeks ago, # ^ |   0 It is quite obvious that Fenwick in D2C is not an intended solutionYet it solves the problem
 » 2 weeks ago, # | ← Rev. 6 →   +16 I think div2 C is easier than div2 B2. div2 B2 caused me to have no time to solve div2 D......
•  » » 2 weeks ago, # ^ |   0 It's obvious that it's intended, because B1+B2's score is 1750 while C's score is only 1250.
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   0 Well, B1 is very simpleThe actual time consumer is B2
•  » » » » 2 weeks ago, # ^ |   0 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.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 2 →   +1 Well, I get your point, yet not like we always prove solutions during the contest
•  » » » » 2 weeks ago, # ^ |   +3 How do you solve B1? I spent a long time on it to prove greedy solution correct.
•  » » » » » 2 weeks ago, # ^ |   0 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.
•  » » 2 weeks ago, # ^ |   0 That's why you should read all the problems and take scoring distributions with a grain of salt.
•  » » » 2 weeks ago, # ^ |   +4 But usually the difficulty of the problem increases gradually
•  » » » » 2 weeks ago, # ^ |   +3 Usually but not always...
 » 2 weeks ago, # |   -7 I should have expected that it will be a trash contest from the blog vibes.
•  » » 2 weeks ago, # ^ |   +3 Ah, I see. It is trash only if you under-perform.
•  » » » 2 weeks ago, # ^ |   +3 Do you know my opinion about every other contest?
 » 2 weeks ago, # | ← Rev. 3 →   0 Nevermind, it is because merge sort tree queries runs in O(log^2n) :(
 » 2 weeks ago, # |   +5 I think A is the hardest among first 5 problems in div 1.
•  » » 2 weeks ago, # ^ |   +1 Seriously?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +3 Yet in Div2 it has more solutions than D2B which is not even present in div1B stands for Balance
•  » » 2 weeks ago, # ^ |   0 how you become a legendary grandmaster, in just 8 contests
 » 2 weeks ago, # |   +17 A is similar to 1400D - Zigzags
 » 2 weeks ago, # |   +18 How to write Tokitsukaze and Meeting without much pain? I had seen there several complex loops, and every time I tried to write them, I had gotten confusion.
•  » » 2 weeks ago, # ^ |   +10 You can check my solution, I think it's pretty easy, and the code is short.
 » 2 weeks ago, # |   0 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?
•  » » 2 weeks ago, # ^ |   +1 Using 32-bit instead of 64-bit ints roughly halves the memory requirement, which helps just as much as optimizing by using one array.
 » 2 weeks ago, # | ← Rev. 6 →   +11 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 !
 » 2 weeks ago, # |   0 Is B2 DP?
•  » » 2 weeks ago, # ^ |   0 I saw that one person used dp, but I am pretty sure that is not the intended solution
•  » » 2 weeks ago, # ^ |   0 Yes, it's fairly standard dp once you notice that you only need to apply the operation to 01/10 pairs.
•  » » 2 weeks ago, # ^ |   0 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?
•  » » 2 weeks ago, # ^ |   0 i solved it using DP
 » 2 weeks ago, # | ← Rev. 2 →   +3 B1 and B2 can be solved with DPstates => 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 Code#include using namespace std; #define f first #define s second #define pb push_back #define pob pop_back #define b back #define cout(x) cout << x << endl #define lb long double #define soa(arr, n) sort(arr,arr+n) #define inputVector(v, n) for(ll i = 0; i < n; i++) cin >> v[i] #define sov(v) sort(v.begin(), v.end()) #define rev(v) reverse(v.begin(), v.end()) #define pl pair #define all(a) a.begin(), a.end() #define vpp vector> #define fastIo ios_base::sync_with_stdio(false), cin.tie(0) #define endl '\n' #include #include using namespace __gnu_pbds; #define ordered_set tree, null_type,less>, rb_tree_tag,tree_order_statistics_node_update> #define No cout << "NO\n"; return; #define Yes cout << "Yes\n"; return; typedef long long int ll; ll P = 1e9 + 7; pair dp[200001][2][2][2]; pair findOps(ll i, string &s, ll p0, ll p1, ll last) { if(i == s.length()) { if(p0 &1 || p1 & 1) return {1e8, 1e8}; else return {0, 1}; } if(dp[i][p0][p1][last].first!= -1) return dp[i][p0][p1][last]; pair ans = {1e8, 1e8}; if(p0) { if(s[i] == '0') { ans = min(ans, findOps(i + 1, s, p0 ^ 1, p1, s[i] - '0')); } else { s[i] = '0'; pair minis = findOps(i + 1, s, p0 ^ 1, p1, s[i] - '0'); minis.first += 1; minis.second += i > 0 && s[i] != s[i - 1]; ans = min(ans, minis); s[i] = '1'; } } else if(p1){ if(s[i] == '1') { ans = min(ans, findOps(i + 1, s, p0, p1 ^ 1, s[i] - '0')); } else { s[i] = '1'; pair minis = findOps(i + 1, s, p0, p1 ^ 1, s[i] - '0'); minis.first += 1; minis.second += i > 0 && s[i] != s[i - 1]; ans = min(ans, minis); s[i] = '0'; } } else { // chance of toggling. if(s[i] == '0') { pair minis = findOps(i + 1, s, p0 ^ 1, p1, s[i] - '0'); minis.second += i > 0 && s[i] != s[i - 1]; ans = min(ans, minis); s[i] = '1'; minis = findOps(i + 1, s, p0, p1 ^ 1, s[i] - '0'); minis.first += 1; minis.second += i > 0 && s[i] != s[i - 1]; ans = min(ans, minis); s[i] = '0'; } else { pair minis = findOps(i + 1, s, p0, p1 ^ 1, s[i] - '0'); minis.second += i > 0 && s[i] != s[i - 1]; ans = min(ans, minis); s[i] = '0'; minis = findOps(i + 1, s, p0 ^ 1, p1, s[i] - '0'); minis.first += 1; minis.second += i > 0 && s[i] != s[i - 1]; ans = min(ans, minis); s[i] = '1'; } } return dp[i][p0][p1][last] = ans; } void solve() { ll n; cin >> n; string s; cin >> s; for(ll i = 0; i < n; i ++) { for(ll j = 0; j < 2; j ++) { for(ll k = 0; k < 2; k ++) { for(int l = 0; l < 2; l ++) dp[i][j][k][l] = {-1, -1}; } } } pair minis = findOps(0, s, 0, 0, 0); cout << minis.first << " " << minis.second << endl; } int main() { ll t=1,i=1, n; fastIo; cin >> t; while(t--) { // cout << "Case #"<
 » 2 weeks ago, # |   +56 Fixed my bug on E 10 minutes after the contest, by just changing two chars. TaT
 » 2 weeks ago, # |   +116 Seriously, I've never seen a problem more stupid than Div.1 E.
 » 2 weeks ago, # |   +2 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?
•  » » 2 weeks ago, # ^ |   -20 I told you but you were busy with your agenda
•  » » » 2 weeks ago, # ^ |   +6 Hi Naman, At how much cost did you sell your ID?
•  » » » » 2 weeks ago, # ^ |   0 yeh MnC wala Naman Arora hai na?
 » 2 weeks ago, # | ← Rev. 2 →   0 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
 » 2 weeks ago, # |   0 That balance is 10 out of 10 basically, but you've tried)
 » 2 weeks ago, # | ← Rev. 2 →   0 at least this round is better than the last chinese one
 » 2 weeks ago, # |   -21 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.
•  » » 2 weeks ago, # ^ |   0 I guess it's because ordered_set has a higher constant than fenwick tree.
•  » » 2 weeks ago, # ^ |   +5 Huh? Just don't use ordered_set when the TL is tight. The constant for it is way too big.
•  » » 2 weeks ago, # ^ |   0 idk my order set solution passes with half of time limit 156302146
•  » » » 2 weeks ago, # ^ |   -8 Thats because you have used one ordered set I used 2 and it failed.156324323
•  » » » 2 weeks ago, # ^ |   0 can you explain your solution more ? thanks in advance.
•  » » » » 2 weeks ago, # ^ |   0 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
 » 2 weeks ago, # |   0 This round let me feel that I sould give up
•  » » 2 weeks ago, # ^ |   +4 Dude if you were specialist at one point that should let you know that you have at least some level of talent.
•  » » 2 weeks ago, # ^ |   0 Not untrue !
 » 2 weeks ago, # |   0 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 >_>
 » 2 weeks ago, # | ← Rev. 2 →   0 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#
 » 2 weeks ago, # |   0 Waiting for usual YT editorials for last div2 problems :)
 » 2 weeks ago, # |   +3 WTF!!link this problem is the same as problem C I replaced every < by == and got accepted
•  » » 2 weeks ago, # ^ |   0 And the question of this link is weaker than the C.....
 » 2 weeks ago, # |   0 The pretests are so powerful that the issue occurred Runtime error on test 4 LOL
 » 2 weeks ago, # |   0 Problem C O(N*N*log) AC : 156339292how is can fit when N up to 5000?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   +5 Codeforces servers are very fast, they can do ~1e9 operations per sec. so your solution fits nicely
•  » » » 2 weeks ago, # ^ |   0 I think this is also the same complexity O(N*N*log)? 156359874
•  » » » » 2 weeks ago, # ^ | ← Rev. 3 →   0 yes, but the constant factor is bigger
 » 2 weeks ago, # |   -42 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
 » 2 weeks ago, # |   -42 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 :/
 » 2 weeks ago, # |   0 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.
•  » » 2 weeks ago, # ^ |   0 I agree with you
 » 2 weeks ago, # |   -27 Guys who created this round, what do you think about Winnie the Pooh?
 » 2 weeks ago, # |   +3 As a Chinese,exicted for Chinese statement!
 » 2 weeks ago, # |   +34 It seems that I am the only person who FST on Div.1 B. :<
 » 2 weeks ago, # | ← Rev. 2 →   +3 Achievement unlocked: "Perfectly Balanced": obtain 0 delta
 » 2 weeks ago, # |   0 OMG! The C is tooooooo annoying!!!!,QAQ.....TLE or MLE(I know the reason is that Im tooooo weak)
 » 2 weeks ago, # |   0 A good contest!
 » 6 days ago, # |   0 Thank you for the Chinese tutorial.