do you know why you got so many downvotes?

Please, Update Score distribution.

Hope to see you GM post this round, Best of luck :P

Well lots of bit manipulation is already going on in comment section.. damn they are already practicing for the problem.. BitForces

bad round, no pikachu theme...

Post Script.

Yes, exactly.

I thought it is always you :)

gepardo

Umm... Not you this time?

NOTED

I wonder if I get negative contribution, will it balance out and give me positive delta

Thank you for teaching me English! You have taught me how to write the verb taught!

Actually, it is not mine, just google it.

Исправил, спасибо.

Well, you are kind of correct: tasks D1 and D2 require a correct solution.

Why not?Every A of CF is easy!Sometimes it looks harder but has an easy solution.Like last round's A was pretty easy.But most of us thought that bruteforce wouldnt work :(

Editorials will be provided only on English and Russian, I think :)

Right after the system testing I guess.

I didn't submit anything for the contest, but I think you might be able to keep the indices of positive/negative in a set, get the lower and upper bound for each query in logn, and just greedily pick from there.

Much easier :)

From D1 you should already know, that answer is always $$$1$$$ for odd segments and $$$2$$$ for even, if sum inside is not equal $$$0$$$. So, firstly we will reduce problem to odd segments by taking first element of even segment to answer, for example. Then, you need to find such element, that sums before it and after in segment the same. Suppose we have query $$$[l, r]$$$ and we want to delete element $$$x$$$. In terms of prefix sums we will get $$$pref[r] - pref[x] = pref[x- 1] - pref[l - 1]$$$, that equals to $$$pref[x - 1] + pref[x] = pref[l - 1] + pref[r]$$$. And all you need — is to count $$$pref[x] + pref[x - 1]$$$ for all elements and add to some associative container such indexes, let's call it $$$C$$$. The answer- lower_bound in $$$C[pref[l - 1] + pref[r]]$$$ by $$$l$$$. 127111849

fr

Broo exactly!

I can think of O(n^2 logn). But I don't think that's meant to pass.

Wait for editorial :)

I used suffix array with an O(N^2) dp, got the pattern when writing out the suffix array of the first sample test and try to get the result from that.

I tried an O(n^2) dp approach. solution

I utilised the fact that the answer for the reverse of the expansion will be the longest decreasing subsequence.

By reversing the string, we can enumerate all the substrings that end at any particular character such that they are in the same order as in the original expansion.

Now let dp[i] be the LDS such that we necessarily took the substring ending with char s[i].

So for calculating dp[i], the answer will be at least i+1 as we can take all the substrings ending at s[i]. Now we can iterate and check if we can add all these substrings to any previous answer only if those answers are greater than all substrings ending at s[i] (as it's always best to include these substrings).

SO to check two substring families ending at s[j] and s[i] (j < i), I pre-calculated g[j][i] which tells me after which length of a substring starting from j towards 0, it becomes greater than the substring family s[i] and use this value to subtract the initial substrings starting at j which are smaller than substring family s[i].

Now final answer is max of all dp[i]

PS:- sorry for my bad explanation.

Greedy .... lets say you have a string 1101 which is x (let's say) then to get a number that dividides it is simply 11010 which is 2 * x

So basically all we need is a 0 to find a multiple .... let place = index of last 0 (from 1 to n)

Case 1 — 0 exist in 1 to n/2 then just print from that place where 0 is to n and place+1 to n

Case 2- 0 exist after n/2 then print 1 to place , 1 to place -1

case 3- 0 is at n/2 ... print from n/2 to n and n/2+1 to n

Case 4 — all numbers are 1 ... then print 1 to n/2 and n/2 to n or 1 to n/2 , 2 to n/2+1

Yes

Problem name of this problem is a big hint to reveal the same.

NOTED

actually if alternative sum is 0 -> ok,

if it's odd then of course there exists 1 rod which divides interval into 2 intervals with equal alternative sum(total sum / 2) so this will be the rod to be removed(and after it second sum will become: -sum and hence 0 in total).

if sum is even -> just ignore first rod in current interval and sum will become odd, now do the same as above.(p.s. here it can be proved that in 1 deletions it's impossible to make things good(of course even in 0 deletions) the reason is simple: making alternative sum in 1 deletions simply means that there should be 1 rod without which the remaining sum should be split into 2 equal alternative sums which is impossible(odd isn't divisible by 2))

These two observations must be enough to get to a solution.

Observation 1: If rod at Index i is removed,the subarray [i+1,N] gets multiplied by -1.

Observation 2: If Sum is odd (of the form 2*a+1), we can find the index at which sum[ l ,i-1 ] == a && sum [ i+1, r ] == a and remove the rod at index i.

Observe that once you remove a character the net value of the sequence following it till the end gets multiplied by -1. Now coming to the question There are 2 cases, either the sequence length is odd or it is even

• Case odd: When the length of the sequence is odd then the total sign-variable sum must be odd. Now every odd number x can be written as odd = even + [+/-] + even. Now if you strategically remove the [+/-] then the net value becomes even — even = 0. Hence the answer for odd length is always 1.

• Case even: When the length of the sequence is even then the total sign-variable sum must be even. If the total sign-variable sum is already equal to 0, then no rods need to be removed hence answer is 0. Otherwise, we can write even = [+/-] + odd. Now to you have to remove one rod to get the net value odd and we saw that every odd value can be made 0 by Furthur removing one rod. Hence the net answer for this case becomes 2.

Yes.

i got this approach when i was done with coding by taking so many cases.

I've prooved all the solutions :)

Just search for one zero For example you have 10111 then ans is 0111 111 k=1 and if the zero is after half the string like 11101 then ans is 1110 111 k=2

Finding out the cases is problem solving too, no?

Same for me. I print the wrong length of the string. I always print 1, even when I have to print 2. The code passed pretets but failed systests. In fact, my solution should fail sample test, so it should have failed pretests as well. There's something wrong here.

I don't know why B asks for outputing the length, it makes no sense, just annoying.

Will be rated.

I'm also in the same situation, let's see how rating changes after the contest.

I can tell from your picture that you are Chinese.

It is to make sure you can print f(t)=f(w)=0.

Yes, such case is possible, and $$$k$$$ can be any integer in this case.

Deleted

Yes I guess.

You are doing way too many calculations you should have checked the string in n^2 complexity considering all pairs of two digit number after the one digit number

Note that if we take some subarray, we can take all the suffix which has the prefix as this subarray. compute the prefix array for every suffix using the z algorithm, Then we do normal LIS dp. The comparison will be, let x = z[j][i] for all j < i. Then if s[i + x] > s[j+x], dp[i] = dp[j] + n-i-x+1. Take the max of all dp. Submission

Unfortunately I din have time to implement this during contest even though I copied the code for z algorithm from geeksforgeeks.