A. among a[i] and k*a[i] you can have only one of them. If we sort all numbers, then it is always better to choose a[i] since a[i]*k potentially will conflict with a higher number. Some inductive argument will prove this claim. Then it takes only one scan of the sorted array and remember the banned numbers in a c++ stl set. One catch is to use 64 bit integer as k can be 10^9.
B. interesting problem. No solution yet. Here are some observations:
1. There is always a solution. Why? You can first solve a subproblem with only n-1 nodes, and then that subtree is all zero, now you have only one node with nonzero value and it is easy to see how to do the rest.
2. Order of operations do not matter. Actually, if you fix the set of operations, any permutation of ordering give you same end result.
3. Given 2, then at least one leaf node needs to be considered at most once.
No comments:
Post a Comment