EugeneJudo's blog

By EugeneJudo, history, 2 months 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

»
2 months 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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. For anyone who wants a bigger hint without the full solution, consider how if we know $$$X'$$$ has every subset sum up to $$$k$$$ but not $$$k+1$$$, then what do we know when we add a new element to $$$X'$$$?