Codeforces Round #804 (Div. 2) Editorial reupload

Revision en2, by tibinyte, 2022-10-31 00:07:58

D — Almost Triple Deletions

Author: Gheal

Hints

Hint 1

Consider the opposite problem: What is the smallest possible length of a final array?

Hint 2

For which arrays is the smallest possible final length equal to

Unable to parse markup [type=CF_MATHJAX]

$?

Hint 3

Considering the second hint, it is possible to completely remove some subsequences from the array.

Solution

Lemma: An array

Unable to parse markup [type=CF_MATHJAX]

$ can be fully deleted via a sequence of operations if and only if it satisfies both of the following constraints:

Unable to parse markup [type=CF_MATHJAX]

$ is even

The maximum frequency of any element in the array is at most

Unable to parse markup [type=CF_MATHJAX]

$.

Proof

If

Unable to parse markup [type=CF_MATHJAX]

$ is odd, then any final array will also have an odd length, which can't be

Unable to parse markup [type=CF_MATHJAX]

$.

An optimal strategy is to always delete one of the most frequent elements and any one of its neighbours. If the most frequent element occurs

Unable to parse markup [type=CF_MATHJAX]

$ times, then the final array will have at least

Unable to parse markup [type=CF_MATHJAX]

$ elements. Otherwise, this strategy ensures the full deletion of the array, since, after performing an operation, it is impossible for an element to occur more than

Unable to parse markup [type=CF_MATHJAX]

$ times in the array.

Since the maximum frequency of a value for every subsequence

Unable to parse markup [type=CF_MATHJAX]

$ can be computed in

Unable to parse markup [type=CF_MATHJAX]

$, it is possible to precompute all subsequences which can be deleted via a sequence of operations.

Let

Unable to parse markup [type=CF_MATHJAX]

$ be the maximum length of a final array consisting of

Unable to parse markup [type=CF_MATHJAX]

$ and some subarray from the first

Unable to parse markup [type=CF_MATHJAX]

$ elements. Initially,

Unable to parse markup [type=CF_MATHJAX]

$ is set to

Unable to parse markup [type=CF_MATHJAX]

$ if the prefix

Unable to parse markup [type=CF_MATHJAX]

$ can be fully deleted. Otherwise,

Unable to parse markup [type=CF_MATHJAX]

$.

For every pair of indices

Unable to parse markup [type=CF_MATHJAX]

$ and

Unable to parse markup [type=CF_MATHJAX]

$ (

Unable to parse markup [type=CF_MATHJAX]

$), if we can fully delete the subsequence

Unable to parse markup [type=CF_MATHJAX]

$, then we can append

Unable to parse markup [type=CF_MATHJAX]

$ to any final array ending in

Unable to parse markup [type=CF_MATHJAX]

$. Naturally,

Unable to parse markup [type=CF_MATHJAX]

$ will be strictly greater than

Unable to parse markup [type=CF_MATHJAX]

$. This gives us the following recurrence:

Unable to parse markup [type=CF_MATHJAX]

$

If we define a final array as a subarray of equal elements from the array

Unable to parse markup [type=CF_MATHJAX]

$, to which

Unable to parse markup [type=CF_MATHJAX]

$ is forcefully appended, then the final answer can be written as

Unable to parse markup [type=CF_MATHJAX]

$. Note that, when computing

Unable to parse markup [type=CF_MATHJAX]

$,

Unable to parse markup [type=CF_MATHJAX]

$ should not be compared to

Unable to parse markup [type=CF_MATHJAX]

$.

Total time complexity per testcase:

Unable to parse markup [type=CF_MATHJAX]

$.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en42 English tibinyte 2022-11-06 21:29:15 0 (published)
en41 English tibinyte 2022-11-06 19:15:16 0 (saved to drafts)
en40 English Gheal 2022-10-31 22:14:25 0 (published)
en39 English Gheal 2022-10-31 22:12:04 16
en38 English Gheal 2022-10-31 22:11:13 13 Tiny change: 'er authors of round 804. We are v' -> 'er authors. We are v'
en37 English Gheal 2022-10-31 22:10:53 211
en36 English Gheal 2022-10-31 22:04:25 26
en35 English Gheal 2022-10-31 22:03:40 39
en34 English Gheal 2022-10-31 22:01:52 74
en33 English Gheal 2022-10-31 21:57:17 200
en32 English Gheal 2022-10-31 21:57:01 747
en31 English Gheal 2022-10-31 21:48:53 629
en30 English tibinyte 2022-10-31 21:41:38 7
en29 English tibinyte 2022-10-31 21:41:03 38
en28 English Gheal 2022-10-31 21:38:59 40
en27 English tibinyte 2022-10-31 21:37:09 17
en26 English Gheal 2022-10-31 21:34:15 81
en25 English Gheal 2022-10-31 21:33:19 2311
en24 English tibinyte 2022-10-31 21:33:02 34
en23 English tibinyte 2022-10-31 21:32:50 340
en22 English tibinyte 2022-10-31 21:31:52 3999
en21 English tibinyte 2022-10-31 21:29:21 303
en20 English tibinyte 2022-10-31 21:29:00 18 Tiny change: 'anks to \ncadmiumky\n ):\n\nT' -> 'anks to \n[user:cadmiumky]\n ):\n\nT'
en19 English tibinyte 2022-10-31 21:28:31 4797
en18 English Gheal 2022-10-31 21:27:42 924
en17 English Gheal 2022-10-31 21:18:46 409
en16 English Gheal 2022-10-31 21:16:45 519
en15 English Gheal 2022-10-31 21:13:59 46
en14 English Gheal 2022-10-31 21:12:58 48
en13 English Gheal 2022-10-31 21:11:37 1405
en12 English tibinyte 2022-10-31 00:18:26 7
en11 English tibinyte 2022-10-31 00:18:18 79
en10 English tibinyte 2022-10-31 00:18:10 73
en9 English tibinyte 2022-10-31 00:18:00 3259
en8 English tibinyte 2022-10-31 00:16:45 3531
en7 English tibinyte 2022-10-31 00:15:55 2754
en6 English tibinyte 2022-10-31 00:15:29 2047
en5 English tibinyte 2022-10-31 00:14:20 1085
en4 English tibinyte 2022-10-31 00:12:33 2468
en3 English tibinyte 2022-10-31 00:08:20 10
en2 English tibinyte 2022-10-31 00:07:58 2606
en1 English Gheal 2022-10-30 23:34:08 50 Initial revision (saved to drafts)