st0ur's blog

Need Help In solving ACM ICPC regional Problem
By st0ur, history, 8 years ago, In English

I was trying to solve this question which was asked in the ACM ICPC Amritapuri regional today morning.

Click here

Both the main and the mirror contests have ended .

The only conclusion which I made is that the growth of the numbers is exponential and hence the maximum number of elements cannot exceed 60 and this is a subset sum problem.

Any hints on how to approach this problem would be appreciated.

Thanks

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

»
8 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Greedy. Start from largest pile. Pick pile i if 2p(i) >= X else don't.

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

It is the subset sum problem, but it can be solved with greedy because you know that the sum of first i piles < value of i + 1 th pile. So if target ≥ val[i + 1], you must take that item since you can't obtain that sum using all of the first i items.

→ Reply