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$$$

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

1 <= n, k <= 1e5

oh cool :P :P

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:

AC

got it thank you so much

I found this implementation which is a lot faster

Can you explain 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.

Ah, you're right

Thanks again :)

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})$$$.

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.

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

Can you please explain,

`result |= result << a;`

what does this line do?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 youdotake`a[i]`

. Finally,`result | (result << a)`

merges these two cases (take/don't take).Hey, can you suggest some problems with non-asymptotic optimizations using bitsets or anything else?

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.

There is a polynomial solution that solves an even harder version of this problem. You can get

the number of waysto 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$$$.Is there an online judge where we can try this?

Sorry I don't know

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