Editorial for Codeforces Round #204
Solution is looking for few cases:
1. If we do not have zeros, then the answer is -1.
2. If we have less than 9 fives, then the answer is 0.
3. Otherwise, the answer is:
4. 1. The maximum number of fives divisible by 9
4. 2. All zeros, we have
We will go through the array from left to right. At each step, we will store the arrays:
1. next x — the last occurrence of the number x
2. period x — period, which occurs x
3. fail x — whether a time when the number of x no longer fit
Now, when we get a new number we considering the case when it is the first, second or occurred more than twice.
All the cases described in any past system testing solution.
Initially, we should remember the number of integers — C. On next step we will round down all numbers and count the sum. Now we can change the sum, rounding up some numbers, with those not matter what kind of, the main thing — how many. Consider a couple what we could get:
1. (int, int) (c 1)
2. (int, double) (c 2)
3. (double, int) (c 3)
4. (double, double) (c 4)
Iterate over the number of pairs of the first type. Then we know the total number of second and third type and number of the fourth type:
1. c 2 + c 3 = C - 2c 1
2. c 4 = N - (c 1 + c 2 + c 3)
Check to see if you can get such numbers (enough for us count of integers and real numbers, respectively). We find that we can round up from c 4 to c 4 + c 2 + c 3 numbers. We will find the best choise.
ote that after each step, the number of inversions in the permutation is changed by 1. Let us turn to the inversions of the permutation — let them be I pcs. It is clear that when we have one inversion, then the answer — 1. Now we will see how to use it further:
1. it is clear that after a Jeff's step inversions will become lower by 1
2. it is clear that after a Furik's step inversions will be on 1 lowerwith porbability of 0, 5, and on 1 greater with probability of 0, 5.
3. we have the formula for an answer ans I = 1 + 1 + ans I - 1 - 1 × 0.5 + ans I - 1 + 1 × 0.5
4. after transformation we have ans I = 4 + ans I - 2.
How to solve the problem for small NM? Just use the dynamic programming dp i, j — minimum cost to build i first brackets with the balance j. Transfers are simple:
1. dp i, j + a i + 1 -> dp i + 1, j + 1
2. dp i, j + b i + 1 -> dp i + 1, j - 1
3. we make transfers only when balance will be non-negative
4. starting state dp 0, 0 = 0
In this problem, we can assume that the balance will never exceed 2N. The proof is left as homework.
And by using this fact problem can be done by erecting a matrix to the power:
1. lets T i, j — cost of transfer from balance i to balance j, using N brackets
2. (T M)0, 0 — answer to the problem
After the first request we can sort the numbers and for further moves will be able to remove all occurrences of a certain number. So the answer is the number of different numbers + 1 if there is no number, occurrence of which form an arithmetic progression.
Number of different numbers on a segment — standart problem, can be done O(N 1.5) with offline algorithm.
The problem about finding the right number will be solved in a similar algorithm:
1. lets sort queries like pairs (l i / 300, r i), we use integer dividing
2. learn how to move from the interval (l, r) to intervals (l - 1, r), (l + 1, r), (l, r - 1), (l, r + 1) with complexcity O(1)
3. by means of such an operation will move from one segment to the next, in the amount of the operation algorithm will works O(N 1.5)
It remains to learn how to make the change on the interval by 1 element. Such a problem can be solved quite simply:
1. we craete deque for all value of numbers in array
2. depending on changes in the segment will add / remove items to the start / end of the respective deque
3. check whether the resulting deque is arithmetic progression. it will be homework.
We make the zero step, replace the elements on their modules.
The first thing you need to understand the way in which we will build our response. After selecting a few ways to understand the fact that initially you need to determine the sign of the largest numbers.
Consider the case where the current step we have only one maximal element. It is clear that if you put a sign - all the elements on the left of this will form an inversion, while on the right there will be no inversions. If we do not put a sign - it will all be the opposite. We select the best one and cross out the number of the array, it will not affect to some inversion.
Now we should understand how to read the response when the highs more than one. We write the dynamics dp[i][j] — how much inversions can you get, when we looked at the first i higest values and j from them lefted as possitive. Of these dynamics is not difficult to make the transition and get the answer.
And so we have a simple and short algorithm:
1. Iterates until the array is not empty
2. Find all the maximal elements
3. Calculate dynamics and find right signs
4. Remove elements from an array