Lesson 13

Programming problem. Implement decoding for the Reed–Solomon code.

The first line contains integers \(1 \le k \le n \le q \le 5000\), where \(q\) is prime. The next line contains a codeword consisting of \(n\) elements of \(\mathbb{F}_{q}\) (space-separated), encoding a message of length \(k\). The encoding procedure is based on evaluating a polynomial at the points \(1, 2, \dotsc, n \in \mathbb{F}_{q}\). It is guaranteed that the number of errors in the codeword does not exceed \(\lfloor \frac{n-k}{2}\rfloor\). Output the original message of length \(k\).

1 3 5
0 3 3

3