1116. The Day Every Flower Is Open

One gardener plants n seeds. Planting seed i occupies the gardener for plant whole days, and exactly grow days after it is planted the seed blooms. Growing needs no attention, so every planted seed grows at the same time as the gardener works on the next one.

Print the earliest day by which every seed has bloomed.

seeds (plant=1,grow=2) (plant=4,grow=3) (plant=3,grow=1) -> 9 seeds (plant=7,grow=7) -> 14 seeds (plant=1,grow=100) (1,1) (1,1) -> 101 seeds (plant=100,grow=1) (1,1) (1,1) -> 103

Trace the first line. Sorted by growing time descending the order is (4,3), (3,1), (1,2). The gardener finishes planting them on days 4, 7 and 8, so they bloom on days 7, 8 and 10. Wait: that gives 10, not 9.

Recompute. Sorted by growing time descending the order is (4,3) with grow 3, then (1,2) with grow 2, then (3,1) with grow 1. Planting finishes on days 4, 5 and 8, so they bloom on days 7, 7 and 9. The answer is 9, and the paragraph above had the second and third seeds the wrong way round on purpose.

## What most people try first

Planting the QUICKEST seeds first, so that more of them are growing sooner. That is wrong on (1,100) (1,1) (1,1): planting the two quick ones first gives blooms on days 2, 3 and 103, so 103, while planting the slow grower first gives 101. Every seed takes one day to plant there, so the quick-first rule has nothing to say and any order it picks may be the bad one.

Planting the seeds with the SHORTEST total plant + grow first is also wrong, for the same reason: what matters is not how long a seed takes altogether but how much of that time runs in parallel.

Trying every order costs n!.

## The method

sort by grow DESCENDING elapsed = 0 answer = 0 for (plant, grow) in that order: elapsed = elapsed + plant answer = max(answer, elapsed + grow)

One sort and one pass.

The planting is strictly sequential, so the total planting time is the same whatever order is used; only which seed carries which prefix changes.

## Why the longest grower goes first

Take any order and two ADJACENT seeds, a immediately before b, with E days of planting already done. Everything outside the pair is untouched by a swap, since the pair occupies plant_a + plant_b days either way.

The bloom days contributed by the pair are

a then b: max( E + plant_a + grow_a , E + plant_a + plant_b + grow_b ) b then a: max( E + plant_b + grow_b , E + plant_a + plant_b + grow_a )

Look at the second expression. Its first term is at most its second term plus nothing useful, so compare the largest terms: E + plant_a + plant_b + grow_b against E + plant_a + plant_b + grow_a. When grow_a >= grow_b the second is at least the first, and the remaining terms of the first expression are both dominated, so putting a first is at least as good.

An order unimprovable by adjacent swaps is exactly the one sorted by grow descending, so that order is optimal.

The intuition is worth keeping: growing is free time, so the seed with the most free time to burn should start burning it first.

## The boundary that breaks a careless implementation

answer is the maximum over seeds of elapsed + grow, not the last seed's value. The last seed planted has the largest elapsed and the smallest grow, and the maximum can easily sit earlier in the order. On (1,100) (1,1) (1,1) the maximum is the FIRST seed, at day 101, while the last blooms on day 4.

Planting times are at least 1, so the gardener is never idle and the elapsed total is simply their sum.

## Sizes

n reaches 10^5 and both numbers reach 10^9, so the total planting time reaches 10^14 and the answer reaches the same magnitude. That is far past the 2147483647 limit of a signed 32-bit integer, and three seeds with both numbers at 10^9 already answer 4 * 10^9, which is the seventh test.

## A related problem

Problem #1111 is the other "two stages, one of which runs in parallel" problem in this block, and it is strictly harder because the second stage there is a single shared machine rather than free parallel time. Comparing the two shows what "unlimited parallelism in the second stage" buys: the rule collapses from Johnson's grouping to a single descending sort.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ plant ≤ 1000000000` - `1 ≤ grow ≤ 1000000000`