Разбор задач Codeforces Round #215
Each time we will go through the array and look for the minimal element which is not yet marked. If we find an item, we add it to the answer and mark it, otherwise we will subtract the penlty from answer.
We will count value ansi — number of different elements on the suffix from i. For calculation will walk from the end of the array, and we count ansi = ansi + 1 + newai, newai equals to 1, if element ai has not yet met and 0 otherwise.
If you look at what is written in the statment, it becomes clear that the algorithm finishes its work, if we can get a string like: xx, yy, zz, zyxzyxzyx... and all its cyclic shuffles. To check you just need to know the number of letters x, y and z separately. Quantities can be counted using partial sums.
We will divide the sequence on min(n, p) sequences. 1-st, (1 + p)-th, (1 + 2·p)-th, ... element will go to the first sequence, 2-nd, (2 + p)-th, (2 + 2·p)-th... will go to the second sequence and so on. Now you need to find an answer for each of them, considering that p = 1. This can be solved by a simple method. You can go along the sequence from left to right and count the number of occurrences of each number. If the number of occurrences of each number will match the number of occurrences of the same number in the second sequence, then everything is OK.
Clear that we need to collect as many of the most expensive properties that would have been possible to build the array. Note that having n numbers, we have m = n·(n - 1) / 2 binding ties. See that this is a graph in which to do Euler path, adding as little as possible edges. For n%2 = 1 — everything is clear, and for n%2 = 0, you need to add an additional n / 2 - 1 rib. Why? This is your homework :)
The detailed explanation can be found here.
Replace out sets by array, where the element — the number set to which its index belongs. Now take all the consequitive sub-arrays with lengths of d and find a set of elements that were not found in that sub array. Clearly, if we as a response to select a subset of such set, it does not fit us. Remember all those "bad set." As we know all of them, we can find all the "bad" subsets. Now we choose the set with maximum count of elements which is not a bad set. It is better to work here with bit masks.
We assume that the intervals are sorted, and in the end we will multiply the answer by n!, We can do so, as all segments are different.
Consider two cases n > m and n ≤ m. It would seem that you need to write different dynamics for them, but not difficult to show that in the first case the answer is always 0 . The second case is the following dynamics : dpi, l, r, i — how many numbers we have considered , l, r — only in this interval will be present number i. Also, we will need an additional dynamic si, l, i — how many numbers are considered , l — how many segments are already closed , and i does not belong to any segment . There will be 4 transfers, since every number we can not begin and end with more than one segment.
Now we should add x to our solution, it is quite simple: just add another parameter 0 / 1 in our dynamics, if we had such a element in the beginning of some interval or not. With out dynamics, it is not difficult.