Link to the problem:- http://mirror.codeforces.com/problemset/problem/437/B
I read the editorial where it says we have to use greedy approach by iterating from limit to 1. I don't understand why this approach works here.Iterating from 1 to limit doesn't work here.
Can someone help me in proving why greedy approach(iterating from limit to 1) works here ?
Thanks.
If you have a certain sum, and you want to get to a smaller sum dropping some elements from the components of sum, you can find the difference, and use the following greedy strategy, since elements are powers of 2 When iterating through the elements of sum, if current element is not bigger than difference left, we will discard it and drop from difference the value of current element
For example, at pretest 1, we have n=5 and lim=5
Value of lowbit for each integer from 1 to 5 is 1 2 1 4 1, which after sorting will become 1 1 1 2 4, therefore total sum will be 9, so the difference will be 4. Iterating from the end up to beginning of the array, we will drop just 4 and write all other elements as they were, thus remaining for us sum = 5. Keeping data of this array can be done with either STL or struct
Why does greedy strategy work for powers of 2 ? If we don't have powers of 2 like 3,4,6 and want to have sum 7, then greedily picking 6 first doesn't work. So why does it work only for powers of 2?
It works for sets of powers because each number can be written as a sum of powers of that set, like powers of 2 for example.
When numbers are random, there is DP approach which will always wor