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

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