When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

tokitsukaze's blog

By tokitsukaze, 22 months 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 May/08/2022 17:35 (Moscow time).

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

  2. WA_On_Pretest2_Forces

  3. ouql

  4. KroosTheKeenGlint

  5. jialiang250

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

| Write comment?
»
22 months 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<).

  • »
    »
    22 months 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”.

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

sjfyyds!

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

sjfnb!!!

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

sjfnb!

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Chinese statement!Wow

»
22 months 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.

  • »
    »
    22 months 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(

»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

SJF YYDS!!!

»
22 months 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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
22 months 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的你 滴滴清纯的蒸馏水"?

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

〜( ̄▽ ̄〜)

  • »
    »
    22 months 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 =^•ω•^=

»
22 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I see meow, I upvote.

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I hope this round came easier than the last one

»
22 months 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 ..

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'll have a cat sooner or later! QAQ

»
22 months 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

»
22 months ago, # |
  Vote: I like it +9 Vote: I do not like it

sjf nb

»
22 months ago, # |
  Vote: I like it +20 Vote: I do not like it

meow!

»
22 months 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

»
22 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

sjfnb!!!

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

»
22 months 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 ( ಠ◡ಠ )?

  • »
    »
    22 months 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.

»
22 months ago, # |
  Vote: I like it +5 Vote: I do not like it

sjfnb!

»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I hope that i will be a pupil

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

Good luck for everyone!!!

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

»
22 months 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

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

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

»
22 months ago, # |
  Vote: I like it -35 Vote: I do not like it

So when are you eating your cats?

»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

my first div1 contest :D

»
22 months 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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

sjf nb!!!

»
22 months 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.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
22 months ago, # |
  Vote: I like it +55 Vote: I do not like it

Permutationforces again

»
22 months 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.

  • »
    »
    22 months 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?

    • »
      »
      »
      22 months 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$$$.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

server is tooo much fast guys :D

»
22 months ago, # |
  Vote: I like it +13 Vote: I do not like it

The memory in problem C is very annoying

  • »
    »
    22 months 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 !

  • »
    »
    22 months 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.

»
22 months 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)?

»
22 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Ugh! Headache from that B2 I'm done

»
22 months 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

  • »
    »
    22 months 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.

»
22 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

»
22 months 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

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

    what ?????

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

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

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it -12 Vote: I do not like it
        you can do it in O(n)???
  • »
    »
    22 months 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.

  • »
    »
    22 months 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.

  • »
    »
    22 months 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 Savior-of-Cross 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

»
22 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Rubbish round

»
22 months ago, # |
  Vote: I like it +14 Vote: I do not like it

C was easier than B2 :/

»
22 months 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.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What was B2? Can someone provide me some testcases?

»
22 months 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...

  • »
    »
    22 months 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.

    • »
      »
      »
      22 months 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" ?

  • »
    »
    22 months 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

»
22 months 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?

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

    It can be solved without DP.

    Solution
»
22 months ago, # |
Rev. 3   Vote: I like it -64 Vote: I do not like it

.

»
22 months 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.

  • »
    »
    22 months 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.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I use seg tree too, TLE too. qwq

      • »
        »
        »
        »
        22 months 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.

  • »
    »
    22 months 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

  • »
    »
    22 months 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.

  • »
    »
    22 months 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)$$$

»
22 months 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 )

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Permutation Forces

»
22 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Div 2 is too unbalanced

»
22 months 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!

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

For me Div2 B2 >>> Div2 E

»
22 months ago, # |
  Vote: I like it +263 Vote: I do not like it

F = this + this + this.

»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

C was easier than B2 :/

»
22 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Would love to know the solution of B2.

»
22 months 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.

  • »
    »
    22 months 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.

»
22 months ago, # |
Rev. 3   Vote: I like it +7 Vote: I do not like it

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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

desperately waiting for the solution to B2

  • »
    »
    22 months 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.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    22 months 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)$$$.

  • »
    »
    22 months 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

»
22 months 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?

  • »
    »
    22 months 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.

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      22 months 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.

»
22 months 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 :^)

»
22 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
22 months 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

»
22 months 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......

  • »
    »
    22 months 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.

    • »
      »
      »
      22 months 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

      • »
        »
        »
        »
        22 months 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.

        • »
          »
          »
          »
          »
          22 months 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

      • »
        »
        »
        »
        22 months 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.

  • »
    »
    22 months 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.

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

      But usually the difficulty of the problem increases gradually

»
22 months 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.

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

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

»
22 months 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.

»
22 months ago, # |
  Vote: I like it +17 Vote: I do not like it

A is similar to 1400D - Zigzags

»
22 months 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.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You can check my solution, I think it's pretty easy, and the code is short.

»
22 months 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?

  • »
    »
    22 months 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.

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

Is B2 DP?

  • »
    »
    22 months 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.

  • »
    »
    22 months 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?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i solved it using DP

»
22 months 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
»
22 months 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

»
22 months 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.

»
22 months 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?

»
22 months 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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
22 months 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.

  • »
    »
    22 months 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.

  • »
    »
    22 months 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.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      22 months 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

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you explain your solution more ? thanks in advance.

      • »
        »
        »
        »
        22 months 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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This round let me feel that I sould give up

  • »
    »
    22 months 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.

»
22 months 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 >_>

»
22 months 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#

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Waiting for usual YT editorials for last div2 problems :)

»
22 months 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

»
22 months 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

»
22 months 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?

  • »
    »
    22 months 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

»
22 months 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?

»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

As a Chinese,exicted for Chinese statement!

»
22 months 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. :<

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

Achievement unlocked: "Perfectly Balanced": obtain 0 delta

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

A good contest!

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you for the Chinese tutorial.