Can somebody explain their solutions to problems-

1) Promotion Game 2) Count Diameters

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

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | tourist | 3404 |

3 | TLE | 3356 |

4 | apiadu | 3351 |

5 | mnbvmar | 3281 |

6 | LHiC | 3276 |

7 | Um_nik | 3268 |

8 | 300iq | 3267 |

9 | yosupo | 3249 |

10 | ainta | 3226 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 190 |

2 | antontrygubO_o | 186 |

3 | tourist | 182 |

4 | Radewoosh | 169 |

5 | vovuh | 167 |

6 | pikmike | 166 |

7 | ko_osaga | 161 |

8 | Um_nik | 160 |

9 | Petr | 155 |

10 | McDic | 153 |

Can somebody explain their solutions to problems-

1) Promotion Game 2) Count Diameters

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/20/2020 00:01:21 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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?

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.

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.

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?