The Difference Engine
Input: standard input
Output: standard output
Time Limit: 3 seconds
A good way to transmit information over an unreliable connection is to
use redundancy to eliminate the damage caused by small errors. For instance, a checksum on data can be used
to reliably determine if a mistake exists anywhere in the data. And if one byte (anywhere in the data) is
missing, the checksum can be used to reconstruct the value of that byte. We will examine a generalized redundancy
approach that allows us to reconstruct a message from which some information
has been lost.
Let p be a prime. Suppose we have
a sequence of p "chunks", a1, a2, ..., ap, each with a value between 0 and p-1 inclusive. We can construct a "difference sequence,"
b1, b2, ..., bp, which has
the same format, and contains the differences between successive elements of
a. (Modular arithmetic is used to
keep the values between 0 and
p-1) So b1 == a2 - a1 (mod p); b2 == a3
- a2 (mod p); and so on, wrapping around to give bp
== a1 - ap (mod p).
We can take the difference sequence of this difference sequence to get a
"2nd difference sequence".
In general, let the "nth difference sequence" be the result of
applying this operation to a sequence n times.
Not every sequence can be an "nth difference sequence", so such
a sequence is redundant in a very useful way.
If somebody tells you they have a message (a sequence of this form) that
IS an nth difference sequence, and sends it to you, you can reconstruct their
message even if up to n "chunks" are lost along the way. It is straightforward to encode useful
information this way: you can write p-n "chunks" of information, then
add n "chunks" to make the sequence an nth difference sequence (of
some unimportant initial sequence).
Write a program to
reconstruct messages of this form.
There will be up to 100 cases,
each consisting of two lines. The first
line contains p, a prime number less than 100, and n, a positive integer. The second line contains p integers from 0 to
p-1, containing the message; however, up to n of them may be missing, and will
be replaced by question marks.
Input is terminated by a line
containing two zeros.
For each case, output one line
containing the reconstructed message, which will be an "nth difference
sequence". If this is impossible,
output "Invalid message!".
for Sample Input
1 3 4 ? 3
1 3 4 2 3
1 3 4 4 3
Problem setter: Derek Kisman,