fkndonttrespass's blog

An algorithmic problem I don't know the solution to
By fkndonttrespass, history, 22 months ago, In English

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.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

$$$dp[0][0]=1;$$$

$$$dp[i][j]=(dp[i-1][j-a[i]||dp[i-1][j+a[i]]);$$$

$$$ans=dp[n][y].$$$

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sir, what do you mean by packing 64 dp value into a 64 bit integer? How do we do that? Please tell

        → Reply
        • »
          »
          »
          »
          »
          22 months ago, # ^ |
          ← Rev. 2   Vote: I like it +9 Vote: I do not like it

          In C++ you can use bitset for 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]$$$.

          → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it +36 Vote: I do not like it

        Why not use the loop dp optimization.

        dp[0][0]=1
dp[i%2][j]=(dp[(i+1)%2][j-a[i]]||dp[(i+1)%2][j+a[i]]);
dp[n%2][y]

        Just empty the dp[i%2] array at each i-loop.

        → Reply