Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### iprakhar22's blog

By iprakhar22, history, 4 weeks ago, , 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.  Comments (17)
 » For problem 2 :https://math.stackexchange.com/questions/3374946/expected-number-of-balls-chosen-from-bag-i-throw-out-everything-in-the-bag-withE(n) = 1 + (sum of E(k) for k = 1 to n-1)/n
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   Will this be right :- Let a[x] : summation of (n-1)Cr * (r+1) where r is from 0 to n-1 (n>=2 and a=1) and Answer is (a+...a[n])/n ???
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   It'll be good if you could explain why you feel this is the correct answer.It's hard for anyone to help you without knowing the intuition behind your recurrence.
•  » » Thank you.I don't understand how in the discussion forum at stackexchange they arrived at the recursion though. It would be of great help if someone is able to explain that a little clearer.
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   Sure, no problem.Initially you have N balls in the bag.With 1/N probability I can pick the smallest ball. Similarly for the 2nd smallest ball there is 1/N chance and so on.E(N) = 1/N*(1 + E(N-1)) + 1/N*(1 + E(N-2)) + .. + 1/N*(1+E(0))If Initially I picked the smallest ball I'll be left with N-1 useful balls same way if I picked the largest , I'll be left with 0 useful balls.That +1 everywhere is because of the person getting promoted because of the current ball draw.x1/N represents the chance of a particular outcome i.e. chance of picking a particular ball.Hope this helps.
•  » » » » Thank you
 » can u share link to similiar problem they had asked about the string problem,where we had to find longest even palindromic subsequence i guess,i need to practice that kind of problem??