he hasn't participated to rated contests for 6 months.

He hasn't participated in the last 6 months, so he has moved to the inactive section of codeforces.

You can see his profile.

Div 4 is not happening any time soon...

West coast be like: Aww I have to wake up early for CF contests

East coast: sleeps in until 10:25 and doesn't miss the contest

You sleep while we work It's not a statement, it's an order.

mike mirzayanov is from russia) so russians sleep at this time)

https://bfy.tw/Ormx

In normal Div 2 ,weightage is different for all question, but in Educational contest weightage is same for all questions,and Ranking is based on penalty and no. of questions.

smh people changing comment content to avoid getting more downvotes

No No No!!! another bad nightmare.

Do you mean specialist?

• Every question has equal weight-age
• 12 hour open hacking phase
• Some problems are standard/classical

for destroying participants by bad ordering of problems

good luck

Tester think all problems are easy :(

B sucks

Luckly I jumped straight to C and got it early. Still didn't solve B tho...

Yes, E is exact copy of:

448 Problem C

I have idea just now. I could have done this. That irritating B costed me. Disgusting round. Don't order problems in terms of difficulty

What exactly is misleading in B and C statement?

448C - Painting Fence

This is an exact replica of that problem. How lucky (and hardworking) I am to have solved it!

dp[pos][k] where pos is the prefix we are at and k is the number of active 2nd type queries and gives minimum answer to make all elements till pos equal to 0

Iterate for $$$j$$$ and $$$k$$$, Now you need a index i such that $$$a_i = a_k$$$ and $$$i < j$$$, similarly, you need index $$$l$$$ such that $$$a_j = a_l$$$ and $$$k < l$$$, this suggests us to store two things.
$$$1$$$. $$$pref[i][j]$$$ be the number of times $$$j$$$ appeared from $$$1$$$ to $$$i$$$
$$$2$$$. $$$suff[i][j]$$$ be the number of times $$$j$$$ appeared from $$$i$$$ to $$$n$$$
Now, rest is quite easy.

There are only at max $$$n$$$ distinct numbers, so lets consider the case where each of them are used as $$$j$$$ and $$$l$$$, lets call this number the $$$divider$$$. So for each $$$divider$$$, we iterate left to right across the array, lets say the current number is $$$cur$$$. There are two cases:

1. $$$cur$$$ $$$\ne$$$ $$$divider$$$ — Then we want to add the number of pairs for which this position is $$$k$$$ and some previous position of $$$cur$$$ is $$$i$$$, lets say it is $$$cnt_{cur}$$$. We'll add this to the answer and also store $$$cur$$$ in a vector with contains all non-$$$divider$$$ numbers visited (if its visited multiple times its stored multiple times). I'll explain how to calculate $$$cnt_{cur}$$$ in the other case.

2. $$$cur$$$ $$$=$$$ $$$divider$$$ — Then we want to add all possible values which act as $$$i$$$ to their respective counts. Clearly each number in the vector we stored can act as $$$i$$$ if this position acts as $$$j$$$, so we just add 1 to $$$cnt_{x}$$$ for each $$$x$$$ in the vector.

Also, we have to consider the case where all 4 numbers are the $$$divider$$$, but this is simply $$$cnt_{divider} \choose 4 $$$.

Now since we're iterating over $$$n$$$ distinct numbers and iterating over the whole array in $$$O(n)$$$ each time, and operation 2 is clearly $$$O(n)$$$, it may appear as if the total complexity is $$$O(n^ 3)$$$. However we can observe that $$$cur$$$ $$$=$$$ $$$divider$$$ can only occur $$$n$$$ times over all iterations as each position has only 1 value. So operation 1 which takes $$$O(1)$$$ time is run $$$O(n ^ 2)$$$ times and operation 2 which has complexity $$$O(n)$$$ is run $$$O(n)$$$ times, so overall $$$O(n ^ 2)$$$ which easily passes.

My submission — 90967360

https://mirror.codeforces.com/contest/1400/submission/90950605

I iterated for i and k and maintain some arrays which mean:

lft[x]: how many x appears in the range [i+1,k-1]

rht[x]: how many x appears in the range [k+1,n]

cnt[x]: how many pairs of (x,x) with the first x in [i+1,k-1] and the second x in [k+1,n]

Apparently, (cnt[x] = lft[x] * rht[x] ) always hold but we can't iterate for x (which cause TLE). But note that with the same i, we move k from k to k+1 will cause only the change of cnt[a[k]] and cnt [a[k+1]], so cnt[] can be maintained with O(1) and the solution is O(n^2)

The solution is greedy. First, if s>w swap them and the number of sords with the number of axes. Make a for from 0 to x axes that you take where x is the maximum available given, check if it's possible to take that many, then add as much sords as possible, then add as much axes as possible to your friend bag then add as much sords as possible to your friends bag. That's it!

Link to my code: 90946553

After D

Why? It is just a basic brute force.

:(

The problem may seem standard but I am curious about how you found that EXACT problem that E was copied from

I had also found this, but wasn't sure if they are same. Checkout the last condition in the link you shared. "Note that you are allowed to paint the same area of the fence multiple times."

Is it the same, as I think we can't the operation in today's problem if not sufficient Ai for which we intend to do operation?

Maybe I'm missing some observation. Please clarify toxic_hack

I Accepted 448C

but I don't know E is the same as 448C,I'm fool ,lol.

congratulation

Inclusion-exclusion, answer is C(cnt[i], i) if m = 0 where cnt[i] is number of people j with l[j] <= i <= r[j]. If m > 0 then for each mask you need to calculate intersection of segments, and subtract\add C(cnt[i] — badCnt, i — badCnt) for L <= i <= R (badCnt is number of unique people in mask, [L, R] is intersection of segments). Since badCnt <= 40, you can precalculate it with prefix sums.

Inclusion-exclusion on the subset of taken pairs of mercenaries that hate each other.

Suppose that we fix a subset of pairs we take, this subset denotes the subset of mercenaries we have to take (up to $$$40$$$ of them). For these mercenaries, intersect the segments $$$[l_i, r_i]$$$ to get the range where the size of the subset will be (let it be $$$[L, R]$$$).

Suppose there are $$$k$$$ mercenaries we have to take. Then we have to compute $$$\sum_{i=L}^{R} C(c_i - k, i - k)$$$, where $$$C(x, y)$$$ is the binomial coefficient, and $$$c_i$$$ is the number of mercenaries that are allowed in a subset of size $$$i$$$ ($$$i \in [l_x, r_x]$$$ for those mercenaries). The key observation is that $$$0 \le k \le 40$$$, so we can build $$$41$$$ arrays of those binomial coefficients and use prefix sums to quickly get the sum on range.

I believe the crux was that max complete combos never exceeded 2^20

Iterate over number of swords bought by one of them, and then select greedily. https://mirror.codeforces.com/contest/1400/submission/90977190

No,It can be done without this theorem.

You can draw a coordinate system in the form of linear programming. According to the slope, the answer must be one of the two endpoints.

plz help

I couldn't understand that long code but here is how i upsolved it: First we only know that we will get a 0 only if there is no '1' on i+x and i-x indices. (Update both indices to '0') then, for each '1' in s, we check if at least one char either i+x or i-x is 1. if both are '0', print -1. else print 1's in all un-updated indices and updated will be '0' from the first step.

Yes and it's actually pretty easy.... Almost solved in during contest and feeling regretful now...

Great decision. I wasted an hour on B. Couldn't even read D which I was able to solve in 10 min after the contest.

I failed just because of starting the loop from 1 instead of 0 ... feel me lol

shouldn't have wasted that much time on B, C was waaayyy easiear and doable than B.

The total length of $$$x$$$-prime strings is not too big (somewhere around $$$5000$$$), so we have to generate them, build an Aho-Corasick automaton and implement the following dynamic programming: $$$dp[x][y]$$$ is the minimum number of characters from the first $$$x$$$ we have to remove, so the resulting state in the automaton is $$$y$$$ (make sure to mark the bad states of the automaton, that is, the states where some prime string ends).

cases of for having '1' is ambigous, but have a '0' is obvious. why are you considering '1's first?

check this test case: 11110 1

same pinch

no there could be multiple answers. so finding one possible and then checking if it matches input is obviously wrong.

Can confirm, just submitted.

I had solved 448C while practicing about a year ago. Couldn't solve it today. Now this is sure that I won't forget this problem/solution ever :)

i guess that you access string w out of bound?

I think you should check conditions i+x<s.size() and i-x>=0 separately.

In your code, when i=0, i-x<0 but i+x<s.size() -> you access character at a negative (i-x) position in string s.