First note that there is always an optimal bracket sequence such that none of its prefixes has a balance larger than 2N (there's a proof sketch somewhere below).

Now make a (2N+1)*(2N+1) matrix. In cell (i, j) write the cost of the optimal n-block that changes the total balance from i to j, such that at no point it goes below 0 or above 2N (this second thing is not necessary actually).

Now we raise this matrix to the m-th power in Max-Plus algebra. This is basically an algebra where you replace addition with max and multiplication with addition. So when you do matrix "multiplication", the inner assignment is C[i][j] = max(C[i][j], A[i][k] + B[k][j]), and you initialize C[i][j] to some large number ("infinity") beforehand. The interpretation of this is pretty straightforward. Let A and B represent the optimal costs of moving from some i to some j total balance using a and b n-blocks, respectively. Then C will represent the same thing using (a+b) n-blocks.

See my code in the practice room for details, or ask for clarifications if I messed something up in my explanation :)

I used doubling algorithm to do this problem.

A bracket sequence can be simplify to the form like

)))(((( = [')' * x + '(' * y]

So we can let f[k][i][j] denote, when we build (2^k * n) brackets, and they will simplify to [')' * i + '(' * j], we can assume that the balance will never exceed N(like sereja's solution).

We can get f[0] by iterator all possible bracket sequencen, and f[k] by merge two f[k — 1] when k > 0.Assume m = 2 ^ k1 + 2 ^ k2 + .. + 2 ^ kx, we just need to merge f[k1]~f[kx] to get the answer f[...][0][0].

i see there are greedy solutions solving the problem, and also appreciated based on time complexity, but this is a straightforward dp solution which fits in the given constraints pretty well.

considering dp[n][f], where array[n] : n'th element of given array[], f : number of elements rounded down so far. integer portions of the input array elements are unnecessary, as they remain same in output sequence of rounded numbers. recursion is halted when n>2N [end of array] or f>N [more than N numbers are rounded down already]. notice that, we need N numbers to round down and the rest N to round up, so f needs to be N exactly.

then while processing dp(n,f), we can either round down the n'th number or otherwise. we attempt both of them and take the minimum based on their absolute difference of course.

My code goes here, http://mirror.codeforces.com/contest/351/submission/4674608

You can try some simple inputs and use different ways to choose which numbers are rounded up and which are rounded down. You will find that if the options we take on integers don't change, the result will be the same. Assume that we round down as many integers as possible, then simply calculate the result. Then if we reduce the number of integers rounded up by 1, the result will incrrease by 1. (Note:Here the result is signed, that means if the sum of new numbers is less than the original sum, the result is negative). If you notice these two points, finding the best answer will be very easy. Also the proof is simple too. So we just iterate on the number of integers we take rounded down, and in each step increase the result by 1, and update the best answer, until there aren't any integers are rounded down, or all round up numbers are integers. So in the program we just need to count the number of integers and calculate the initial answer(that can be done by sorting the numbers with the fractional parts), then the following work is easy. You can check my solution 4664512 for details.

http://mirror.codeforces.com/blog/entry/9070?locale=en#comment-147569

i think this is a easy one for me to understand http://mirror.codeforces.com/contest/351/submission/4677352

Took me a while to understand the Greedy Approach. Lets say the input array is A[2n]. In this array, we have to ceil n numbers and floor n numbers. We modify the input array to store only the decimal portion of the numbers. The decimal portion of the numbers also represents the amount needed to Floor the Number. We take the sum of all numbers in A as S.

If the amount to floor a number is x, then the amount to ceil the same number is (1-x).

From the given array, if we choose two indexes i & j, where we choose to floor index i and ceil index j, then the total deviation from the S due to the rounding off of the given pair would be :

Amount required to Ceil index j - Amount required to floor index i

= (1-A[j]) - A[i] , where A[i] and A[j] is the amount required to floor the number at index i & j respectively.

Now (1-A[j]) - A[i] = 1 - A[j] - A[i] = (1-A[i]) - A[j] Which implies that it doesnt matter which number you choose to ceil or floor in the given pair.

Now the TOTAL deviation from S due to all such pairs would be given by :

 1 - A[j_1] - A[i_1]
+1 - A[j_2] - A[i_2]
+1 - A[j_3] - A[i_3]
and on till
+1 -A[j_n] - A[i_n]
-------------------
= n - S

where (j_1, i_1), (j_2, i_2), ....., (j_n, i_n) are the indexes that form a pair.

The answer would have been this, but since some numbers in the array can be integers to begin with, the amount required to round them off (whether ceil or floor) is equal to 0. But in the above equation we have ceiled some of these numbers and added '1' to the total. Hence run a loop :

M = n-S
for i 1 to Min( Count(Integers in A),n ):
ans = min(ans, abs(M-i))

We are running the loop till Min( Count(Integers in A),n ) , since we can ceil at max n numbers.

4679640

A more simpler approach (for me) but O(N*2001) was to use DP. DP(i,j) = the minimum deviation from S by using the first i numbers in A and ceiling exactly j of those numbers.

The recurrence relation would be :

DP(i,j) = Minimum of 
- The ith number is Ceiled  : DP(i-1,j-1) + Amount To Ceil A[i]
- The ith number is Floored : DP(i-1,j)   - Amount to Floor A[i]

The final answer would be in DP(2n,n) since we need the minimum deviation by using the entire array of size 2n and ceiling exactly n numbers.

4675561

Next time use a better tool before making such a claim: https://www.wolframalpha.com/input/?i=555555555555555555%2F9

A number is divisible by 9 iff the sum of its digits is divisible by 9, and 18·5 is divisible by 9.

Okay the tags have now been updated and I look like a fool. :P

I'll prove that there is always an optimal (i.e. cheapest) bracket sequence where the prefix balance never exceeds 2N. This differs from what you said only slightly in that it is possible that a prefix balance exceeds 2N in many optimal solutions (I know you're probably aware of this, just trying to be precise), and also that I'm using 2N instead of N (2N is what is suggested by the editorial).

Anyway, this is the proof. Take any optimal bracket sequence. If no prefix balance is above 2N, then we are done. Otherwise, find the leftmost n-block inside which the prefix balance exceeds 2N (let's call this n-block block X). At the end of this block, the current balance is surely larger than N, so that must mean that there are some n-blocks to the right that have a negative total balance (because we must end on balance 0).

On the other hand, just before block X the prefix balance is strictly larger than N (block X could only have added N). That means that we can safely add any n-block from the right with a negative balance (because even if its balance is -N, the prefix balance will still not go negative). Now, the prefix balance inside X decreases, but it still might be larger than 2N (also note that it is surely >0 because it was >N before the move). If it is, you repeat the procedure (all the preconditions are the same as just before we made this one move).

You can repeat this until the claim is met.

Now, it might be possible to adjust this to just N, but proving that doesn't seem as easy if it is even true to begin with.

Edit: I forgot to address the issue that when you decrease this prefix balance, somewhere in the optimal solution you might get a negative prefix balance (i.e. an invalid sequence). You can fix this in a very similar manner.

It is known that we can solve this problem in O(mnlgn) using the greedy approach.

could you provide more details :)

.o. i have figured something while thinking about your equation. let's take always by block of size 2*n.

It is obvious that we are considering our options to change when we are at odd positions and we are changing the optimal positions before or equal to the current index which is yet unchanged.

now, let n=5. so, for first 10 positions the considering points would be: 1 2 3 4 5 6 7 8 9 10.

at position 1 we have no option but to change the 1st position. so, for the first block of 2n we have to consider the optimal answer with compulsory changing of 1st position, which is stored in V(2n).

But for the 2n blocks which will we join later, it may not be optimal to change the 1st bracket of those blocks. let's take for position 11 to 20. changing the 11th position may not be optimal. So, for the rest of 2n block we take V(3n) — V(n) in which our optimal answer is stored regardless of the change in 1st position of that block. the number of block yet to consider is (m/2 — 1). which is the next part of the equation.

Thanks for mentioning the greedy approach. :)

I found a different greedy solution which can be done in $$$O(n \log m)$$$.

Let's first put opening brackets everywhere. We need to pick $$$nm/2$$$ positions and put closing brackets there, so the bracket sequence will be regular and the sum $$$b_{j \bmod n} - a_{j \bmod n}$$$ for all picked positions $$$j$$$ is the least possible.

Observation 1. Consider a set of positions with the same remainder modulo $$$n$$$. Obviously, it's best to move all picked positions in this set to the right, so brackets in this set will look like "((($$$\ldots$$$)))" (the cost will not change and the sequence will stay regular).

Now, the greedy idea: let's sort all remainders $$$i$$$ by $$$b_i - a_i$$$ and going through each $$$i$$$ in this order let's try to pick as many positions with the remainder $$$i$$$ as possible (by observation 1, we'll be picking these positions from the right). To do that optimally, let's binary search the number of picked positions. Now we need to check that the sequence is regular given the number of picked positions for each remainder.

Observation 2. It suffices to check only first $$$n$$$ and last $$$n$$$ prefix balances.

Proof. Let $$$0 \ldots i$$$ be a prefix with a negative balance. If there is a whole block to the left, there might be two cases. If that block's balance is positive, then blocks before it are also positive, and thus prefix $$$0 \ldots i \bmod n$$$ is negative. If that block's balance is not positive, the blocks after it are also not positive, so we can move to the right until we are in the last block. The prefix will still be negative.

This here 97872815 is $$$O(n^2 + n \log m)$$$, but it can be done in $$$O(n \log m)$$$ with data structures.

Actually, problem D can be solved in O(NlogN) by an online algorithm. Check 4673602 for details.

All these weird problem are caused by some careless error, like visiting a[-1], or the array is not bit enough, or a variable has not been initialized. I had a too small array. Please ignore my previous post.

Can you please explain why this is correct ?

Are you sure you get right answer for test #5 on your computer? On my machine and on CF your code outputs sth wrong.

You don't check if(count >= 0) in one place. Check out this change

Suppose we have 'i' inversions at this time. Then during Jeff's turn i -> i-1 as he will always try to make the array sorted. But during Furik's turn 50% times i -> i-1 and 50% times i ->i+1.

So let the current state be dp[i];

Jeff's Turn : dp[i] = 1 + dp[i-1].

Now Furik's Turn : dp[i-1] = 1 + 0.5*dp[i-2] + 0.5*dp[i].

So, dp[i] = 1 + 1 + 0.5*dp[i-2] + 0.5*dp[i].

dp[i] = 4 + dp[i-2] (required recurrence)

EV(n) = 1 + 0.5*(EV(n-2)) + 0.5*(2+EV(n))

EV(n) represent expected value for n inversions required. As Jeff starts the game so EV(n) should be equal to 1 + g where g is 0.5*(EV(n-2)) + 0.5*(2+EV(n)) (and now it's Furik's turn). If heads appears inversions reduces by 1 and if tails appears inversions increases by 1. so g = p(head)*EV(n-2) + p(tails)*(EV(n) + 2(as 2 turns are wasted))

Suppose we have 'i' inversions at this time. Then during Jeff's turn i -> i-1 as he will always try to make the array sorted. But during Furik's turn 50% times i -> i-1 and 50% times i ->i+1.

So let the current state be dp[i];

Jeff's Turn : dp[i] = 1 + dp[i-1].

Now Furik's Turn : dp[i-1] = 1 + 0.5*dp[i-2] + 0.5*dp[i].

So, dp[i] = 1 + 1 + 0.5*dp[i-2] + 0.5*dp[i].

dp[i] = 4 + dp[i-2] (required recurrence)

Suppose we have 'i' inversions at this time. Then during Jeff's turn i -> i-1 as he will always try to make the array sorted. But during Furik's turn 50% times i -> i-1 and 50% times i ->i+1.

So let the current state be dp[i];

Jeff's Turn : dp[i] = 1 + dp[i-1].

Now Furik's Turn : dp[i-1] = 1 + 0.5*dp[i-2] + 0.5*dp[i].

So, dp[i] = 1 + 1 + 0.5*dp[i-2] + 0.5*dp[i].

dp[i] = 4 + dp[i-2] (required recurrence)