Laboratory

First, sort all type numbers lexicographically by $(B_i,i)$ to obtain a permutation $p_1,p_2,\ldots,p_N$. The growth-coefficient order of any selected sample is a subsequence of this permutation.

Fix a day $t$, and place the pair $X_j(t)=(A_{p_j}+B_{p_j}t,p_j)$ at each position of the permutation. Compare pairs by their first components, breaking ties by their second components. The selected types have the same population order exactly when their pairs are strictly increasing under this comparison. Thus, the maximum number of types that can be selected on day is the length of the longest increasing subsequence of these pairs. Comparing only populations would miss the rule for tied populations, so type numbers must also be included.

Compute the longest increasing subsequence by maintaining the smallest possible final pair for every subsequence length. Process the pairs in order. Use binary search to find the first stored final pair greater than or equal to the current pair, and replace it with the current pair. If no such position exists, append the current pair. This check takes $O(N\log N)$ time.

A sample that satisfies the condition on a certain day also satisfies it on every later day. Consequently, the predicate that the longest increasing subsequence has length at least $K$ changes only from false to true as the day increases. Let $U=10^9$. If the condition holds on day $0$, output $0$ immediately. Otherwise, if the length is still less than $$ on day , output . In the remaining cases, binary search over for the first day satisfying the condition.

The initial sort takes $O(N\log N)$ time, and there are $O(\log U)$ checks. The total time complexity is $O(N\log N\log U)$, and the space complexity is .

Proof

Consider two types $p,q$ in their growth-coefficient order, with $p$ appearing first. Then $B_p\leq B_q$. The population difference never decreases as increases.

Solution written by GPT6