### dunjen_master's blog

By dunjen_master, history, 15 months ago, Can somebody explain their solutions to problems-

1) Promotion Game 2) Count Diameters Comments (39)
 » 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)
•  » » Oh shit !!
•  » » Did you submit and get the testcases right?
•  » » » Yes
•  » » 15 months ago, # ^ | ← Rev. 2 →   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 ?
•  » » » 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
•  » » » » Oh thanks ! I understand my mistake. I was counting diameters but we should be counting subgraphs !
 » 15 months ago, # | ← Rev. 3 →   Promotion Game — Stirling numbers of the first kind (https://oeis.org/A000254). This gives p. q is n!
•  » » And is $summation(1/i)$ for all i from 1 to n . Can anyone prove????
 » How did you get to know about the test through some website or anything..?
 » How did you solve the string question?
•  » » 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².
•  » » » 15 months ago, # ^ | ← Rev. 2 →   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)); } } } 
 » Someone please tell the approach for string problem.
 » Had you written a brute force and searched oeis, the solution of promotion game was <10 Lines of code
•  » » Yah i wrote a brute force but didn't know about oeis. I just checked 1,3,11,50,274
•  » » 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 :/
•  » » » 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.
 » 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]
•  » » why my above solution is wrong?
 » Any idea when they call for further rounds and what will the cutoff in this test?
 » How many questions did you solved? I was able to solve 1st, promotion game and partial for count diameters.
•  » » 1st and strings.
•  » » » Great.
 » 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.
 » The content was great.
 » Hey, how come some of the comments mention "googling" the problems? Isn't it forbidden to use Internet resources in this?
•  » » Nope it wasn't this time.
•  » » » 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?
 » Can You please Provide the question statements for the same...
 » To view more question of CodeNation CNIL Test 2020 See link https://codeforcompany.blogspot.com/2020/08/codenation-cnil-recruitment-test-2020.html?m=1
 » did anyone give today's hiring test?
•  » » Yes, did war one. What about you?
•  » » » 9 months ago, # ^ | ← Rev. 3 →   I did the cubes one, and I passed 12 test cases/15 in the metrices problem. What was your approach for War?
•  » » » » I was only shown 1 sample test and 4 hidden tests which my solution passed for B. How were you able to see the 12/15 thing? Btw I used binary search to find the answer in B and used prefix array in the check function. What should be the cutoff according to you?
•  » » » » » Oh, sorry. I meant the 3rd one. Metrices. I passed 12/15 there. I think, if partial was allowed, 2/3 should get you selected
•  » » » » what is the formula for cubes question?