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.

• +10

 » 4 weeks ago, # |   +12 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 →   0 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]=1) and Answer is (a[1]+...a[n])/n ???
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 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.
•  » » 4 weeks ago, # ^ |   0 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 →   0 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.
•  » » » » 4 weeks ago, # ^ |   0 Thank you
 » 4 weeks ago, # |   +3 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??
•  » » 4 weeks ago, # ^ |   0 Link 1And Link 2
 » 4 weeks ago, # |   +3 Is there any chances of getting a call after solving only 2 problems ?
•  » » 4 weeks ago, # ^ |   0 Not to break your hopes but I'm guessing a lot of people solved all 4 problems. Still, I'd be happy if you get selected :)
•  » » » 4 weeks ago, # ^ |   +11 Haha !! Never mind. I know that I haven't performed well this time but have certainly improved a lot from the last Hiring Contest(Codeagon). Will expect to improve afterwards. Thanks anyways :)
•  » » » » 4 weeks ago, # ^ |   0 That's the spirit brother!
 » 4 weeks ago, # | ← Rev. 2 →   +5 For problem 1: I think it should work, but you have to drop cases which would compose disconnected tree graph, by this you will reduce runtime a lot.
•  » » 4 weeks ago, # ^ |   0 Thank you. I believe some people did submit the brute force solution and got it right without any optimizations even.
•  » » » 4 weeks ago, # ^ |   0 Yup, bruteforce solution was passing all the test cases without any optimization.
 » 4 weeks ago, # |   +3 For the second problem formula for promoted men is f(n)=n!/2+n*(f(n-1)), where n>1,f(1)=1; so p=f(n) && q=n!
 » 4 weeks ago, # |   +4 Did anyone receive a call for an interview? If yes then how many did they solve?