Some Doubts

Revision en2, by likecs, 2016-09-12 21:23:50

Hello All,

I have some questions as doubts:

1) How can we solve problem E (The secret code) in http://codeforces.net/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.

Tags doubts, maths, computational geometry, probability, graphs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English likecs 2016-09-12 21:23:50 164
en1 English likecs 2016-09-12 21:20:22 1925 Initial revision (published)