problem link. I thought of finding the divine number as : first take any vertex and connect all other vertex to that(in a star like manner). Now, untill this vertex is not included in considered set of r[i] we are done but when we include this we need to have another vertex which is connected to all and similarly we have to have atleast ‘r[i]+1’ vertex which are connected to all.
And after finding that number I used in-out dp to find the required answer.
Can someone suggest me where am I going wrong? OR provide a valid proof that the way I am finding the divine number is optimal in all the cases?
And when will the problem will be available for practice?
Divine number as I understood : It is written that for every Ri cities there exist a city that is connected to all of them. And for the 2nd test case : For every pair of city there exist atleast one other city which is connected to all of the selected cities directly.
Dp states : once the divine numbers are built we can find the value of the minimum path length from all the nodes considering only it’s subtree i.e. path length when we go to all the available cities in the plan that are present in the sub-tree of the current node. Apart from this I also have calculated bck[i] for all the nodes which denotes how much distance we have to travel more if we want to come back to the root again (important info when we have to cover rest of the cities outside the current sub-tree). For calculating this I sort all the values for all the branches and just select the maximum (as for minimum length to visit all the nodes we have to go to all the branches one by one and we have return from all of them except from the last one which we may choose to be the longest one.).
Similarly for the out_States I used the in_States info. and just calculate the same two things out[i] and bck_[i] . If you want I can explain it more.
PS : I don’t know whether the approach or the way I calculate the divine number is correct or not as my code doesn’t ACed at contest time due to some bugs which I fixed after the contest. Even though I am not sure whether it will pass or not. So, if you get correct solution or a valid proof for divine number then plz plz explain.
UPD : I didn’t get AC.
[1]. If you got the solution then please share.
Thanks!
[1]: https://www.codechef.com/viewsolution/20974276
I mean in question it was written that for every Ri set,1 must exist which is connected to all,but seeing sample tc for city 2,it clearly violates(there existed 2 vertices with degree 2)