775. Sizing the Message Parts
A message of L characters has to be sent as exactly k numbered parts. Part i, for i from
1 to k, carries some of the message followed by the tag <i/k>. The tag for part 3 of 12 is
the six characters <3/12>, so a tag occupies 3 + digits(i) + digits(k) characters, counting
the angle brackets and the slash.
Every part must be at most limit characters long INCLUDING its tag, every part must carry at
least one character of the message, the parts in order must spell out the message exactly, and
no character may be duplicated or dropped.
Print the smallest limit that makes this possible, or -1 if no limit does.
L = 14, k = 3 answer 10 tags are 5 long, so 3 parts hold 3 * 5 = 15 >= 14
L = 5, k = 5 answer 6 every part carries exactly one character
L = 1, k = 1 answer 6 the tag <1/1> is five characters and one must follow
L = 3, k = 4 answer -1 four parts cannot each hold a character of a 3-character message
## Why the usual version of this question is NOT a binary search
Worth saying first, because the trap is real. The commonly asked form of this problem fixes
limit and asks for the FEWEST parts. That version is not monotone: raising k from 9 to 10
lengthens every single tag by one character, so total capacity can go DOWN even though there
are more parts. A binary search over k is simply wrong there, and the accepted solution scans
k upwards.
Turn the question around, fix k and search over limit, and monotonicity comes back, because
raising the limit makes every part strictly roomier and changes no tag. Recognising which of the
two variables is the monotone one is the whole lesson of this problem.
## Capacity of a part
Part i spends 3 + digits(i) + digits(k) characters on its tag, so it can carry
cap(i) = limit - 3 - digits(i) - digits(k)
characters of the message. Let d = digits(k). Since digits(i) <= d for every i <= k, the
tightest part is one with the most digits, and its capacity is limit - 3 - 2d.
## The feasibility test
A split into exactly k parts exists if and only if
every cap(i) >= 1 which reduces to limit >= 4 + 2d
total capacity >= L which is sum over i of cap(i) >= L
The "only if" is clear: each part needs room for at least one character, and the parts together
must hold all L.
The "if" is a filling argument. Give every part one character first, which is possible because
every cap(i) >= 1 and k <= L. That leaves L - k characters to place, and the remaining
room is sum(cap(i)) - k, which is at least L - k by assumption. Pour the leftovers into the
parts in order, never exceeding any part's own capacity. Since the message is just a sequence of
characters and parts are filled left to right, the result is a valid split.
Note that k > L can never be fixed by any limit, which is the -1 case.
## Making the sum O(1)
Summing cap(i) naively is O(k) per probe. Pull the constant part out:
sum over i of cap(i) = k * (limit - 3 - d) - S, where S = sum over i of digits(i)
S does not depend on limit, so compute it ONCE before the search. It can be found in
O(log k) by counting how many values in 1 .. k have each digit length, or in O(k) by a
plain loop, which is fast enough here.
## Why the predicate is monotone
Raising limit by one raises every cap(i) by exactly one, so the total capacity rises by k
and the per-part minimum only becomes easier to satisfy. Feasibility never turns off, so the
workable limits form a suffix and the answer is the FIRST true value.
## The bounds
lo = 4 + 2d, the smallest limit at which the tightest part has room for one character. Below
that nothing is possible regardless of L.
hi = 4 + 2d + L. At that limit each part holds at least 1 + L characters, so the k parts
together hold at least L. Always feasible, so the search cannot run off the top.
## The boundary that breaks a careless implementation
The digit count of k appears in EVERY tag, including part 1's. A tag is <1/100> when
k = 100, not <1/1>, so a capacity formula that uses digits(i) twice, or forgets d
altogether, is short by a character or two on exactly the inputs where k crosses a power of
ten. The pair L = 1000, k = 99 and L = 1000, k = 100 is in the tests for that reason.
The other boundary is k > L, which must print -1 before any search runs. Letting the search
proceed returns 4 + 2d, a perfectly plausible looking number that is wrong.
## Relationship with problem 760
760 hits the same wall from the other side, and the two ways around it are worth holding
together. There the quantity to minimise is abs(f(v) - target), a V shape with no monotonicity
at all, and the repair is to search a DIFFERENT PREDICATE, f(v) >= target, then compare the two
values either side of the seam it finds.
Here the quantity is fine and the VARIABLE is wrong. Searching over the number of parts fails
because raising k past a power of ten lengthens every tag at once; searching over limit with
k fixed restores monotonicity, since a larger limit changes no tag and makes every part
roomier. One problem changes what is tested, the other changes what is searched over.
## Overflow
k reaches 10^5 and limit reaches just over 10^9, so k * (limit - 3 - d) reaches
10^14. That product must be 64-bit even though both factors fit comfortably in 32 bits, which
is the classic shape of this bug: the operands look safe and the product is not.
## Cost
O(k + log L), or O(log k + log L) with the closed form for S.
Constraints - `1 ≤ L ≤ 10^9` - `1 ≤ k ≤ 100000`
Input
The single line of input contains two integers L and k.
Output
Print one integer on its own line: the smallest workable value of limit, or -1 if no
value of limit works. No other text.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.