Learner99's blog

CodeMutants Revisited

By Learner99, history, 5 years ago, In English

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.

  • Vote: I like it
  • +52
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Will there not be an onsite this time?

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +20 Vote: I do not like it

How to solve (The Dothrakis (TDT)) ?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +11 Vote: I do not like it

    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

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will editorials be posted?

→ Reply