Overview

Given \(N\) types of strings (length \(L_i\), stock \(C_i\) pieces each), the problem asks for the minimum number of strings needed to combine them so that the total length is exactly \(W\) centimeters.

Analysis

This problem is a minimization version of the classic “bounded knapsack problem”.

Naive Approach

We consider using dynamic programming (DP). Define \(dp[i][j]\) as “the minimum number of strings needed to make length \(j\) using only the first \(i\) types of strings.” The transition is as follows: \(dp[i][j] = \min_{0 \le k \le C_i} \{ dp[i-1][j - k \cdot L_i] + k \}\)

However, if we implement this transition directly, we need \(C_i\) comparisons for each \(j\). In the worst case, the time complexity becomes \(O(W \cdot \sum C_i)\), which is too slow for the constraints of this problem (\(W=50000, C_i=10000\)).

Hint for Optimization

Looking closely at the transition, we notice that transitions for length \(j\) only come from positions with the same “remainder” when divided by \(L_i\). For example, when using strings of length \(L_i=3\), positions with remainder \(0\) (\(0, 3, 6, \dots\)) only update among themselves and do not interfere with positions with remainder \(1\) (\(1, 4, 7, \dots\)).

Therefore, we compute independently for each remainder \(r \in \{0, 1, \dots, L_i-1\}\). Setting \(j = q \cdot L_i + r\), the transition can be rewritten as: \(dp[r + q \cdot L_i] = \min_{q - C_i \le p \le q} \{ dp[r + p \cdot L_i] + (q - p) \}\) \(dp[r + q \cdot L_i] = \min_{q - C_i \le p \le q} \{ dp[r + p \cdot L_i] - p \} + q\)

The expression inside the \(\min\), \(\{ dp[r + p \cdot L_i] - p \}\), takes the form of finding the minimum within a specific range (window). This can be computed in amortized \(O(1)\) per \(q\) using the “sliding window minimum” algorithm.

Algorithm

DP with Sliding Window

1. Initialize the DP table with \(dp[0]=0\) and all other entries as infinity (\(\infty\)).
2. For each string type \(i=1 \dots N\), perform the following:
   • Group by remainder \(r = 0, \dots, L_i-1\) when divided by length \(L_i\).
   • Within each group, compute the “sliding window minimum” using a double-ended queue (deque).
   • The deque maintains indices \(p\) such that the values \(dp[r + p \cdot L_i] - p\) are kept in ascending order.
   • When the left end of the window exceeds \(q - C_i\), remove old elements from the deque.
3. The final answer is \(dp[W]\). If it was never reached, output \(-1\).

Complexity

• Time Complexity: \(O(NW)\)
  • For each string type, we scan the array of length \(W\) a constant number of times, so the complexity does not depend on the stock count \(C_i\).
• Space Complexity: \(O(W)\)
  • This can be achieved by reusing a 1-dimensional DP array.

Implementation Notes

• Special case optimizations:

  • When \(C_i = 1\), this can be optimized by updating from back to front as a “0/1 knapsack problem.”
  • When \(C_i \ge W/L_i\), this can be optimized by updating from front to back as an “unbounded knapsack problem.”

• Optimization in Python:

  • By using collections.deque and caching methods such as append and pop into local variables, we can reduce overhead inside loops.

  • Using slice notation like dp[r::L] allows efficient extraction and updating of elements with a specific remainder.

    Source Code

import sys
from collections import deque

def solve():
    # Read all input data at once for speed
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Use an iterator to efficiently traverse the input data
    it = iter(input_data)
    N = int(next(it))
    W = int(next(it))
    
    # dp[j] stores the minimum number of strings to reach a total length of j
    INF = 10**9
    dp = [INF] * (W + 1)
    dp[0] = 0
    
    for _ in range(N):
        L = int(next(it))
        C = int(next(it))
        
        # If the string length is greater than the target W, it cannot be used
        if L > W:
            continue
        
        # Optimization for special cases of the Bounded Knapsack Problem
        if C == 1:
            # 0/1 Knapsack optimization: iterate backwards to reuse results from previous items
            for j in range(W, L - 1, -1):
                new_val = dp[j - L] + 1
                if new_val < dp[j]:
                    dp[j] = new_val
        elif C >= W // L:
            # Unbounded Knapsack optimization: iterate forwards to allow using the same item multiple times
            for j in range(L, W + 1):
                new_val = dp[j - L] + 1
                if new_val < dp[j]:
                    dp[j] = new_val
        else:
            # General Bounded Knapsack using a sliding window (monotonic queue) for O(NW) total complexity
            for r in range(L):
                # If the remainder r + L exceeds W, this slice will only contain one element which cannot be updated
                if r + L > W:
                    break
                
                # Extract the relevant slice of dp values for the current remainder r
                old_vals = dp[r::L]
                n_q = len(old_vals)
                new_vals = [INF] * n_q
                deq = deque()
                
                # Cache deque methods for slight performance gain in Python
                deq_append = deq.append
                deq_pop = deq.pop
                deq_popleft = deq.popleft
                
                for q in range(n_q):
                    ov_q = old_vals[q]
                    # Only add reachable states to the deque
                    if ov_q < INF:
                        # We want to minimize (dp[r + p*L] - p) + q
                        val = ov_q - q
                        # Maintain the deque such that values are in non-decreasing order
                        while deq and deq[-1][0] >= val:
                            deq_pop()
                        deq_append((val, q))
                    
                    # Ensure the current string count (q - p) does not exceed the stock count C
                    if deq and deq[0][1] < q - C:
                        deq_popleft()
                    
                    # Update new_vals with the minimum found in the current window
                    if deq:
                        new_vals[q] = deq[0][0] + q
                
                # Assign the updated slice back to the main dp array
                dp[r::L] = new_vals
                
    # Final answer: if dp[W] is still INF, it's impossible to form exactly W cm
    ans = dp[W]
    if ans >= INF:
        print("-1")
    else:
        print(ans)

if __name__ == '__main__':
    solve()

---

This editorial was generated by gemini-3-flash-thinking.