"Meet-in-the-middle technique" on Educational Codeforces Round 32, Problem E

Problem Link: Problem - E - Codeforces

The meet-in-the-middle technique is interesting, and actually, before we get into the problem E, let see another problem that is similar. (Problem based on: 4 Values whose Sum is 0)

Suppose there are four lists A, B, C, D of integer values, how can we tell if it is possible to choose a ∈ A, b ∈ B, c ∈ C, d ∈ D, such that  a + b + c + d = 0?

Let's consider the naive way, enumerating all combination of a,b,c,d. We could certainly get the right answer. But it costs a time of complexity O(n ^ 4), which is really bad when n gets large as, say, 4000.

Here comes the technique. Instead of computing the combination of four variables, we can compute two and two separately. We could compute the possible sum of a and b, which cost a time complexity of O(n ^ 2), and also the possible sum of c and d, which is also O(n ^ 2).

Let's call the list of sum of a and b List 1, and the other List 2. Then we sort List 1.

For each element k in List 2, we could use binary search to search if there is a (-k) in the List 1 in O(logn). If there is a (-k) in the List 1, then the answer to the problem is yes; otherwise, no.

This kind of bidirectional search help us reduce our time complexity from O(n ^ 4) to O(n ^ 2 · logn).

So now, what's your thoughts on problem E in this Educational Round?

Besides, there is another problem that might be helpful for you guys to practice. 
Here is the link: Chef and Subsequences 
Thanks to our friend aneesh2312 in Codeforces!

My code on this problem: Submission #32171833 - Codeforces
The official editorial on this round: Educational Codeforces Round 32 - Editorial

Feel free to comment below if you have any questions and suggestions!