Hello friends can someone tell me how to approach this problem ??
@vijju123 @kaushal101 @mohit_negi @taran_1407 @vivek_1998299 @meooow @john_smith_3
Thanks in advance 
I don’t have any good answers, but here are some thoughts.
For a very simple but bad solution, choose a node. Call it the root of the tree, and position it at (0,0).
Look at all the immediate children of root by doing a breadth-first-search. Choose a suitably large y to satisfy the minimum distance constraints, and put the nodes at (0,y), (1,y), …, (k,y).
Continue the breadth-first-search to get the next layer. Choose an even larger Y to satisfy the distance constraints, and put the nodes at (0,Y), (1,Y), … . And repeat for each layer of the tree.
It should be clear that such a tree will satisfy the distance and 2-d embedding constraints. But the score will be very bad because the distance between root and leaves will be high.
Next step is to compress it, in a sort of zig-zag.
Root at (0,0)
Children at (d,1), (d+1,1), (d+2,1), \ldots
Grand children at (0,2), (1,2), (2,2), \ldots
Next layer at (D,3), (D+1,3), (D+2,3), \ldots
where you choose d and D to be as small as possible to satisfy the distance constraints, though they will still be about 5000. At least the nodes in the even layers will be close together.
Spend almost the full 2 seconds choosing random root nodes, calculating zig zag trees and the resulting score, and choose the best tree. You might get over 50 points for something as simple as this.
I made a number of further small improvements:
- for the nodes in the odd layers, don’t have the x-values consecutive. Reduce x where possible
- randomly permute the order of searching the children, and hence the order of nodes in each layer.
- put the root node in the center, and grow the tree in both increasing and decreasing y. I was hoping distance constraints would be less severe. Didn’t help much.
- if possible, put one of the children of the end nodes of each layer on the same layer.
- jiggle the nodes on the root and even layers to have increased x where possible. Instead of calculating Euclidean distance between every pair of nodes (which would be costly), I calculated total x-deviation from average x value and moved nodes if that would reduce. This earned me a few points.
My resulting code is certainly not pretty to read, nor very clever, but scored 73 points. (I think it was showing 100 points on Friday night, reducing to 84 just before the contest ended).
2 Likes
Thanks for your help . Haven’t tried it yet though , will give it a try soon and soon come back to this . Thanks a lot for such good explanation 