### dunjen_master's blog

By dunjen_master, history, 6 months ago, ,

Can somebody explain their solutions to problems-

1) Promotion Game 2) Count Diameters

• -8

 » 6 months ago, # |   +6 2)Count Diameters SpoilerBrute Force Okay, what?Iterate over all masks from 1 to 2^n — 1. See if the set bits in the mask form a subtree. If yes, find its diameter, update its count. The check and diameter find part can be done in O(n), overall O(n * 2^n)
•  » » 6 months ago, # ^ |   0 Oh shit !!
•  » » 6 months ago, # ^ |   0 Did you submit and get the testcases right?
•  » » » 6 months ago, # ^ |   +6 Yes
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Suppose the graph looks like this 5 3 1 3 5 5 4 5 2 $k=1$ There are $4$ diameters $k=2$ There are $4$ diameters $k=3$ There are $2$ diameters $k=4$ There are $0$ diameters Can someone please explain why this is wrong ?
•  » » » 6 months ago, # ^ |   +2 I also had a stupid bug. After fixing my code gives these graphs k=1 There are 4 diameters (1,3), (3,5), (4,5), (2,5) k=2 There are 5 diameters (1,3,5), (3,5,4), (3,5,4,1), (3,5,2), (2,5,4) k=3 There are 3 diameters (1,2,3,4,5), (1,3,5,4), (1,3,5,2) k=4 There are 0 diameters
•  » » » » 6 months ago, # ^ |   0 Oh thanks ! I understand my mistake. I was counting diameters but we should be counting subgraphs !
 » 6 months ago, # | ← Rev. 3 →   +4 Promotion Game — Stirling numbers of the first kind (https://oeis.org/A000254). This gives p. q is n!
•  » » 6 months ago, # ^ |   0 And is $summation(1/i)$ for all i from 1 to n . Can anyone prove????
 » 6 months ago, # |   +3 How did you get to know about the test through some website or anything..?
•  » » 6 months ago, # ^ |   0 Facebook / LinkedIn post
 » 6 months ago, # |   +2 How did you solve the string question?
•  » » 6 months ago, # ^ |   +5 Dp with states (i,j,k) representing answer for substring from l to r with k being the last taken alphabet, as there are 26n² states and each state can be computed in constant time, the overall run time was 26n².
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 what is wrong in it? static int f(int left,int right,int last,char a[]){ if(dp[left][right][last]!=null)return dp[left][right][last]; if(left>=right)return dp[left][right][last]=0; if(a[left]!=a[right]){ return dp[left][right][last]=Math.max(f(left+1,right,last,a),f(left,right-1,last,a)); } else{ if(last!=a[left]-'a'){ int temp=2+f(left+1,right-1,a[left]-'a',a); temp=Math.max(temp,Math.max(f(left+1,right,last,a),f(left,right-1,last,a))); return dp[left][right][last]=temp; } else{ return dp[left][right][last]=Math.max(f(left+1,right,last,a),f(left,right-1,last,a)); } } } 
 » 6 months ago, # |   0 Someone please tell the approach for string problem.
 » 6 months ago, # |   +2 Had you written a brute force and searched oeis, the solution of promotion game was <10 Lines of code
•  » » 6 months ago, # ^ |   0 Yah i wrote a brute force but didn't know about oeis. I just checked 1,3,11,50,274
•  » » 6 months ago, # ^ |   -9 I expected better from CodeNation problem setters. Google-able problems are unfair and pointless really. Some people spent time solving problems while others simply googled them :/
•  » » » 6 months ago, # ^ |   +4 That wasn't exactly "Google-able", you had to build up the stirling number recurrence anyways and not everyone remembers the expansion of ith level coefficients of nth stirling number and there is nothing wrong with googling it. Our opinions might differ, ofcourse.
•  » » » » 6 months ago, # ^ |   +11 I was actually talking about this : https://math.stackexchange.com/questions/3374946/expected-number-of-balls-chosen-from-bag-i-throw-out-everything-in-the-bag-with
 » 6 months ago, # |   +1 For string question- Take two pointers let's say i and j representing the points in the string where i<=j Now if s[i] is equal to s[j] we can take them only if the last character we took is not equal to s[i], this is because of the condition that Xi =/= Xi+1. Thus along with i and j we need to remember the last character we took. Thus in this case ans= 2+ f(i+1,j-1,s[i]) If s[i] =/= s[j] we need to take maximum by increasing i or decreasing j that is, ans=max( f(i+1,j,last_ch) , f(i,j-1,last_ch) )ans=f(0,n-1,26) , ['a'-'z']=[0-25]
•  » » 6 months ago, # ^ |   0 why my above solution is wrong?
 » 6 months ago, # |   +14 Any idea when they call for further rounds and what will the cutoff in this test?
 » 6 months ago, # |   0 How many questions did you solved? I was able to solve 1st, promotion game and partial for count diameters.
•  » » 6 months ago, # ^ |   0 1st and strings.
•  » » » 6 months ago, # ^ |   0 Great.
 » 6 months ago, # |   0 if i would have more time, i would have solved all. promotion game u can find series on OEIS. counting diameters is BF by checking all graphs( i didnt solve my friend did). stirng problem was LPS dp.
 » 6 months ago, # |   0 The content was great.
 » 6 months ago, # |   0 Hey, how come some of the comments mention "googling" the problems? Isn't it forbidden to use Internet resources in this?
•  » » 6 months ago, # ^ |   0 Nope it wasn't this time.
•  » » » 6 months ago, # ^ |   +1 I remember there was a check box before starting the test on HackerRank that said only language reference and IDE with auto-completion are allowed?
 » 8 days ago, # |   +2 Can You please Provide the question statements for the same...