kavascg's blog

Question on maxiumum mex
By kavascg, history, 23 months ago, In English

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 .

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (9)
| Write comment?
»
23 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kavascg (previous revision, new revision, compare).

→ Reply
»
23 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I misread the problem

→ Reply
  • »
    »
    23 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
23 months ago, hide # |
← Rev. 3  
Vote: I like it +7 Vote: I do not like it

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.

Code

A nice problem that uses the same idea : 2030E - MEXimize the Score

→ Reply
  • »
    »
    23 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    this would be for subsquence for subarray it would be diff [0 0 1 1 ] will have ans 3

    → Reply
»
23 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This looks like DP where dp[i] is the score of the prefix until i but I didn't solve yet

→ Reply
»
23 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kavascg (previous revision, new revision, compare).

→ Reply
»
23 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kavascg (previous revision, new revision, compare).

→ Reply
»
6 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Did you got the solution?

→ Reply