yesnomaybe's blog

Educational Round 89 Problem E
By yesnomaybe, history, 5 years ago, In English

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://mirror.codeforces.com/contest/1366/problem/E Solution Link : https://mirror.codeforces.com/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
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 6   Vote: I like it 0 Vote: I do not like it

      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$$$

      → Reply