учитывая что это Div2, думаю проблем вообще нет.

Если ты не будешь знаком с задачами, то, конечно, можно участвовать в этом раунде.

Да, в таком случае участвовать можно.

You can know more here: https://mirror.codeforces.com/blog/entry/49569

Not Original, Copied it from some previous post because it was hilarious. xD

YES，very nice

I think they can't move it because it's like online mirror of the on-site contest.

How old are you?

Maybe you finished it just now...

I'm just like you.

https://mirror.codeforces.com/spectator/ranklist/78d1f77c847042d2441c139c64a57c15

waiting for it :)

School on Sunday?

I hope 2-sat with segtree won't pass (I tried to eliminate non-linear solutions).

The easiest linear solution is to take care of $$$f$$$ by introducing variables of the form $$$f \ge i$$$, that way every station adds only $$$2$$$ clauses (with $$$f \ge l_i$$$ and with $$$f \ge r_i + 1$$$).

I think it's googlebale, if you google it you might find a solution, Am not sure thought :(

Compute for each pair of color i,j the cost of putting color i before j and the cost of putting j before i (number of inversions between the two colors), and add the minimum to the result.

DP on bitmask, like travelling salesman problem, except this time the distance is number of inversions.

if ? only on one side: Bicarp always can add (9-a) value on the same side where "a"=previous step from Monocarp

If ? on both side: Bicarp always can add the same value on 2nd side like Monocarp on previous step on 1st side

I made some observations, but I may be incorrect.

(1) If you remove a question mark from each half, the winner does not change. I could not fully prove this, but a partial proof is if Bicarp was the winner before, then adding a ? to each side means that any Monocarp's move can be countered by Bicarp by doing the exact same move on the other side. (2) So we can keep removing question marks until only one half has a question mark. Now if there are odd number then Monocarp has the last move and can always win. (3) Define difference as subtraction of question_mark half from other_half. If even then if the difference/9 = question_marks/2 then Bicarp wins, else monocarp wins (also difference%9 must be 0 and difference must be positive). This is because any move Monocarp makes, Bicarp can make a move so that the sum of their moves goes up to 9.

Find (b,a) pairs, (such that first string has 'b' in that position and second string has 'a'), and use one swap to fix. Find (a,b) pairs and use one swap to fix. Then find the remainder (b,a/a,b) pairs if there exist, and use two swaps to fix.

Look for all pairs (i, j) of discrepancies such as s[i] != t[i] and s[j] != t[j] and s[i] != t[j], and swap them. If there is no such a pair now, swap s[i] with t[i]. Continue until all is fixed.

Use dynamic programming — calculate the number of negative and positive substrings ended at each position. The accumulated value will be the answer.

Define dp(i,+) as the number of arrays that end on the i'th array that are positive, and dp(i, -) as the number of arrays that end on the i'th array that are negative.

Then the dp states are updated as follows. if the current number is positive then dp(i,+) += dp(i-1,+) + 1 dp(i,-) += dp(i-1, -)

if the current number is negative dp(i,-) += dp(i-1,+) + 1 dp(i,+) += dp(i-1,-)

(the + 1 is because the number itself adds to the answer if it is positive or negative)

Final answer is sum of all dp(i,-) and dp(i,+)

60616510

my submission first go through whole array and count start from idx 0 and end at 0 to n — 1;

and count if segment is negative or positive;

neg, pos;

set positives = 0, negatives = 0;

and go through idx 0 to n -1 again.

if current array element is positive 

    pos--;

else if current element is negative

    neg--;

    swap(pos, neg)

positives += pos;

negatives += neg;

time complexity is O(n)

Exactly the same thing, half hour more and I would solve it also. Today with minor fixes my solution has passed.

-rating but +knowledge

I solved D with greedy:

Try to maximize left half, minimize left half, maximize right half, or minimize right half for Monocarp, then if at least in one case Bicarp can't make it equal, Monocarp win, else Bicarp.

Split the string into two part, calc the sum of left and right parts (denoted as s1 and s2), and how many unknown digit for each sides(denoted as c1 and c2).

Then this problem become: there is a number s=s1-s2, you can do c1 times plus operation and c2 times subtract operation, if the result is 0, then the second guy win, else the first one.

Now it's still difficult, so let's transform subtract operations into plus operations. Because of subtract x equal to plus y-9 while y = 9-x.So now the problem is about a number s'=s-9*c2, you can do c1 + c2 times plus operation.

It's easy to prove only when res = s' + 9 * (c1 + c2) / 2 equal to 0, the second guy will win.If res < 0, then first guy can always plus 0 in each turn, else plus 9 in each turn.

I don't know whether the idea is right because I haven't submited it.

His code has been running on pretest 8 for 2 hours lol

Probably BledDest and his team are fans of trash rounds from '...' with lots of hacks and being in love with bad pretests. OR THEY THOUGHT THAT IT WOULD BE EDUCATIONAL ROUND LMAO

Many solutions on D failed because several contestants did integer division by 9. That works if Bicarp wins, but may give a false alarm if Monocarp wins.

Everyone of us has gone through this phase my friend :)

:(

Frequently

never mind.