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

Автор st0ur, история, 8 лет назад, По-английски

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

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

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

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

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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.