PROBLEM STATEMENT
When transmitting data over great distances, there is always a chance that some
errors will creep in due to noise in the wires. As a result, modern
communication systems use an encoding and decoding schema that reduces the risk
of errors corrupting data. The transmitter first encodes the data based on two
parameters (upperConnection and lowerConnection). The transmitter then sends
the encoded data to a receiver, which also knows the two parameters
(upperConnection and lowerConnection). The receiver uses the encoded data, and
the same two parameters as the transmitter user to decode the data. Because
some errors might occur during the transmission of the encoded sequence, the
receiver decodes the encoded data by finding some data which, when encoded, is
as similar as possible to the encoded sequence that is received.
The message is encoded using a number of shift registers, which are one bit
devices used to temporarily store data. The number of shift registers is
dictated by the number of elements in upperConnection (which is the same as the
number of elements in lowerConnection).
The encoding process works as follows:
1) Initially all the shift registers are set to zero.
2) All data currently in the registers is shifted one place up, and the next
bit in the data being encoded is shifted into the first register.
3) We obtain two binary digits (an upper and a lower) by XORing certain bits
together. Which bits are XORed is dictated by upperConnection and
lowerConnection. Each of these int[]'s tells us how to generate one of the
binary digits. For each bit in the shift register, if there is a one in the
corresponding place in the int[], that bit is XORed, otherwise the bit is
ignored. For example, if upperConnection = {1,0,1,1,0}, then the bits in the
first, third, and fourth shift registers should be XORed together, while the
second and fifth registers can be ignored for this calculation. The same
process is applied using lowerConnection.
4) The output from both upper and lower connections is then transmitted.
5) Go to 2 and repeat until there is no more data to shift in.
For Example:
Saw we want to encode the data {1,0,1,0}
upperConnection is {1, 1, 1}
lowerConnection is (1, 0, 0}
Since upper and lower connections have three elements, there are three shift
registers.
- At time t=0 the shift registers are all zero, so we have {0,0,0}.
- At t=1 the first bit of the data is shifted into the first register giving us
{1,0,0}. We now must generate the output based on the upper and lower
connections. The upper connection tells us that all three bits in the
registers should be XORed together. 1 XOR 0 XOR 0 = 1, so the upper output is
1. The lower connection tells us that only the first bit should be XORed.
Thus the lower output is the same as the first shift register, which is 1.
- At t=2 a zero is shifted in giving us {0,1,0}. The upper connection XORs all
of the bits so it outputs 1. The lower connection takes only the first bit
which is a zero, so its output is 0.
- At t=3 a one is shifted in giving us {1,0,1}. So the upper result is zero and
the lower result is one.
- At t=4 a zero is shift in giving us {0,1,0}. So the upper result is one and
the lower result is zero.
Thus the upper output is {1,1,0,1} and the lower output is {1,0,1,0}.
The upper and lower sequences are then transmitted from the sender to the
receiver. The receiver must then decode the data be figuring out what data
generated the encoded sequence it receives. Your task is to write a class
CovEncoder, with a method decoding, which takes an int[] upperConnection, an
int[] lowerConnection, an int[] upperReceived, and an int[] lowerReceived, and
returns the data which is most likely to have generated the upperReceived, and
lowerReceived, given the upper and lower connections. For the purposes of this
problem, we will define the most likely data to be that which gives rise to
upper and lower sequences with the fewest differences from the received
sequences. Thus, if encoding some data generates a lower of {0,0,1,0} and
lowerReceived is {1,0,1,0}, there is one difference between the sequence that
is received, and the sequence generated from the candidate data. This data is
less likely to be the original data (that was encoded by the transmitter) than
some other data whose encoding generates a lower of {1,0,1,0}, since this lower
sequence has zero differences from lowerReceived, (assuming that both generate
the same upper sequence).
DEFINITION
Class: CovEncoder
Method: decoding
Parameters: int[], int[], int[], int[]
Returns: int[]
Method signature (be sure your method is public): int[] decoding(int[]
upperReceived, int[] lowerReceived, int[] upperConnection, int[]
lowerConnection);
NOTES
-If two or more sequences of data are detected which are equally likely, pick
the one where the first difference in the two sequences is a zero. Thus, if
{0,0,1,0,0,1} and {0,0,1,1,0,0} are both equally likely as the originally data,
return {0,0,1,0,0,1} because it has a zero as the fourth element, and the first
three elements are the same in both sequences. See Example 3.
-lower and upper connection are both established prior to transmission of any
data, so we are guaranteed that we have the same upper and lower connection as
those used to encode the data.
-upperReceived and lowerReceived have up to 50 elements each, so it will not be
possible to evaluate all 2^50 possible data sequences to find the one that
gives rise to the fewest differences.
-When making up your own problems, know that certain combinations of errors can
cause the decoded sequence to not be what the input to the encoder was.
-When a number of bits are XORed together, the result is a one if and only if
the number of bits which are one is odd. Otherwise the result is zero.
TopCoder will ensure the validity of all inputs. Inputs are valid if:
- upperConnection and lowerConnection will have between 2 and 10 elements each
one or zero representing no connection or a connection.
- upperConnection and lowerConnection are the same length.
- upperReceived and lowerReceived will each contain between 3 and 50 numbers,
each of which is a 1 or a 0.
- upperReceived and lowerReceived will have the same length.
EXAMPLES
1)
upperReceived = {0,1,1}
lowerReceived = {0,0,0}
upperConnection = {1,0}
lowerConnection = {1,1}
Since upperReceived and lowerReceived both have 3 bits, the decoded data must
also have three bits. There are 8 possible sequences of three bits, each of
which is a candidate for the decoded data.
if we encode {0,0,0} we get an upper of {0,0,0} and a lower of {0,0,0} which
has 2 differences from the received upper and lower.
if we encode {0,0,1} we get an upper of {0,0,1} and a lower of {0,0,1} which
has 2 differences.
if we encode {0,1,0} we get an upper of {0,1,0} and a lower of {0,1,1} which
has 3 differences.
if we encode {0,1,1} we get an upper of {0,1,1} and a lower of {0,1,0} which
has 1 difference.
if we encode {1,0,0} we get an upper of {1,0,0} and a lower of {1,1,0} which
has 5 differences.
if we encode {1,0,1} we get an upper of {1,0,1} and a lower of {1,1,1} which
has 5 differences.
if we encode {1,1,0} we get an upper of {1,1,0} and a lower of {1,0,1} which
has 5 differences.
if we encode {1,1,1} we get an upper of {1,1,1} and a lower of {1,0,0} which
has 2 differences.
We can see the answer with the least differences is the input of {0,1,1}
Returns {0,1,1}
2)
upperReceived = {1,0,0}
lowerReceived = {0,1,1}
upperConnection = {1,0}
lowerConnection = {1,1}
Going through all possible inputs to the encoder we find that {0,1,0}, {1,0,0},
and {1,0,1} have 2 errors each.
Of these, we see that {0,1,0} has a zero in the first place and the other two
have a 1 in the first place. So we eliminate {1,0,0}, and {1,0,1} and are left
with {0,1,0} which is the answer.
Returns {0,1,0}
3)
upperReceived = {1,1,1,0,1}
lowerReceived = {1,0,1,1,1}
upperConnection = {1,1,1}
lowerConnection = {1,0,1}
returns {1,0,0,0,1}