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, 3 weeks 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.

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

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it
  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 ???

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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??

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Is there any chances of getting a call after solving only 2 problems ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 :)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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 :)

»
3 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you. I believe some people did submit the brute force solution and got it right without any optimizations even.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yup, bruteforce solution was passing all the test cases without any optimization.

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Did anyone receive a call for an interview?
If yes then how many did they solve?