Please help me with DEMTREE (practice easy)

Gosh, that was boring :slight_smile: Hats off to everyone who managed to complete this plus other problems in less than 3 hours!!

Here’s my solution - AC in 0.07 seconds. It’s missing the high-level approach, but the source is heavily-commented and you should be able to piece it together :slight_smile:

Might add a high-level approach later.


Aaaaagh - there’s a far easier way to do it with a little thought! The minimum X will always be 0 (as we can always generate a 0-cost subset sum in the path from source to the pivot and in the path from the pivot to the destination), so we just need to find the largest cost subset sum that can be generated in both the source-to-the-pivot and the in the path from the pivot-to-the-destination XD That was embarrassing!

Thank you …:slightly_smiling_face::slightly_smiling_face:

1 Like