MINIKILL - ENIGMA! EDITORIAL PLEASE!

what is the approach being the ques named Corrouption in Freedonia( MINIKILL)

3 Likes

I got WA.
My approach:
The value for a vertex is the sum of its children
If the vertex contains at least one child such that its branch has only 1 path in it, then subtract 1 from its value
All leaves are 1

I used the logic that we have two cases -whether to cut a particular node on which we are right now or not, and find the answer for both these cases for each node. When a node is not cut, the number of components we currently have will be always 1. Similarly there will be two cases for each of its children too. So if we want to cut a particular node, atleast one of the child nodes should also be cut. So I found the max value of a child, when cut will give us the maximum amount of different components. And for the other children we can use the max value of both cases (cut or not cut).

u have any good TC ??

1 Like

Your logic is completely correct. There might be some flaws in your code.
My logic was the same as yours and this gives AC :
https://www.codechef.com/viewsolution/28873175

Testcase-1:
21
1 2
1 3
2 7
2 13
2 14
2 15
3 5
3 6
3 4
6 16
6 17
7 8
7 9
7 10
7 11
7 12
5 18
5 19
5 20
5 21

Test-case-2:
10
1 2
1 3
1 4
2 5
5 6
3 7
7 8
4 9
9 10

Hope it helps

3 Likes

My Submission Link https://www.codechef.com/viewsolution/28872164
Will u pls tell me what i m missing?
your Tcâ€™s are also working in my code:

1 Like

I tried but canâ€™t find anything wrong till now. I have seen most people use dfs/bfs in tree-dp-problems, I use some weird method of traversal in which I start from leaves and eventually reach the root and it seems to work fine most of the times

3 Likes

When one gets to 6 star, are they supposed to write 400 line solutions

1 Like

Stop it

pls if anyone has good Testcase so pls post it here :

9
1 2
2 4
2 3
2 5
1 6
6 7
1 8
8 9
Ans - 4

11
1 2
2 4
2 3
2 5
1 6
6 7
1 8
8 9
6 10
6 11
Ans - 5
I used these two to debug my code.

1 Like

Thereâ€™s a huge difference between (6-star coders) and (6-star coders who only do long challenges)

25 Likes

One more important testcase I feel is the one which has many straight-paths in a tree.

1 Like

ankit_betch you savage XD XD

4 Likes

can u explain what u did??and logic too

1 Like

@naman_9899
Nhi yaar. Jaane do.Long challenge waalon ko kaha kuch coding aata hai . Sab long challenge waalein to stupid hi hai according to some coding-immortals here

1 Like

are brooâ€¦ignore such foolsâ€¦meko pta h 6 star phuchna is not a cakewalk,i takes sleepless nightâ€¦apart from thisâ€¦soltuion btaa naaâ€¦i was thinking of the diameter or something like that for the quesâ€¦

3 Likes

just tell me the approach:slightly_smiling_face:

1 Like

Haan bhaiâ€¦toh this is a very famous(self-created) trick , you gotta memorize it , ok ?

In tree-dp questions(most of them), you start from leaves and traverse till the root like this :-

Lets calculate answer for this :-

And this:-

If we join them both, answer is this:-

In short, from the bottom, go up and keep joining all the sums till you reach the root !

4 Likes