This problem is the easiest one. You need to use only div and mod functions. If *n*>0, then answer is *n*, else you need to delete one of two digits.

For better understanding you can look at solution.

Precalculate some array *A*_{i}, that *A*_{i} = 1, if *s*_{i} = *s*_{i + 1}, else *A*_{i} = 0. Now for any query (*l*, *r*), you need to find sum of *A*_{i}, that (*l* ≤ *i* < *r*). It is standart problem. For solving this problem you can precalcutate some another array Sum, where *Sum*_{i} = *A*_{1} + *A*_{2} + ... + *A*_{i}. Then sum of interval (*l*, *r*) is Sum_r — Sum_{l-1}.

For better understanding you can look at solution.

At the start sort array. Let *C*_{i} — number of times of entering the number in *A*_{і} optimal placement. Answer is sum of *A*_{i} * *C*_{i} for all *i* (1 ≤ *i* ≤ 4^{n}). If we look at the array *C*, we can see that for maximal element *C* = *n* + 1 (for array with size 4^{n}), then for second, third and fourth maximum elements *C* = *n*. On this basis we can see, that for array with non-increasing order answer calculate like *Sum*(1, 1) + *Sum*(1, 4) + *Sum*(1, 16) + ... + *Sum*(1, 4^{n}). So, for solve this problem you have to know only sort.

For better understanding you can look at solution

To solve this problem you need to use dynamic programming. Let *Full*_{i, j} — minimal cost of covering interval (*i*, *j*). Fix left border and move right. You can solve this subtask with complexity *O*(*nm*) or *O*(*nmlogn*). Now we need to solve the standart problem of dynamic programming. Cover *K* points with intervals that have not intersect. This problem with square dynamic. *dp*_{i, j} — minimal cost of covering *j*-points, if you look some prefix length *i*. Answer for all problem is minimal integer from *dp*_{i, j}, (*k* ≤ *j* ≤ *n*).

To solve second part:

1) *dp*_{i + 1, j} = *min*(*dp*_{i + 1, j}, *dp*_{i, j}) — skip point with number *i* + 1

2) *dp*_{k, j + len} = *min*(*dp*_{k, j + len}, *dp*_{i, j} + *Cost*); *Cost* — cost of interval with length *len*, that ending at point k. We precalculate *Cost* at first part of solution.

For better understanding you can look at solution

Author solution is harder than that which is offered by MrDindows. It is solution of MrDindows.

1) Get the number of our sequences in sorted by frequencies. Thus from the first sequence (hereinafter — the first type) — in a direct order from the second — to the contrary.

2) These numbers are put on the stack, where if, recording onto the stack of the second type, we find the number at the top of the first type, then this pair of extract and add to the answer.

3) At the end, obviously the stack we can find a number of properties of the second type and the first bottom — on. Then their grouping in response pairs with the start and end.

For better understanding you can look at solution.

*Sorry* *for* *waiting*.

thanks and great contest

Will the English editorial public？

google translate may help you ;)

sorry for delay, but in nearest future I will make it.

thx

I still don't get problem D's explanation.

This editorial looks like it is written for those whom have already solved the problems, not for those who struggled with some.

Me too. Please explain it clearly. DP[i,j] is explained really confusing.

Thanks. GL & HF!

I will try to explain.

First, lets define cost[i,j] as the minimum cost to fix interval [i,j]. This can be achieved by doing the following for each of the M companies that fixes the holes of the interval [a,b] with cost C: cost[a,l] = min(cost[a,l], C), a <= l <= b.

Once cost[i,j] is defined lets define dp[i,j]. dp[i,j] stores the minimum cost to fix J holes using the interval [1,i]. With this definition our answer lies in dp[N,k] (N as defined by the problem statement, length of the road/amount of holes).

Now lets look at the transitions of this state. To compute dp[i,j] I have to take into account:

a) not fixing any hole, or in other words, dp[i,j] = min(dp[i,j], dp[k,j], 1 <= k < i (with this I'm querying every interval [1,k] that is smaller than [1,i] that has already fixed J holes);

b) to fix k holes. The holes that we'are going to fix are the ones at the end ([i-k,i], 1 <= k <= i). So we will query the states dp[i,j] = min(dp[i,j], dp[i-k][j-k]+cost[i-k][i]) [1].

This works because a) the problem statements says to "fix at LEAST k holes" b) it will not add the cost of a company more than one time (if you can't see this stare a bit longer at the code).

[1] the indexes are not quite correct, take a look at my code: http://codeforces.com/contest/313/submission/3812990

nice.

but no need to calculate

`dp[i,j] = min(dp[i,j], dp[k,j], 1 <= k < i`

because these values do not change when you go to new "i". enough of this:`dp[i][j] = min(dp[i][j], dp[i-1][j]);`

sorry for my english.

in problem C, i can't seem to understand why the sorting worked here. i was thinking of this to recursively divide the matrix at each step and then find the maximum of such submatrices and the maximum of whole matrix and then add them and then so on.

i don't understand how magically you sorted them and did those things mentioned above and it did what exactly is mentioned in the problem i.e dividing the matrix into submatrices.

can you make this problem C little clear to me especially WHY THIS SORTING ?

Your largest matrix will have 4^N integers. At first, you will pick the largest number from it, right? Next, you break this largest matrix, into four smaller matrices. You will be picking four integers out of them, such that your overall beauty is maximised. That is only possible if these four matrices have the four largest numbers out of the 4^N integers in them. On next step, you get 16 smaller matrices, and you want them to have the largest 16 integers in them in order to maximise overall beauty. And so on...

I hope you get the idea behind sorting now.

wonder to know the harder "author solution" since the correctness of "MrDindows" is not that obvious.

can you explain more clearly?

thanks in advanced.

This is my idea but my code wasn't right for samples: First I define dp[i][j][k] = minimum cost to fix at least k holes in j first holes using first i companies. while companies are sorted by their right points. And the update: dp[i][j][k] = min (dp[i — 1][j][k], dp[i — 1][j — (j — company[i].left + 1)][k — (j — company[i].left)] + company[i].cost) I saw that the difference between second and third dimensions of dp is always the same, so I omitted third dimension. And so this dp is my solution: dp[i][j] = minimum cost to fix at least j — n + k holes in first j holes using first i companies while companies are sorted. Is this solution right ? :-?

Your intervals are not intersect. Is it right? If its true, then its wrong, because your intervals may intersect. For example: 10 2 5 1 4 1 2 5 1

You need to take 2 intervals, that covers 5 points. Is it clear now?

I don't get why my solution doesn't satisfy this condition. :-?

You solution dont use intervals if they are intersect.

Div2 C Illya and Matrixcan be solved using BFS by constructing a tree of maximum element in a submatrix (a tree very similar to Quad Tree/2D Segment Tree) also. You can refer following solution.Implementation using Queue

@divyank1 The main solution provided in the editorial is also very similar too. Thanks

313C gives a TLE on test 48 when submitted on GNU C++14, but the same code gets ACed when submitted on GNU C++.

Why is that the case?

Problem E hint :We have`0 <= a,b,c < m`

`if (a + b >= m and c + b < m) (resp. c + a)`

`then (always) (c + b) % m >= (a + b) % m`

but why (c + b) % m >= (a + b) % m ?

<

m, 0 <a,b<m<

m