SUBMEXS - Editorial

editorial
, , , , , ,
43

Wow thank you very much that solved my problem. I was more focused on finding a corner case. Indeed it was a overflow case.

44

It is not optimal to greedily choose the next node with maximum subtree size
because we donā€™t know what will be the subtree sizes of coming nodes.
example:
1
10
1 1 3 3 3 3 2 8 9
Draw the tree for this testcase ,you will see that according to your logic we went to the node having max subtree size from root but it was optimal to go to the node with smaller subtree size.(Therefore we have to check all possibilities)
Here is my commented AC code:
https://www.codechef.com/viewsolution/39256390

3 Likes
46

https://www.codechef.com/viewsolution/39258537

Please help me out. I am getting RE in 2 out of 5 test cases. In the rest 3 I am getting AC verdict.

47

I think bottom most approach wonā€™t work all the time

48

https://www.codechef.com/viewsolution/39257498
Can anyone tell me , what am I doing wrong, I am getting TLE on 4 test cases and AC in one .

49

thanks a lot bhai

50

Ans= 1+2+3+4+13 = 23
Assign (0, 1, 2, 3, 12) to the nodes (5,4,3,2,1) respectively.

51
52

My logic is wrongā€¦I have found my mistake

53

Yes,bottom most approach would work ,it would get tlebut in my case I have done logical errors.

54

Can someone help me out with yesterdayā€™s Lunchtime submexes question ? Canā€™t seem to figure out where Iā€™m going wrong.

Question link CodeChef: Practical coding for everyone

My solution link : CodeChef: Practical coding for everyone

I saw the video editorial of Codechefā€™s official channel on YouTube and Iā€™m getting proper output for the test inputs they have used
Test Input :
3
9
1 1 2 2 3 4 5 6
9
1 1 2 2 3 6 7 8
11
1 2 2 2 2 2 2 1 9 10
Output(which is correct) that Iā€™m getting
17
24
19

Approach that Iā€™ve used :
1)Store the tree in an adjacency list and also store the number of nodes every leaf node has in an array.
2)Initialise count variable to 0,
Traverse root node, increment count by (number of children of that node +1) and go to the child node with highest number of children and keep doing this till leaf node is reached

If you want you can uncomment all the stuff that Iā€™ve commented in my code and try running it in your pc, it will better describe what exactly the code is doing.

Any help is appreciated

1 Like
56

Hey Brother,
Your code is failing for the following test case:

Input:

1
10
1 1 1 4 2 2 3 3 5

Expected Output - 16
Your output - 14

This is due to fact that considering maximum number of nodes in a subtree for calculating MEX is wrong. You have to consider height too.

Draw the tree on pen and paper and dry run it.You will get what i just told. :slightly_smiling_face:

1 Like
57

Brother,Your simple code explains the approach itself.

I watched the editorial video which made me more confused than i was before.

After looking at your code,i got to know where i went wrong and how the correct approach is really working!

Good Job!

1 Like
58

Finally I understood it. Thank you for you help bud, really appreciate it. :innocent:

1 Like
59

I know right, even i felt the editorial was a little confusing :sweat_smile:

1 Like
60

Video is focussed more on formality.
The part where explaination was needed,There was no explaination.

1 Like
61

Thanks a lot man but I m too weak in codeforces :neutral_face:

1 Like
62

Brother, its about about how to write a user friendly code so that others can understand. :slightly_smiling_face:

1 Like
63

:grinning:

1 Like
65

Nice and user friendly code!
Good job!

1 Like