Блог пользователя Learner99

Автор Learner99, история, 6 лет назад, По-английски

Hello

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.

  • Проголосовать: нравится
  • +52
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Will there not be an onsite this time?

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Update: Contest starts in 1:30 hours...

»
6 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

How to solve (The Dothrakis (TDT)) ?

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

    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

  • »
    »
    6 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When will editorials be posted?