Optimizing Contest Problem Sets

A company produces programming contest problems. The problems come in two types:

• Fixed‐difficulty problems: For each difficulty level \(i\) (where \(0 \leq i \leq N-1\)), there are \(A_i\) problems.
• Ambiguous problems: For each \(i\) (where \(0 \leq i \leq N-2\)), there are \(B_i\) problems whose difficulty can be assigned either as \(i\) or \(i+1\).

There are also \(M\) companies (numbered from \(0\) to \(M-1\)) interested in buying a set of contest problems. The \(j\)th company is only interested in problems with difficulties in the range \([L_j, U_j]\). For company \(j\), a competition is defined as a selection of exactly one problem for each difficulty level in the range \([L_j, U_j]\) (i.e. one problem of difficulty \(L_j\), one of \(L_j+1\), and so on, up to \(U_j\)).

The twist is that when using an ambiguous problem \(B_i\), you may choose to use it either as a problem of difficulty \(i\) or difficulty \(i+1\), but each problem can only be used once in a single competition. When selling to only one company \(j\), you are allowed to assign the ambiguous problems arbitrarily among the difficulties so that the number of complete competitions sold is maximized.

Your task is to implement the function:

[ \texttt{vector testset(vector A, vector B, vector L, vector U);} ]

which returns an array \(S\) of size \(M\) such that \(S_j\) is the maximum number of complete competitions that can be sold to company \(j\).

Note: There is no standard input or output. You only need to implement the function as specified.

Constraints and Clarifications:

• The fixed supply for difficulty \(i\) is \(A_i\).
• An ambiguous problem in \(B_i\) can be used as either difficulty \(i\) or difficulty \(i+1\) as needed.
• Each competition requires one problem for every difficulty level in the interval \([L_j, U_j]\); problems may not be reused across competitions.
• You may assume that the arrays A, B, L and U are all valid and that \(N\) (the length of A) is at least 1; B has length \(N-1\); and L and U have length \(M\).

inputFormat

The function testset is provided with the following inputs:

• A: an integer array of length \(N\); \(A[i]\) represents the number of problems with difficulty \(i\).
• B: an integer array of length \(N-1\); \(B[i]\) represents the number of ambiguous problems that can be assigned either difficulty \(i\) or \(i+1\).
• L and U: integer arrays of length \(M\); for each company \(j\) (\(0 \leq j \leq M-1\)), L[j] and U[j] represent the minimum and maximum difficulties, respectively, that the company is interested in.

The function is to compute and return an integer array \(S\) of length \(M\) where \(S[j]\) is the maximum number of complete competitions (sets of problems) that can be sold to company \(j\) under an optimal allocation of ambiguous problems.

outputFormat

The function should return an integer array \(S\) of length \(M\). For each company \(j\):

• S[j] is the maximum number of competitions (each competition being a set of one problem per difficulty level in the range \([L_j, U_j]\)) that can be assembled without reusing any problem. Ambiguous problems may be allocated as either required difficulty so long as each is used at most once.

sample

A = [3, 2, 1]
B = [1, 1]
L = [0, 1]
U = [1, 2]

[3,2]