Sum in array - Codeforces

Блог пользователя Satoru

Sum in array

Автор Satoru, 5 лет назад, По-английски

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 \lt = n, k \lt = 10^5$$$

UPD2: thanks purplesyringa for the solution

array, sum, problem

Satoru
5 лет назад
18

Комментарии (18)

Написать комментарий?

bhatKa

5 лет назад, скрыть # |

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

→ Ответить

Satoru

5 лет назад, скрыть # ^ |

+11

1 <= n, k <= 1e5

→ Ответить

bhatKa

5 лет назад, скрыть # ^ |

oh cool :P :P

→ Ответить

purplesyringa

5 лет назад, скрыть # |

+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;
}

→ Ответить

Satoru

5 лет назад, скрыть # ^ |

got it thank you so much

→ Ответить

Satoru

5 лет назад, скрыть # ^ |

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;
}

→ Ответить

purplesyringa

5 лет назад, скрыть # ^ |

← 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.

→ Ответить

Satoru

5 лет назад, скрыть # ^ |

Ah, you're right

Thanks again :)

→ Ответить

-is-this-fft-

5 лет назад, скрыть # ^ |

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

→ Ответить

Perry_Prasad_Platypus

5 лет назад, скрыть # ^ |

← 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.

→ Ответить

purplesyringa

5 лет назад, скрыть # ^ |

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

→ Ответить

dca

5 лет назад, скрыть # ^ |

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

→ Ответить

purplesyringa

5 лет назад, скрыть # ^ |

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

→ Ответить

Perry_Prasad_Platypus

5 лет назад, скрыть # ^ |

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

→ Ответить

purplesyringa

5 лет назад, скрыть # ^ |

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.

→ Ответить

RezwanArefin01

5 лет назад, скрыть # ^ |

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

→ Ответить