888E : Maximum Subsequence

http://codeforces.com/problemset/problem/888/E

Difficulty : 4/10

I couldn't solve this problem during the contest.

this problem is not very difficult. but need some technique. 

making subset (dfs or bitmask) and find max value ( low bound search )

This problem needs meet in the middle algorithm. meet in the middle algorithm is similar to brute froce.

meet in the middle is for big size, so that brute force cant be used.

In this problem - if n=35, we can make all subset in 2^35 *O(1) time. but it is too big time complexity to solve in time.

so we first divide set into two subset, then we make all subset A and B. (need DFS or bitmask)

these subset are equivalent to all possible sum of subset. 

and then we find max value. 

now the time to use search algorithm that is called low bound.

It returns min index that greater or equal to argument.

I use nested for loop (bruteforce) to find maxvalue .

so it return time limit exceeded.....

eg) {a, b, c , d , e} 

=> divide in to two subset, {a, b, c}, {d, e} 

=> make all possible subset

+ {a, b, c, a+b, a+c, b+c, a+b+c}, {d, e, d+e}

=> plus empty set

+ { 0, a, b, c, a+b, a+c, b+c, a+b+c} , {0, d, e, d+e}

=> find max value.

Source Code:

https://github.com/ingyeoking13/algorithm/blob/master/cf/sortsearch/888E.c