I'm trying to solve the following problems here:

In the X world, companies have a hierarchical structure to form a large binary tree network (can be assumed to be a perfect binary tree). Thus every company has two sub companies as their children with the root as company X. The total number of companies in the structure is N. The wealth of each company follow the same general trend and doubles after every month. Also after every year, half of the wealth is distributed to the two child companies (i.e. one fourth to each) if they exist (i.e. the leaf node companies do not distribute their wealth). Given the initial wealth of each of the N companies, you want to determine the final wealth of each company after m months. (A perfect binary tree is a special tree such that all leaf nodes are at the maximum depth of the tree, and the tree is completely filled with no gaps.)

(a) Design an algorithm in O(n^3 log(m)) complexity to find the final wealth of each company after m months.

To achieve the above mentioned constraints, I'm thinking it'll be great idea to introduce dynamic programming with memoisation.

The dp array would be of three dimensions N*m*2 with dp[i][j][k] representing the wealth of company i after j months with k denoting whether the wealth has been distributed in the last year.

In the recursive step, I think while traversing the tree from the leaf to the root, and for every non-leaf node, calculate its wealth after j months using its children's wealth values from the previous month. This involves considering two cases: wealth distribution and wealth doubling.

a. If the wealth was not distributed in the last year (k = 0), calculate the wealth as the sum of the children's wealth (dp[i][j-1][0] + dp[i][j-1][1]) b. If the wealth was distributed in the last year (k = 1), calculate the wealth as half of the sum of the children's wealth ((dp[i][j-1][0] + dp[i][j-1][1]) / 2)

Pseudocode for the same:

function calculateFinalWealth(initial_wealth[], m):
    N = length(initial_wealth)
    Initialize dp[N][m+1][2] array
    for i = 0 to N-1:
        dp[i][0][0] = initial_wealth[i]
    for j = 1 to m:
        for i = 0 to N-1:
            if i is a non-leaf node:
                dp[i][j][0] = dp[i][j-1][0] * 2
                dp[i][j][1] = (dp[i][j-1][0] + dp[i][j-1][1]) / 2
    return dp

(b) Analyze the time complexity of your algorithm and briefly argue about the correctness of your solution.

I need help about how to discuss the correctness argument in this case apart from what I've already discussed above.

(c) Consider the case of a single company (i.e. only root) in the tree. Give a constant time solution to find the final wealth after m months.

Since it is said the wealth of the company doubles after every m months, I think it should be safe to assume Final_Wealth = Initial_Wealth * 2^m

I just need to verify that this is indeed what I'm thinking.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.