Problem E. Can someone please help me find issue with my solution? Was able to pass sample test cases but it failed on submission.
Problem Link : https://codeforces.net/contest/1366/problem/E Solution Link : https://codeforces.net/contest/1366/submission/83481690
Here is my greedy approach. For each element (at index i) in B, I keep three variables
0-indexed
start[i] and end[i] : denoting the range in Array A in which B[i] is minimum.
start[i] denotes index in array A from where B[i] can start being minimum (first occurrence of B[i] from where it can start being minimum).
mov[i] : the index of the last occurrence of B[i] in range (start[i], end[i]), such that B[i] is minimum in range (mov[i], end[i]) in Array A (I calculate this for B[1, m-1])
Note : That means for B[i-1], I can choose subarray ending at index from end[i-1] to mov[i] - 1
I calculate answer for each i from 0 to m-2
ans = 1
ans = ans * ((mov[i+1] - 1) - end[i] + 1) for all i in range 0,m-2
Example :
A : 12 10 15 20 20 25 30
B : 10 20 30
start : 0 3 7
end : 2 6 7
mov : 4 7
ans : 2 1
ans = 2 * 1 = 2
start[i] doesn't necessarily have to be the first occurrence of B[i], take for example (assuming 0-indexing),
A : 12 10 15 25 20 20 25 30
B : 10 20 30
start[1] can be 3 whereas your code calculates it as 4.
Right, as I wasn't using start[i] anywhere to calculate the final answer. I missed that case. Thanks for pointing out.
I didn't code what I exactly thought to code. :/
As in the approached mentioned — start[i] should be from where B[i] could start being minimum (and it need not be the first occurrence as you pointed). Nonetheless, is my approach correct? I have an intuition but not so sure.
let's count the number of ways of setting the border between the $$$i-th$$$ and the $$$(i + 1)-th$$$ subarray, it's the same as deciding which element will be the last element in the $$$i-th$$$ subarray because we can put the border right after that element.
let $$$end[i]$$$ be the index of the last occurrence of $$$B[i]$$$, and $$$start[i]$$$ as you defined it above.
our candidates(indices) for last element of the $$$i-th$$$ subarray are :
$$$(start[i + 1] - 1, start[i + 1], ..... , end[i + 1] - 1)$$$, we can put the border right after these elements.
So the number of ways is $$$(end[i + 1] - start[i + 1] - 1)$$$.
example :
$$$A : 12, 10, 15, 25, 25, 25, 20, 20, 25, 30$$$
$$$B : 10, 20, 30$$$
possible borders between first and second subarray : $$$12, 10, 15$$$ | $$$25$$$ | $$$25$$$ | $$$25$$$ | $$$20$$$ | $$$20$$$, $$$25, 30$$$ . In this case $$$5$$$ choices for borders.
the final answer is the product of $$$(end[i + 1] - start[i + 1] - 1)$$$ s for all possible $$$i$$$
and for any $$$B[i]$$$, if there's a smaller element to the right of the last occurrence of $$$B[i]$$$, return $$$0$$$