Operations on Tree - Leetcode Biweekly Contest - 1993 - Python

0:00 - Read the problem
1:40 - Drawing Explanation
4:55 - Coding Explanation

leetcode 1993

#tree #operation #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[meeradad]

Actually, quite elegant - very concise code. It is great that everything is done as lists/arrays, instead of linked list traversals.

[halahmilksheikh]

3:45 me when solving an easy question first try

[heejoojin]

I really appreciate your video!!! Can you please also do one on "Remove K Digits"?

[igorku]

This is a one convoluted task description. While big thanks to NeedCode for an explanation (I did not get it to the end in any case), I wonder what is the educational value for it? Does it help with an abstract thinking?

[NiteshGarg-udvy]

In the upgrade code, before you return False value by checking if there is any child that is locked, shouldn't the operation to all of them be performed only after confirming that upgrade is true? Otherwise even on not having the conditions satisfied, the person will unlock all the children node.

[Lucan_]

Sir today's weekly contest, problem 2. I was getting TLE. Was able to solve just 2

[karthik-varma-]

i have spent more than 2hrs but not able to implement upgarde() function

[thegodofblunder]

Hey man, can you upload the much hyped logN solution

[mayurgarud]

Hello sir, can you solve this problem? /please Give me hint to solve this one

Problem:
The parcel section of the Head Post Office is in a mess. The parcels that need to be loaded to the vans have been lined up in a row in an arbitrary order of weights. The Head Post Master wants them to be sorted in the increasing order of the weights of the parcels, with one exception. He wants the heaviest (and presumably the most valuable) parcel kept nearest his office.

You and your friend try to sort these boxes and you decide to sort them by interchanging two boxes at a time. Such an interchange needs effort equals to the product of the weights of the two boxes.

The objective is to reposition the boxes as required with minimum effort.

N<=50

Weights <= 1000

Example 1

Input

5 2

20 50 30 80 70

Output

3600

Explanation

There are 5 boxes (N=5) and the heaviest box must be in position 2 (k=2). If we look at the final order (sorted, with the heaviest at position 2), it should be 20 80 30 50 70. If we look at this, we notice that only the 50 and the 80 parcels need to be exchanged. As this takes effort of the product of the weights, the effort is 4000.

Further reduction can be obtained if we use the smallest package (20) as an intermediary. If we exchange 20 with 50 (effort 1000), then with 80 (effort 1600) and back with 50 again (effort 1000), the effect is the same, with a total effort of 3600 (less th an the effort obtained by the direct move)an the effort

The results after the optimal sequence of exchanges are

50 20 30 80 70

50 80 30 20 70

20 80 30 80 70

As this takes an effort of 3600, the output is 3600.

Example 2

Input

6 3

30 20 40 80 70 60

Output

7600

Explanation

There are 6 parcels, and the heaviest should be at position 3. Hence the final order needs to be 20 30 80 40 60 70. If we look at the initial position, we see that 20 and 30 need to be exchanged (effort 600), 40 and 80 need to be exchanged (effort 3200) and 60 and 70 need to be exchanged (effort 4200). Hence the total effort is 600+3200+4200=8000.

If we use the same approach as in Example 1, we get the following efforts

(600) 20 30 40 80 70 60

(3200) 20 30 80 40 70 60

(1200) 60 30 80 40 70 20

(1400) 60 30 80 40 20 70

(1200) 20 30 80 40 60 70

A total effort of 7600 is obtained rather than an effort of 8000, which is the output.

[sagekikitchen]

Please upload solution for the last problem of today's contest

[codetrooper]

you losed all my respecct by just showing the code and showing the least amount of explanan=ition for how we are gonna create the children array