Hello everyone!
We would like to invite you to participate in CodeMutants Revisited. We are reconducting this contest as the last contest faced technical issues from the server side. This contest will be held on CodeChef on 27th February (Wednesday) from 9:00 PM IST.
There will be 7 questions covering various topics. Problems may not be difficulty-wise sorted. So power up your brain and be ready to conquer.
Prizes: 250 Laddus to Top 10 ( Top 5 Global and Top 5 Indians ). Cash Prize of Rs. 3000 distributed among Top 3 Indian Participants.
Time: 27th February, 9 PM to 12 AM.
Contest Link: CodeMutants Revisited
Note: For Indian's to be eligible for Cash Prize, one must fill the below-given Google form:
https://goo.gl/forms/cwyaUjqDLqMpHy7y1
Happy Coding :)
Team CodeMutants.
Will there not be an onsite this time?
No, There won't be any onsite this time.
Update: Contest starts in 1:30 hours...
How to solve (The Dothrakis (TDT)) ?
TDT is just standard modification of Barricades problem from Looking for a challenge book. You can do dp[x][y] which denotes maximum value of a component in subtree of x containing y nodes including x. Now, it is trivial that complexity to compute this dp is less than equal to O(n^3). But if you iterate only over current size of subtree then it can be computed in O(n^2). You can get it that you will only iterate number of times equal to number of times two nodes's lca is x while computing dp for x. So, it is O(n^2). Sorry if I was unclear. My code- LINK
Firstly, without loss of generality we can assume the tree to be rooted at 1. Let dp[i][j] be the maximum sum(which in turn will lead to maximum mean) that can be obtained by considering the j-connected component in the subtree of node i which includes node i.Now for a node src, if I have the DP table filled for all of its children, how can I fill up the DP table for node src?
Here is the code for your reference. You need to run it for all children u of node src.
Lastly, do not forget to take floor value at the end.
When will editorials be posted?