None_Po's blog

Partition array to maximize sum of MEX – need help with approach
By None_Po, history, 2 months ago, In English

Problem:

Given an array A of size N

We need to partition it into non-overlapping subarrays (continuous segments)

For each segment: MEX = smallest non-negative integer not present

Score = sum of MEX of all segments

Goal: Maximize total score

example

  1. a= 0,2,1,1 ans= 3 (we can divide it into {0,2,1},{1} whose MEX are 3 and 0 respectively)

2.a= 0,2,1,1,0 ans= 5 (we can divide it into {0,2,1},{1,0} whose MEX are 3 and 2 respectively)

What I tried-

  1. DP, 1 state, but it had a for loop inside it that was running from i to n. O(n^2). This caused TLE ofcourse.
  2. DP, same as above, but I called rec() it whenever I encountered 0;
   mex=0;
   for(i to n)
      keeping mex updated
      if(arr[i]==0)
          ans=max(ans, mex+rec(i))

   return max(ans,mex)

This ran few cases for the dry run, but for hidden cases it wasn't running. the reason i thought of calling rec() because the partition need an element 0 for MEX to calculate

  1. greedy, but was couldn't find the right approach/ direction for greedy. I was again cutting whenever i was finding 0 but wasn't good solution.

Doubt:

  • Is there a correct greedy strategy?
  • Or is there a way to optimize DP?
  • What observation am I missing?

Thanks.

  • Vote: I like it
  • +13
  • Vote: I do not like it

»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

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

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

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

@None_Po please provide the problem link

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

    This question was asked in a test, so i dont have it.

    The test ended and it was on hackerearth and was set up by my college.

    So dont have.

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

Let’s take your example: 0, 2, 1, 1, 0 For the full array we know the MEX 3. Now suppose we maintain a count like cnt[] = {2, 2, 1, 0, 0, …}. If you remove all occurrences of a value v such that v < MEX, then the MEX becomes v itself.

So, by removing values from left to right, you can determine the MEX of the remaining (right-side) array and for the left side, you can just add values one by onea DSU-based approach should work Or, you can apply the same process in reverse and store the values.

So, both O(n) and O(n log n) approaches are possible.

I misunderstood the question at first, I thought only need to divide the array into 2 subarrays. so

Update: From every zero, we will take the MEX before the next zero. Now, if there are x zeros, we have x blocks. Iterate from the back and decide whether it’s better to merge two adjacent blocks or not. Now merge if (old MEX1 + old MEX2) < new merged MEX.
Also, if you have a link to the problem, please share it, I’d like to give it a try.

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

    i did try the 0 one, like u said.

    i tried DP, my 2nd approach is similar to what u said in update.

    sorry, dont have the link. This question was asked in a test, so i dont have it. The test ended and it was on hackerearth and was set up by my college.

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

    If there are x zeros, we have ≤ x blocks. For test [5,4,3,2,0,0,1] for 1 block answer is 6, while for 2 blocks is 3

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

My assumption is

dp[i] considering some partition ending at r = i, the most optional l for that subarray partition is opt[i] = l

my whole assumption is that opt array is a sorted array, i'm not that much sure, but i think opt array should be non-decreasing, if this is true, we can use two pointer to make the transition amortized O(n), and mex inside last subarray can be maintained using a set

if i'm incorrect, someone correct me

→ Reply