SUBMEXS - Editorial

editorial
, , , , , ,
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
66

Got AC.
Time 0.13 sec.

Approach :
Calculate and store subtree size of each node in a vector called subtree[i].
While backtraking at each node return subtree[node] + max(value returned by below subtree)…

Please see solution for clear understanding …
https://www.codechef.com/viewsolution/39266674

Thanks

67

Link u have given does not lead to your solution. This is correct link

68

If anybody is facing difficulty in understanding the reason for the solution.
Check my solution, i have added comments to explain the reason.

Solution-Click Here

Draw tree on a paper,it helps in getting a better understanding!

1 Like
69

Take a look, I used the same approach but

70

Thxx