### SuhaibSawalha1's blog

By SuhaibSawalha1, 5 weeks ago,

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 imachug for the solution

• +42

 » 5 weeks ago, # |   0 Pretty Standard DP Problem I think Surf SUBSET SUM Problem, N*K dp table can do the trick for you
•  » » 5 weeks ago, # ^ |   +11 1 <= n, k <= 1e5
•  » » » 5 weeks ago, # ^ |   +6 oh cool :P :P
 » 5 weeks ago, # |   +26 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; } 
•  » » 5 weeks ago, # ^ |   0 ACgot it thank you so much
•  » » 5 weeks ago, # ^ |   +8 I found this implementation which is a lot fasterCan you explain it ? int main (){ int k, n; cin >> k >> n; vector 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; } 
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +18 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.
•  » » » » 5 weeks ago, # ^ |   0 Ah, you're right Thanks again :)
•  » » » » 5 weeks ago, # ^ |   +23 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})$.
•  » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   -8 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.
•  » » » » » 5 weeks ago, # ^ |   0 Oh, wow, I forgot about the sum constraint! That's awesome, I've never seen such a trick before.
•  » » 5 weeks ago, # ^ |   0 Can you please explain, result |= result << a; what does this line do?
•  » » » 5 weeks ago, # ^ |   +7 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).
•  » » » » 5 weeks ago, # ^ |   0 Hey, can you suggest some problems with non-asymptotic optimizations using bitsets or anything else?
•  » » » » » 5 weeks ago, # ^ |   +7 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.
•  » » 5 weeks ago, # ^ |   +3 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$.
 » 5 weeks ago, # |   0 Is there an online judge where we can try this?
•  » » 5 weeks ago, # ^ |   0 Sorry I don't know I posted this blog to solve this problem , You can try to solve it's not hard