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↵
↵
3. 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.
↵
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↵
↵
3. 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.
