You are given two integers x and y and array a of n integers. x is initially equal to zero. For every element in the a you can either add it to x, or you can subtract it from x. You have to tell whether you can make the number x equal to the number y by any means. An O(n^2) approach would work too. Additionally all the elements of a are <=300, I don't know if it's of any use.
Note that x should be compared to y only after all the elements of a are either added to it or subtracted from it.
Thanks.
$$$dp[0][0]=1;$$$
$$$dp[i][j]=(dp[i-1][j-a[i]||dp[i-1][j+a[i]]);$$$
$$$ans=dp[n][y].$$$
Does the second dp state need to have a size of 300 * n, or is there a way to compress it?
If n = 1e3, the total memory would be 3e8, which is too big.
You're only storing booleans in the dp array, which means you could pack 64 dp values into a single 64 bit integer. It would only take around 40MB of memory which should be enough.
Sir, what do you mean by packing 64 dp value into a 64 bit integer? How do we do that? Please tell
In C++ you can use
bitsetfor storing bools and work with them $$$32-64$$$ times faster than with ints. For this problem:const int M = 300005, N = 2 * M; bitset <N> b; b[M] = 1; for(int i = 0; i < n; i++) b = ((b << a[i]) | (b >> a[i]));In the end $$$b_{i+M} = 1$$$ if we can add $$$i$$$ to the start number.
This solution uses very little memory because we store all dp values in one bitset and change it depending on $$$a[i]$$$.
Why not use the loop dp optimization.
Just empty the dp[i%2] array at each i-loop.