Lazy Squirrel Learns Tough Programming

Computer Science Level 4

The length of each edge in the binary tree is given as a real number element of an array/list: $a=\left[a[0],a[1],\ldots,a[2^{n+1}-2]\right].$ At each of the $2^n$ leaves, there is an acorn. The squirrel is lazy and wants to travel the minimum possible distance to get 1 acorn, so the squirrel learns to program. If $a$ is given by the list in this file , what is the minimum distance the squirrel has to walk?

The answer is 317.

1 solution

Eli Ross Staff
May 2, 2016

Relevant wiki: Recursive Backtracking

Consider the parent vertices of the leaves (the level in the tree just above the acorns). Once the squirrel gets to one of these, he will just pick the shortest of the two paths to the acorn; the other acorn is irrelevant.

Using this same logic, we can work up the entire tree, keeping track of the "best case to acorn" from any given vertex downward. Here's a simple example for illustration:

There are many nice ways to implement this recursion on the given list. Here's one (fairly inefficient and contrived) implementation; what's yours? What is the best asymptotic runtime you can achieve?

b = []
for i in range(0,11):
    b.append(a[2**i-1:2**(i+1)-1])

for j in range(1,11):
    i = 10-j
    for x in range(0,len(b[i])):
        b[i][x] += min(b[i+1][2*x],b[i+1][2*x+1])

print b[0]

I think correct answer is 397, you didn't consider the length of root node which is 80. You need to traverse length 80 in order to reach second level nodes.

Siva Bathula - 5 years ago

@Siva Bathula

The 80 is actually being correctly accounted for. In the second for loop, when $j = 10,$ $i = 10-10 = 0.$ Then, the nested for loop computes $b[0][0]$ += $\min\{b[1][0],b[1][1]\}.$ Note that it is +=, not =, so it is adding $b[0][0] = 80$ to the minimum of the two nodes below it.

If you want to convince yourself further, try changing the first element in the original list to $79$ and you'll see that this code returns $316.$

Eli Ross Staff - 5 years ago

I was wrong again. It's 317. I was actually accounting for 80 twice :)

Siva Bathula - 5 years ago

Lazy Squirrel Learns Tough Programming

The answer is 317.

1 solution

0 pending reports