Educational Round 89 Problem E

Revision en1, by yesnomaybe, 2020-06-12 10:38:10

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.me/contest/1366/problem/E Solution Link : https://codeforces.me/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

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English yesnomaybe 2020-06-12 10:38:10 1191 Initial revision (published)