iprakhar22's blog

By iprakhar22, history, 4 years ago, In English

I have questions about the following problems from one of the hiring tests of CodeNation:

Problem 1 : Given a tree, find number of subgraphs of the tree which have diameter equal to x. Print answer for all x. 1 <= x <= N. Constraints : 2 <= N <= 20

My question : Since N <= 20, can't we just try all possible sub graphs and find their diameters? I was thinking O(2^N * N) complexity should work with such small N? I also thought of some kind of a solution for a little larger N though.

Problem 2 : N men pick elements from a bag of N distinct elements. Each man pick a element one by one. If a man picks an element that is greater than all the previous picked element, then we say that this man is promoted. Each element is equi-probable to be picked. Find the expected value of promoted men. Print answer in pq^-1 mod M form. 1 <= N <= 1e5. N is the only given input.

For Example : if N = 2, then bag can contain (1, 2). All combinations are (1, 2) and (2, 1). In (1, 2) , 1 and 2 both get promoted. In (2, 1) , only 2 get promoted. Answer for N = 2 is hence 1*(1/2) + 2*(1/2) = 3/2

My question : How to approach and solve this problem? I feel like there are many ways to approach expected value problems and I got confused as to which direction to think in.

Full text and comments »

  • Vote: I like it
  • +10
  • Vote: I do not like it