PROBLEM LINK:Author: Misha Chorniy DIFFICULTY:MediumHard PREREQUISITES:Dynamic Programming PROBLEM:Given are two arrays $S[1..N]$ and $X[1..N]$. We have to tell how many vectors $V$ of length $N$ exist such that $V_i \geq X_i$ if $S_i = 1$ and $V_i \leq X_i$ if $S_i = 0$. EXPLANATION:The key insight for this problem is that we can write the given $N$ numbers into a matrix of $N*D$ size, where $D = 18$ and then do a digitbydigit DP. We maintain a 6 state DP $dp[mask][now][pos][pre][sum][exist]$. The states are:
We can now give the rucurrence for this DP. When $pos < N$, we have the following recurrences:
Please follow Setter's solution for implementation details. COMPLEXITY:$\mathcal{O}(2^N*N^3*D)$ which a constant of complexity equivalent to 300. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 20 Dec '15, 23:50

Don't you think the editorial should be more detailed? answered 22 Jan '16, 19:33

answered 22 Dec '15, 19:49

What is the meaning of the following line? now and pos: putting (now+1) digits in first pos elements and now digits in last (N−pos) elements. Why are we doing this? What happens on incrementing the now + 1 th digit ? answered 20 May, 03:55

now and pos: putting (now+1) digits in first pos elements and now digits in last (N−pos) elements.This step is not clear .optimal substructure is not explained .Can anyone explain this step? answered 20 May, 13:20

Author and Tester solution link is not working. Any alternate link please?