Satoru's blog

Sum in array
By Satoru, 4 years ago, In English

Hello codeforces

Can you help me solve this problem:

Given an array of size $$$k$$$, the sum of it's elements is equal to $$$n$$$, print a binary string of size $$$n$$$ ('$$$1$$$' if you can create $$$i$$$ by taking a subset from the array, '$$$0$$$' otherwise)

Example

UPD: Constraints: $$$1 <= n, k <= 10^5$$$

UPD2: thanks purplesyringa for the solution

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

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Pretty Standard DP Problem I think Surf SUBSET SUM Problem, N*K dp table can do the trick for you

→ Reply
»
4 years ago, # |
  Vote: I like it +26 Vote: I do not like it

This is very similar to the knapsack problem so I'm afraid there is no polynomial solution. I think you should try non-asymptotic optimizations. Instead of using arrays, use bitset, this should speed up the code by a factor of 64.

(unchecked) implementation:

bitset<100001> result;

int main() {
    int n, sum;
    cin >> n >> sum;

    result[0] = 1;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        result |= result << a;
    }
    for(int i = 1; i <= sum; i++) {
        cout << result[i];
    }
    cout << endl;
    return 0;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    AC

    got it thank you so much

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I found this implementation which is a lot faster

    Can you explain it ?

    int main (){
    
  int k, n;
  cin >> k >> n;
  vector<int> freq(n + 1);
  for (int i = 0; i < k; ++i) {
    int a;
    cin >> a;
    ++freq[a];
  }
  bitset<100001> ans;
  ans[0] = 1;
  for (int i = 1; i <= n; ++i) {
    if (freq[i]) {
      ++freq[i];
      if (freq[i] >= 4) {
        int take = freq[i] / 2 - 1;
        freq[2 * i] += take;
        freq[i] -= 2 * take;
      }
      while (--freq[i]) {
        ans |= ans << i;
      }
    }
  }
  for (int i = 1; i <= n; ++i) {
    cout << ans[i];
  }

  return 0;
}
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +18 Vote: I do not like it

      This implementation is fast when there are many repetitions in the array. The idea is that you can replace any three-tuple $$$[x, x, x]$$$ with a pair $$$[x, 2x]$$$ and the answer will be the same. Here's an example: if there are 7 fives, i.e. $$$a = [5, 5, 5, 5, 5, 5, 5]$$$, you can replace a with $$$[5, 10, 10, 10]$$$ or $$$[5, 10, 20]$$$ and the answer will be the same.

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

        Ah, you're right

        Thanks again :)

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

        This implementation is always fast. After replacing such three-tuples (replacing also any tuples that are created during the process) the sum of elements in the array is still $$$n$$$, but every element appears at most 2 times. This means that the array size is now $$$O(\sqrt{n})$$$, which brings the complexity down to $$$O(k \sqrt{n})$$$.

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

          Damn! took me time to understand why array size becomes O(root n).

          Btw final complexity should be O(nrootn) not O(krootn) but it doesn't even matter.

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

          Oh, wow, I forgot about the sum constraint! That's awesome, I've never seen such a trick before.

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

    Can you please explain, result |= result << a; what does this line do?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Basically, we want result to have bit p if you can get p as a subset sum.

      At iteration i, result stores the answer if you're allowed to take any numbers from a[0] to a[i], we extend this range iteratively.

      At the beginning of iteration i, result stores the sums if you don't take a[i]. When you do result << a, all bits are shifted by a, so bit p becomes p+a, as if you do take a[i]. Finally, result | (result << a) merges these two cases (take/don't take).

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

        Hey, can you suggest some problems with non-asymptotic optimizations using bitsets or anything else?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +7 Vote: I do not like it

          I don't have links to any problems at the moment, but I have another topic you could research, that is, SSE and AVX, all the SIMD instructions. In some cases, they can speed up your solution a lot.

          → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    There is a polynomial solution that solves an even harder version of this problem. You can get the number of ways to make $$$i$$$ for each $$$i$$$ in $$$[0, N]$$$ in $$$O(N \lg N)$$$. It is solved by taking $$$\ln$$$ of the generating function $$$\prod (1+x^{a_i})$$$, then expanding the $$$\ln$$$s using its series and collecting coefficients (which gives a nice sieve like sum computable in $$$O(N \lg N)$$$), and then taking $$$\exp$$$.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an online judge where we can try this?

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

    Sorry I don't know

    I posted this blog to solve this problem , You can try to solve it's not hard

    → Reply