Overview

Given multiple types of strings with fixed lengths, select them within their stock limits so that the total length is exactly \(W\) while minimizing the number of strings used (output \(-1\) if it’s impossible).

Analysis

This is a bounded knapsack problem where, instead of maximizing value, we minimize the number of strings (cost) while making the total length exactly \(W\).

• It is natural to maintain the state “minimum number of strings to achieve length \(x\).”
• However, naive approaches such as:
  • For each type, enumerate all \(k=0..C_i\) strings used and transition (\(O(W\sum C_i)\))
  • Or decompose into \(C_i\) copies of 0/1 knapsack (also too slow)

will not be fast enough given \(W\le 50000\) and \(C_i\le 10000\).

The key observation is that when considering only strings of length \(L\), the transition is

[ dp’[x] = \min_{0 \le k \le C,\ x-kL\ge 0}{dp[x-kL] + k} ]

and for the same \(L\), the processing is independent for each residue class \(x\equiv r\pmod L\).
By applying a sliding window minimum (monotonic deque) to the “sequence for each residue,” we can perform the update in \(O(W)\).

Also, the input may contain “types with the same length,” so aggregating the stock counts by length beforehand reduces the number of types and simplifies the implementation.

Algorithm

1. DP Definition

• \(dp[x]\): minimum number of strings to achieve a total length of exactly \(x\) (\(\infty\) if impossible)
• Initial values: \(dp[0]=0,\ dp[1..W]=\infty\)

2. Update for length \(L\) and stock \(C\) (monotonic deque optimization)

The transition is

[ dp’[x] = \min_{k}{dp[x-kL] + k} ]

Setting \(x=r+mL\) (where \(r\) ranges from \(0\) to \(L-1\)) and increasing \(m\):

[ dp’[r+mL] = \min_{t \in [m-C,\ m]}{dp[r+tL] + (m-t)} ]

Rearranging the right-hand side:

[ dp’[r+mL] = m + \min_{t \in [m-C,\ m]}{dp[r+tL] - t} ]

In other words, for each residue \(r\), we define the sequence [ A[t] = dp[r+tL] - t ] and need to compute the range minimum over a window of width \((C+1)\) in order.

For each \(r\), we use a deque (monotonic queue):

• The deque maintains candidates \((t, A[t])\) in increasing order of \(A[t]\)
• Candidates out of range (\(t < m-C\)) are removed from the front
• The front always holds the range minimum

This computes \(dp'[r+mL] = m + \text{(front } A[t]\text{)}\) in amortized \(O(1)\).

3. Answer

After processing all types, if \(dp[W]\) is \(\infty\), output \(-1\); otherwise, output \(dp[W]\).

Complexity

• Time complexity: \(O(W \cdot M)\) (\(M\) is the number of distinct lengths. For each type, all \(x=0..W\) are processed in a total of \(O(W)\))
• Space complexity: \(O(W)\) (the \(dp\) array)

Implementation Notes

• Aggregate stock counts for the same length (cnt_by_len[L] += C). This eliminates redundant loops.

• Use a sufficiently large value INF to represent “impossible,” and at the end check whether dp[W] equals INF.

• Two key points for managing the monotonic deque:

  • Remove candidates with “worse (larger) values” from the back to maintain monotonicity

  • Remove candidates “out of range due to stock limits” from the front (discard when \(t < m-C\))

    Source Code

import sys
from collections import defaultdict, deque

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    W = int(next(it))

    cnt_by_len = defaultdict(int)
    for _ in range(N):
        L = int(next(it))
        C = int(next(it))
        cnt_by_len[L] += C

    items = sorted(cnt_by_len.items())  # (L, C)

    INF = 10**18
    dp = [INF] * (W + 1)
    dp[0] = 0

    for L, C in items:
        new_dp = [INF] * (W + 1)
        for r in range(L):
            dq = deque()  # (m, dp[r+mL] - m)
            m = 0
            x = r
            while x <= W:
                val = dp[x] - m
                while dq and dq[-1][1] >= val:
                    dq.pop()
                dq.append((m, val))
                while dq[0][0] < m - C:
                    dq.popleft()
                new_dp[x] = dq[0][1] + m
                m += 1
                x += L
        dp = new_dp

    ans = dp[W]
    print(-1 if ans >= INF // 2 else ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.