| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
Suppose we partition the elements of an array b into any number k of non-empty subarrays S1,S2,…,Sk , where k is an arbitrary positive integer. Define the score of b as the maximum value of MEX(S1)+MEX(S2)+…+MEX(Sk) over all possible partitions of b for any integer k n <= 2e5
continous subarrays not for subsequence for [0 0 1 1] ans is 3
how can i calculate score .
Auto comment: topic has been updated by kavascg (previous revision, new revision, compare).
I misread the problem
how would u implement it? like how would you make partition i can think of an O(n^2) approach and ans for [ 0 1 2 3 6 5 4 3 2 1 0 0] will be 12
The solution is:
Make a frequency table, store the frequency of all elements in the array, make a prefix (min) array of that frequency table, the answer is the sum of all elements in the prefix min array.
A nice problem that uses the same idea : 2030E - MEXimize the Score
this would be for subsquence for subarray it would be diff [0 0 1 1 ] will have ans 3
This looks like DP where dp[i] is the score of the prefix until i but I didn't solve yet
Auto comment: topic has been updated by kavascg (previous revision, new revision, compare).
Auto comment: topic has been updated by kavascg (previous revision, new revision, compare).
Can you write the problem a bit better? What is the constraint on the numbers in the array?
Where can I try submitting the problem to test?
Few observations (Assuming the array only contains non-negatives):
Here's a possible solution based on above observation but I am still thinking on how to prove that this is optimal.
Count 0s in the array. No 0s means ans = 0 (because no matter how many partitions you do, MEX of each partition is 0). That many partition should be optimal. Now, the question comes how to do a partition. We can find the left most 0. Then partition, that much prefix (index 0 of array and index of first 0). Then from first 0 till second 0, there should be some part of array that belongs to first 0 and some part that belongs to second 0. This is where I am stuck..but I think the solution would be in this direction.