I didn’t want to ask during the contest, but I felt like my solution was correct, yet still got WA. I haven’t seen an editorial for the problem yet so I have no way to verify my solution.
So I’d like to ask for a test case that my method fails.
My Approach
I picked a root node in the tree (Usually 1, but I tried others) and calculated the distance to each node from there, using Breath First Search/Dijkstra.
I then grouped the nodes into 4 groups with each node going into the group number dist_from_root%4
If group(0) + group(2) == group(1) + group(3), Then the answer is 1 and the sets are chosen in the same way
If they not equal I moved only nodes from one of the groups across to the other side until they were equal, but making the answer 2.
Solution Code
https://www.codechef.com/viewsolution/22349636
Please help me find a failed test case, I’ve tried to find my error but could not.
I haven’t been able to fully understand your solution however I was doing the same thing (except I had 2 groups) and that approach would fail when I move one node to another group and all the nodes in its subtree change groups as well.
This was one of the expected incorrect solutions, which fails on some random trees because while moving vertices from groups, it always ends up making the H_2 disconnected. Intended solution is much simpler and different, and is discussed in editorial.
There may be some way to move vertices, but most ways have some flaws, failing on certain trees.
I used 4 groups to avoid that from happening, with 4 groups if I’m moving nodes from say group 3 all nodes 2 away (in group 1) won’t move.
I think I avoided that by using 4 groups, but I must have missed something. I’d still like an example though.
I haven’t seen the editorial for this.
Editorial would be out anytime now.
As for example, it is easy to write a solution tester. Generate random trees and run ur solution and test it.
Hint For making tester. First try dividing nodes into groups on basis of parity. If groups are of same size, k = 1. Otherwise, k = 2 suffices. Read the partitions generated by solution, find all pairs of nodes and check if the graphs are connected.
@taran_1407 isn’t this solution doing the same thing (which u said is wrong) but it got 75 pts.
There are many ways to approach this problem. It is neither possible nor feasible to find countercases for all possible solutions. Maybe this solution fails on some small tree but fails on large trees.
The more I speak about it, the more I’m convinced that my solution is correct, Is it possible to get access to the referee code and/or test cases? I just want to know where I went wrong
You could add a check function in your own code, store the spanning tree and assert that it is correct.
The solution you mentioned, was my first idea when i saw the problem for the first time. I too was convinced, but there are many cases to be considered in it, and trust me, the solution in editorial is much simpler. As for test cases, it is not possible to access test cases.
Maybe this solution fails on some small tree but fails on large trees.
Hmm. I think you meant something else 
1 Like
Test case
1
6
1 2
2 3
2 4
2 5
5 6
gives output
2
1 3 4
2 5 6
But the output is incorrect because the shortest jump from 6 to one of {1,3,4} is three steps.
1 Like