811. The First Broken Build

A server numbers its builds 1, 2, 3 and so on up to n. Regression reports arrive from m independent monitors. Monitor i files its first report at build o[i] and then files another one every p[i] builds, for ever. So by the time build v is cut, monitor i has filed

(v - o[i]) / p[i] + 1 reports, when v >= o[i] (integer division) 0 reports, when v < o[i]

A build is BROKEN once the total number of reports filed by then, added up over all monitors, has reached R.

Print the smallest broken build in the range 1 .. n. If no build in that range is broken, print -1.

n=5, monitors (o=1,p=2) and (o=3,p=2), R=4 -> 5 n=5, the same monitors, R=100 -> -1 n=10, one monitor (o=1,p=1), R=10 -> 10

In the first line the totals at builds 1 to 5 are 1, 1, 3, 3, 5, so build 5 is the first to reach 4.

## Why walking the builds one at a time is too slow

Counting the reports at a GIVEN build is easy, one pass over the monitors. Finding the first build that qualifies by trying v = 1, then 2, then 3, costs O(m) each time and n can be 2 * 10^9, so at the limits that is 2 * 10^14 operations.

## The predicate is monotone

Fix a monitor. As v grows, (v - o[i]) / p[i] never falls, because integer division by a fixed positive number is non-decreasing in its numerator, and the term switches from 0 to a positive value exactly once. So every term of the total is non-decreasing in v, therefore the total is too, therefore a build that is broken is followed only by builds that are broken. The answers to "is build v broken?" read

no no no YES YES YES and so on

and the answer is the seam.

## The invariant the loop maintains

Start with lo = 1 and hi = n, and keep this true at the top of every iteration:

> if any build in 1 .. n is broken, the smallest one lies in [lo, hi].

It holds at the start because the whole range is [1, n]. Each step takes mid strictly inside the range and asks the predicate once. If mid is broken, no build after mid can be the smallest broken one, so hi = mid keeps the invariant, and note mid itself stays in play. If mid is not broken, monotonicity says nothing at or below mid is broken either, so lo = mid + 1 keeps it.

## Why the loop terminates

mid = lo + (hi - lo) / 2 satisfies lo <= mid < hi whenever lo < hi, because the integer division rounds down and hi - lo >= 1. The first branch sets hi to something strictly less than the old hi; the second sets lo to something strictly greater than the old lo. So hi - lo drops by at least one every iteration and the loop runs at most log2(n) times, about 31 here.

## What is printed when nothing qualifies

The loop always ends with lo == hi, and it has no way to report "nothing". So test the top of the range FIRST: if build n is not broken, print -1 and stop. After that check the answer is guaranteed to exist and the seam the loop finds is it.

## The midpoint, and why the obvious spelling breaks

n can be 2 * 10^9. That still fits in a signed 32-bit integer, whose ceiling is 2147483647, so int looks like a perfectly sensible type for a build number, and on the first iteration lo + hi is 2000000001, which also fits. A few iterations later lo has climbed to 1500000001 while hi is still 2000000000, and now lo + hi is 3500000001. In C, C++ and Java that addition wraps to a negative number, the division produces a negative midpoint, and the search collapses.

lo + (hi - lo) / 2 never forms that sum. hi - lo is at most the width of the range, which is itself a representable value, so the expression cannot overflow, and it produces the same midpoint as (lo + hi) / 2 whenever lo <= hi. Use it everywhere, not only when you think the numbers are large.

## Overflow in the counter

One monitor with p[i] = 1 files 2 * 10^9 reports by the last build, and there can be 10^5 monitors, so the honest total reaches 2 * 10^14. That needs 64 bits. Stop adding the moment the running total reaches R, which caps the value and makes the check faster at the same time.

## Related problems

Problem 753 adds a very similar sum of integer divisions, but its upper bound is constructed so that it always works, so it never has to say "no answer". Here the top of the range can fail, which is why -1 exists and why it is tested first.

## Cost

Time O(m log n). Space O(m).

Constraints - `1 ≤ n ≤ 2000000000` - `1 ≤ m ≤ 100000` - `1 ≤ o[i] ≤ n` - `1 ≤ p[i] ≤ 1000000000` - `1 ≤ R ≤ 10^15`