Question

AsliVideo is revolutionizing their video streaming platform! They’ve developed N different compression algorithms and tested them on M different types of video content. For each video type, they know:

1. How many units of processing power each algorithm consumes
2. The total compression score achieved when all algorithms work together

The engineering team needs to determine each algorithm’s individual contribution to the compression score.

• The first line contains two integers N and M (1 ≤ N, M ≤ 100) — the number of algorithms and video types respectively
• The next M lines each contain N+1 integers:
  • First N integers p[i] (0 ≤ p[i] ≤ 1000) represent the processing power units (cpu cycles) required by each algorithm for this video type
  • The last integer s (0 ≤ s ≤ 10000) represents the total compression score achieved for this video type

Output

• Output N space-separated floating-point numbers — the individual contribution of each algorithm to the compression score
• the absolute or relative error should not exceed 10^-6
• If you think there is no solution for the given input, output “observation error”

Example

Input:
3 3
2 1 3 95
1 3 1 82
3 2 1 75

Output:
5.58823529 18.17647059 21.88235294

Input:
3 3
2 1 0 95
1 3 0 82
3 2 0 75

Output:
observation error

Solution

Here’s the code for reference and some notes on the solution below.

• We have a system of linear equations where each equation represents a video type
• The unknowns are the individual contributions of each algorithm
• The coefficients are the processing power units
• The constants are the total compression scores

For the example input, our system looks like this:

2x + y + 3z = 95
x + 3y + z = 82
3x + 2y + z = 75

where x, y, z are the individual contributions we’re looking for.

This is a perfect case for solving using matrices. We can use NumPy to solve this system efficiently.

...
x = np.linalg.solve(A, b)
...

numpy.linalg.solve function efficiently solves the system Ax = b. Internally it uses advanced numerical methods (like LU decomposition) under the hood.

We should also verify the solution using np.allclose() to ensures our solution actually satisfies all equations within tolerance. We handle cases where no solution exists

Practical Applications

The problem and its solution mirror real-world scenarios in:

1. Feature attribution in ML models
2. Resource allocation problems
3. Signal processing
4. Computer vision (image reconstruction)
5. Optimization problems in general