When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

EugeneJudo's blog

By EugeneJudo, history, 3 years ago, In English

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.

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

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

Sort the array.

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