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”.

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(

Don't mind（＾ω＾）

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

Thank you (ฅ'ω'ฅ)♪

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

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

...on Codechef

znjjnb!!!

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 very similar questions separated because of difference in difficulty levels.

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

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

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

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.

what ?????

I did same :D. I was shocked seeing so many AC's so I thought a bit more later, and realized there was no need of FFT/NTT.

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

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

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

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

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

6 101000

and

4 1011

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

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

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

It can be solved without DP.

    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"; 

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

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

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

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

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

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

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

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.

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

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

more intuition : ------11----00----11 the dashed spaces represents blocks where first element != second element those spaces can be filled by 1 or 0.but the remaining 11,00,11 will not be changed as first element == second element. As dashed spaces can be formed by 0 or 1 the only thing deciding the segment whether there is a 00 infront of 11 or 11 infront of 00.

So the answer is,for every i%2 ==0 check whether s[i+1]== s[i].if its true append the value of s[i]to an array.Now for every array[i] check whether array[i] != array[i+1].if its true ans will be increased by 1 as we have found a new segment

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.

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

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

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

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

Seriously?

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

B stands for Balance

how you become a legendary grandmaster, in just 8 contests

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

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

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

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

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

i solved it using DP

I told you but you were busy with your agenda

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

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

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

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

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