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