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

### dunjen_master's blog

By dunjen_master, history, 3 weeks ago, , Can somebody explain their solutions to problems-

1) Promotion Game 2) Count Diameters Comments (31)
 » 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
•  » » 3 weeks 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 !
 » 3 weeks 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².
•  » » » 3 weeks 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.