1D Convolution

题面

Implement a program that performs a 1D convolution operation. Given an input array and a kernel (filter), compute the convolved output. The convolution should be performed with a "valid" boundary condition, meaning the kernel is only applied where it fully overlaps with the input.

Illustration

Given:

• Input: [1, 2, 3, 4, 5]
• Kernel: [1, 0, -1]

Step 1 (Index 0):
Multiply input slice [1, 2, 3] with kernel [1, 0, -1]:
1*1 + 2*0 + 3*(-1) = 1 + 0 - 3 = -2
Output so far: [-2]

The input consists of two arrays:

• input: A 1D array of 32-bit floating-point numbers.
• kernel: A 1D array of 32-bit floating-point numbers representing the convolution kernel.

The output should be written to the output array, which will have a size of input_size - kernel_size + 1.

The convolution operation is defined mathematically as:

$$\text{output}[i] = \sum_{j=0}^{\text{kernel\_size}-1} \text{input}[i+j] \cdot \text{kernel}[j]$$

where $i$ ranges from $0$ to $\text{input\_size} - \text{kernel\_size}$.

Implementation Requirements

• Use only native features (external libraries are not permitted)
• The solve function signature must remain unchanged
• The final result must be stored in the array output

Examples

Example 1:

Input: input = [1, 2, 3, 4, 5], kernel = [1, 0, -1]
Output: [-2, -2, -2]

Example 2:

Input: input = [2, 4, 6, 8], kernel = [0.5, 0.2]
Output: [1.8, 3.2, 4.6]

Constraints

• $1 \le \text{input\_size} \le 1,500,000$
• $1 \le \text{kernel\_size} \le 2047$
• $\text{kernel\_size} \le \text{input\_size}$
• Performance is measured with $\text{input\_size} = 1,500,000, \text{kernel\_size} = 2,047$