tokitsukaze's blog

By tokitsukaze, 2 weeks ago, In English

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:

  1. maroonrk

  2. tourist

  3. eecs

  4. ainta

  5. duality

Div.2:

  1. Kakki_Haruka

  2. WA_On_Pretest2_Forces

  3. ouql

  4. KroosTheKeenGlint

  5. jialiang250

 
 
 
 
  • Vote: I like it
  • +766
  • Vote: I do not like it

»
2 weeks ago, # |
Rev. 4   Vote: I like it +25 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    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, # |
  Vote: I like it +2 Vote: I do not like it

sjfyyds!

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

sjfnb!!!

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

sjfnb!

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Chinese statement!Wow

»
2 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

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, # ^ |
      Vote: I like it +21 Vote: I do not like it

    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, # |
  Vote: I like it +3 Vote: I do not like it

SJF YYDS!!!

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

love em catss <3

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

〜( ̄▽ ̄〜)

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

I see meow, I upvote.

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I hope this round came easier than the last one

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    Trauma
»
2 weeks ago, # |
Rev. 4   Vote: I like it -7 Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

BTW the meowsmeowsmeows are really cute!

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

≧ω≦ it is a nice cat .. I wish the round be good like the latest one ..

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'll have a cat sooner or later! QAQ

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish you all a great rating gain.

»
2 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

sjf nb

»
2 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

meow!

»
2 weeks ago, # |
  Vote: I like it +39 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

sjfnb!!!

»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

sjfyyds

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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, # |
  Vote: I like it +5 Vote: I do not like it

sjfnb!

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

I hope that i will be a pupil

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

Good luck for everyone!!!

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

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thank you codeforces!

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

meow! I upvote

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it -35 Vote: I do not like it

So when are you eating your cats?

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

my first div1 contest :D

»
2 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

sjf nb!!!

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What about the wrong submission?

»
2 weeks ago, # |
  Vote: I like it +55 Vote: I do not like it

Permutationforces again

»
2 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      $$$|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, # |
  Vote: I like it 0 Vote: I do not like it

server is tooo much fast guys :D

»
2 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

The memory in problem C is very annoying

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Dang, that problem B though :P

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

»
2 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Ugh! Headache from that B2 I'm done

»
2 weeks ago, # |
  Vote: I like it -46 Vote: I do not like it

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

Context

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it +30 Vote: I do not like it

    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, # ^ |
        Vote: I like it -16 Vote: I do not like it

      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, # |
  Vote: I like it +9 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Finally solved a FFT problem during contest. POG

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    what ?????

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it -12 Vote: I do not like it
        you can do it in O(n)???
  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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   Vote: I like it +13 Vote: I do not like 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

    1
    1000000 0
    -1 -1 ...
    

    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

»
2 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Rubbish round

»
2 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

C was easier than B2 :/

»
2 weeks ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Hints for Div2E/Div1C

Solve 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, # |
  Vote: I like it 0 Vote: I do not like it

What was B2? Can someone provide me some testcases?

»
2 weeks ago, # |
  Vote: I like it +51 Vote: I do not like it

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, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    It can be solved without DP.

    Solution
»
2 weeks ago, # |
Rev. 2   Vote: I like it -64 Vote: I do not like it

...(nothing)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I use seg tree too, TLE too. qwq

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dynamic programming for both B1 and B2.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Permutation Forces

»
2 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Div 2 is too unbalanced

»
2 weeks ago, # |
  Vote: I like it +62 Vote: I do not like it

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, # |
  Vote: I like it +2 Vote: I do not like it

For me Div2 B2 >>> Div2 E

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +263 Vote: I do not like it

F = this + this + this.

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

C was easier than B2 :/

»
2 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Would love to know the solution of B2.

»
2 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it +7 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

desperately waiting for the solution to B2

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it +1 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

My submission to pC

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
      Rev. 4   Vote: I like it +1 Vote: I do not like it

      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, # |
  Vote: I like it +19 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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, # |
Rev. 6   Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      Well, B1 is very simple

      The actual time consumer is B2

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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   Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      But usually the difficulty of the problem increases gradually

»
2 weeks ago, # |
  Vote: I like it -7 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

A is similar to 1400D - Zigzags

»
2 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +1 Vote: I do not like 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.

»
2 weeks ago, # |
Rev. 6   Vote: I like it +11 Vote: I do not like it

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

Div 2 B1 solution
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is B2 DP?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i solved it using DP

»
2 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

Code
»
2 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +116 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

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, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

at least this round is better than the last chinese one

»
2 weeks ago, # |
  Vote: I like it -21 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

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

      156324323

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain your solution more ? thanks in advance.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

This round let me feel that I sould give up

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not untrue !

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Waiting for usual YT editorials for last div2 problems :)

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

WTF!!

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

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

how is can fit when N up to 5000?

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

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, # |
  Vote: I like it -42 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it -27 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

As a Chinese,exicted for Chinese statement!

»
2 weeks ago, # |
  Vote: I like it +34 Vote: I do not like it

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

»
2 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Achievement unlocked: "Perfectly Balanced": obtain 0 delta

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

A good contest!

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the Chinese tutorial.