SUBMEXS - Editorial

editorial
, , , , , ,
2

great contest btw

5 Likes
3

Can anyone help me what i have done wrong? My approach has been
For each child of root
1)do dfs and during dfs calculate the subtree size of each node and also find out the bottommost node in that subtree
2)traverse in bottom up manner from the bottommost node of each subtree till that subtree root and at each step add the subtree size to a variable sum
3)Add n=no.of vertices to sum.
4)find maximum of all sum that is obtained by repeating the steps 1 to 3 for each child of 1
Link to my solution
https://www.codechef.com/viewsolution/39244783
Thanks in advance…

4
  1. count the subtree size of eah node.
  2. insert the pairs of {subtree size ,node} and sort them for each node descending order.
    3.start adding the mex from root and move to the child node that has grater subtree-size until we reach leaf node.
    what’s wrong with approach?
    Link-
    CodeChef: Practical coding for everyone
5

Hi, can we try to find out wrong in each other’s solution? I find out yours…you find out mine

6

okay,I’ll try!

7

Hey, i have found out yours…
try this input
n=13
1 2 3 4 1 6 6 6 6 6 6 6 —> this is the input sequence …output should be 23 yours is 22

3 Likes
8

@bootcoder

9

I did dp on trees.

void dfs(ll u, ll p)
{
    par[u] = p;
    cnt[u] = 1;
    for (int v : adj[u])
    {
        if (v != p)
        {
            dfs(v, u);
            cnt[u] += cnt[v];
        }
    }
    if (adj[u].size() == 1 && u != 1) dp[u] = 1;
    for (int v : adj[u])
        if (v != p)
            ckmax(dp[u], dp[v]+cnt[u]);
}

dp_i is the answer for the subtree of i including i.
So dp_u = \text{max}(dp_v) \ + \ \text{size}(u)

5 Likes
10

thanks!

11

Hello, can anyone tell me what I’m doing wrong?
My solution
What the code is doing is that it calculates how many vertices there are in the subtree of each node and then it finds the vertex with maximum depth and does up the tree from that vertex until we reach vertex 1
At every vertex that we visit, we add (number of vertices in subtree) to the answer
Why I thought this was correct:
1
/\
2 3
/\
4 5
If we assign 0 to 5 then 1 to 4 and then 2 to 2 then 3 to 3 and then 4 to 1 then answer will be (1 + 3 + 5) = 9
Please help me ;-;

1 Like
12

My solution is
1.Calculate maximum size subtree for every level ,Let it be maxSiz[i] for level i , for e.g. maxSiz[1]=n 2. Then sum all the maxSiz[i] for all the levels,
Result is answer.

But it is giving wrong answer, i can’t think of any test case that fails, please point out the mistake, or just provide a test case.

My solution

13

When i submitted in cpp : CodeChef: Practical coding for everyone it passed but earlier i tried to submit in python the same code :: CodeChef: Practical coding for everyone i got runtime error i dont know why
please help

14

Try this testcase, ur code is giving wrong ans with this testcase.

3 Likes
15

how much time ur solution took? execution time?
I used dfs twice it took 0.20 secs.
https://www.codechef.com/viewsolution/39250093

1 Like
16

u should assign 1 to the leaf nodes and then calculate subtree size.
This is my submission link check this out
https://www.codechef.com/viewsolution/39250093

2 Likes
17

0.08s.

2 Likes
18

nice I m studying ur solution

1 Like
19

There’s some unnecessary stuff like par that I forgot to remove, so don’t confuse yourself.

2 Likes
20

use dfs twice

1 Like
21

Can you help me how the answer is 23.