Some Doubts - Codeforces

#	User	Rating
1	ecnerwala	3649
2	Benq	3581
3	orzdevinwang	3570
4	Geothermal	3569
4	cnnfls_csy	3569
6	tourist	3565
7	maroonrk	3531
8	Radewoosh	3521
9	Um_nik	3482
10	jiangly	3468

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	161
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	152
8	SecondThread	147
9	orz	146
10	pajenegod	145

Hello All,

I have some questions as doubts:

1) How can we solve problem E (The secret code) in http://codeforces.com/gym/100371 Any hints?

2) I am given an sorted array of 1000 elements, where each element can be in the range [0, 20000]. We need to consider all subsequences on the array. For every subsequence, it's power is defined as the sum of all the elements in it. We are given 1000 queries of the form "x" where i need to print the xth smallest value of the power of any subsequence of the array. Here "x" is in the range of [1, min(2^n, 10000)].

For example: Let the array be [1, 2, 100]. Then the power of subsequences sorted order are [0, 1, 2, 3, 100, 101, 102, 103]. If the query is x = 3, I need to print 2.

3) How can we solve this problem https://icpcarchive.ecs.baylor.edu/index.php?option=onlinejudge&page=show_problem&problem=2334

My approach to this problem- First of all if the graph contains a directed cycle, then the answer is 0, as a trivial case. Otherwise, consider all the cases where we can partition the groups into 2 equal halves. For this I use of mask (till 2^(2m)) and if it contains number of set bits as "m" I continue the loop. Then I consider the partition if it is valid or not i.e. if in partition 1 or 2, whether there exits a person "i" who has a dependency on person "j" but is not present in the same set. In such a case, I just add nothing. In rest of the cases, I try to find the number of topological sorts on graph in set 1 and 2 and multiply their results and finally add it to the final result. (For number of topological sorts, I used this method http://cs.stackexchange.com/questions/12713/find-the-number-of-topological-sorts-in-a-tree )

Here is a link to my code according to the above implementation https://textb.org/r/doubt-likecs/

4) How can we efficiently find the points of intersection of a line and polygon, where the polygon is not necessarily convex polygon (but the polygon is simple)?

Please help in the above problems. If possible please post the code as well.

Thanks in advance.