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

Автор EugeneJudo, история, 3 года назад, По-английски

I'm trying to solve https://cses.fi/problemset/task/2183, and I'm completely baffled since every approach I come up with looks to violate the subset sum problem being NP complete for finding a specific subset that sums to N. I'd appreciate a nudge in the right direction.

My observations so far:

  • If $$$1,2,4,...,2^i$$$ are in $$$X$$$, then $$$MEX >= 2^{i+1}$$$

  • $$$MEX <= 1 + (x_1 + \ldots + x_n)$$$

  • $$$MEX = 1$$$ if $$$\min(X) > 1$$$

None of these observations seem sufficient in general.

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

Sort the array.

Edit. Oops I guess I should not give too much details for hints. You can check full solution on edit history.