Item — HN Reader

Am I completely misunderstanding the problem, or is the math in the example solution wrong?

    Bursting 1 first gives you 3×1×5=15 coins. <-- OK...
    Bursting 3 first gives you 1×3×1=1 coins. (using left virtual balloon) <-- Should be 3?
    A possibility would be bursting 1, then 5, then 3, which gives you a total of 3×1×5+3×5×1+1×3×1=33 coins. <-- Should be 3x1x5+1x5x1+1x3x1=24?

2 comments

The first error seems to be a transcription error, it's correct in their graph representation further down.

The second one isn't an error, but a poor explanation. After a balloon is burst, the balloons now have new neighbors. That is, it isn't this:

  3 1 5 -> pop 1 = 15
  3 _ 5 -> pop 3 = 3

It's:

  3 1 5 -> pop 1 = 15
  3 5   -> pop 3 = 15

The distance between the balloons doesn't make them not neighbors.

If you have "3 1 5" and you burst 1, you gain 3x1x5 points and the state becomes "3 5", with the two remaining balloons being adjacent to each other.

The "1x3x1=1" part for the earlier example is a typo indeed, it should be 3.