I was trying to solve this question which was asked in the ACM ICPC Amritapuri regional today morning.
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
Greedy. Start from largest pile. Pick pile i if 2p(i) >= X else don't.
Thanks :)
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.
Thanks :)