You are not logged in. Please login at www.codechef.com to post your questions!

×

Can anyone help me with Embedding a Tree from March Challenge 2018 DIV 2 Contest?

0
1

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 :)

asked 15 Mar '18, 01:11

harrypotter0's gravatar image

4★harrypotter0
318110
accept rate: 1%

edited 15 Mar '18, 01:11


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).

link

answered 15 Mar '18, 03:56

john_smith_3's gravatar image

6★john_smith_3
60517
accept rate: 26%

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 :)

(24 Mar '18, 22:17) harrypotter04★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,738
×2,658
×2,475
×1,424

question asked: 15 Mar '18, 01:11

question was seen: 287 times

last updated: 24 Mar '18, 22:17