Can somebody explain their solutions to problems-
1) Promotion Game 2) Count Diameters
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
Can somebody explain their solutions to problems-
1) Promotion Game 2) Count Diameters
Name |
---|
2)Count Diameters
Brute Force
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
Suppose the graph looks like this
5 3 1 3 5 5 4 5 2
Can someone please explain why this is wrong ?
I also had a stupid bug. After fixing my code gives these graphs
Oh thanks ! I understand my mistake. I was counting diameters but we should be counting subgraphs !
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..?
Facebook / LinkedIn post
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².
what is wrong in it?
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.
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
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.
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...
did anyone give today's hiring test?
Yes, did war one. What about you?
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?