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.

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.

My solution: (not the optimal solution)

For the minimum: Consider C is the number of players and k is the amount of cards a player can get before being banned. Every player can receive k-1 cards and still be in the game so you can give every player k-1 cards and since every player is one card away from being banned the number of cards left is the minimum number of players. min = min_team1+min_team2; (if minimum is negative result = 0 !!)

For the maximum: you can pick the team with the smallest k and while players > 0 and n-k >= 0 you can pick a player then n = n-k; then same for the second team. you can do this with math equations but I find Greedy easier to understand

A more naive solution: Just use priority queue to simulate the process.
My solution can be found here.

Well, one observation is that any operation must increase the number of matching indices (s[i] == t[i]) by at least 1. So we might iterate over all pairs of indices and check whether we can make an operation such that for one of those indices, say j after the operation, s[j] == t[j]. If we find such a pair, we remove j and continue. Otherwise, we stop and if the string is non-empty, then there is no solution.

That works in time O(alphabet_size ^ 6), which seems to be well enough.

pref[i] *= arr[i] / abs(arr[i])

We dont need array a we just need sign of a and if you do just pref[i] *= a[i] then after 3 iterasions with 10^9 it becomes 10^27 which doesn fit anywhere

How were you generating testcases?

I found this is the smallest case that should prevent people from calculating cost the wrong way and it's only 7 digits long.

I also didn't understand your code at first and tried to come up with countercases, but I couldn't and in the process, I came to the conclusion that the algorithm was correct.

So here's a small proof:

First notice that pref[i] % 2 == 0 iff the product of numbers up to i is positive.

When calculating the number of positive subsegments, you have 3 terms:

• The number of ways to choose two indices, i and j, such that the products of numbers up to i (inclusive) and j (inclusive) are both positive / both negative. That means that, in both cases, there is an even number of negative numbers between i + 1 and j (we use a similar property when constructing prefix sums). Thus, the subsegment (i, j] is suitable.

• The number of indices i such that the product of numbers up to i (inclusive) is positive. This means that the subsegment [1, i] is suitable (1-based indexing).

So we proved that all those subsegments are positive. It remains to prove that we haven't missed any other positive subsegments.

Let's make the proof by contradiction. Assume there is a subsegment (i, j] such that the products of numbers up to i and j (both inclusive) have different signs. That means that there is an odd number of negative numbers in the interval [i, j] (again, remember prefix sums), and the subsegment is negative.

The number of negative subsegments is simply this amount subtracted from the total number of subsegments.

Overall, B was a bit tricky, even though it's obvious that the problem is classic. It took me the longest to solve from [A, D], and I have only a vague understanding of why my code works.

Hope that helped!

maybe sometimes if M reducing the difference is a better choose. like this example:

4 ??01

if M choose write a number>=2 on the left sum(right)-sum(lift) will be negative，and M will win. but you code will cout B.

It was already out when you asked about it: editorial

MikeMirzayanov