How to solve the problem Mex division from snackdown elimination round
I don’t have enough karma points so I am asking this question here.
1 Like
Give a search to forums. There is a separate thread for 1 karma users to ask questions. Converted to questions for now.
How much time they will take to upload the editorials??? They sure take a long time.
1 Like
We need to find the number of ways of splitting the given array into contiguous parts, such that the MEX of any part does not exceed ‘k’, one thing to note is that, although the constraints on ‘k’ are high, if k >= n, then every possible way of splitting is valid, and your answer will be 2^(n-1) (why ?).
Now, when k < n, let A[] be the input array, let ans[i] denote the number of ways of splitting A[0…i], you can use ans[0]…ans[i] to calculate ans[i+1], we will simply see how far to the left the last part can extend. I will explain this with an example.
n=5 k=3 A={0,1,2,3,4}, for this example, lets suppose that we need to find ans[4] (0-based indexing, last position):
We need to split A[0…4] into parts, lets take a look at the choices that we have for the rightmost part. We can have {4}, {3,4}, {2,3,4}, {1,2,3,4} but not {0,1,2,3,4} because then MEX of that part will be 5. So the answer in this case will be ans[0]+ans[1]+ans[2]+ans[3], with each term in the sum corresponding to the number of ways of splitting the whole array, with the rightmost part as the ones I mentioned above.
Now that the original problem is solved, there’s something else that needs to be calculated before doing this. For calculating the answer in the above example, we had to see how far to the left can the last part extend. We need to calculate this value for every position in the array. I’ll take another example for this:n=3 k=1 A={0,1,2} lets store the values that we calculate in another array called pos. pos[i] will contain the minimum index ‘j’ such that A[j…i] is a valid part ie. it has MEX <= k. Let’s do this manually for this example. Lets calculate pos[0], it will be 0. pos[1] will be 1 because we can have {1} as a part, but not {0,1}, pos[2] will also be 1, you can see why. Observe that the values in the pos[] array form an increasing sequence, {0,1,1} in this case. This will always be true because pos[i] says that the subarray ending at ‘i’ cannot go beyond pos[i], since going any further would make MEX >= k, then obviously, the subarray ending at ‘i+1’ will also have MEX >= k if it goes beyond pos[i], so you can find fill the array pos[], in a way similar to the two pointer method, while keeping track of the count of the relevant numbers ie. numbers in the range 0…k, you can use an array for this because we are only looking at cases where k < n, and n is less than 5*10^5.
We will use these values to calculate our ans[] array quickly, ans[i] will be equal to ans[i-1]+ans[i-2]…+ans[i-pos[i]], you can find this quickly by maintaining a prefix sum of the already calculated answers. Let me know if there’s something that you didn’t understand (comment). Link to my submission :
4 Likes
That was a nice explanation.
Can you explain how did u end up with this :
“you can use ans[0]…ans[i] to calculate ans[i+1], we will simply see how far to the left the last part can extend.”
If A = [1,2,3] and if we partition it as [1,2] and [3] what is the MEX of [1,2]? 0 or 3?
Can we partition [1,2,3] as [1,3] and [2] if not why? How can we assume only contigous partition?
Its a standard approach for problems like this, where you need to count the number of ways or maximise/minimise something by splitting an array and maintaining some condition on each of the parts or a combination of parts (MEX in this case), you start with the number of ways to pick one part, and then recursively calculate the number of ways for splitting the remaining part. Try solving these problems:
http://codeforces.com/problemset/problem/811/C
https://www.codechef.com/NOV16/problems/GIFTCHEF
https://www.codechef.com/MAY17/problems/KILLER (small subtask)
mex of [1,2] is 0.
[1,3] and [2] is not a valid partition,it is given in the question that the partitions must be subarrays and we know that subarrays are contiguous.