Statistics

Problem Statement for "PrefixSynchronization"

Problem Statement

Huffman codes are an example of the general class of minimal prefix codes. A prefix code is a set of binary codewords (sequences of 0s and 1s) in which no codeword is a prefix of another codeword. A prefix code is minimal if, for every proper prefix P of some codeword, P0 (P concatenated with 0) is a prefix of some codeword and P1 (P concatenated with 1) is also a prefix of some codeword. Note that every string is a prefix of itself, but not a proper prefix of itself, so P0 and P1 may be codewords themselves.

A message is a series of codewords. The sender concatenates codewords of the message together and transmits the resulting sequence of 0s and 1s to the receiver, who recovers the original message by deciding where the codeword boundaries fall. To accomplish this, the receiver processes the bits from left to right, grouping consecutive bits until they match a codeword. By the definition of a prefix code, only one such match is possible. The receiver then inserts a codeword boundary, and repeats until no more bits remain.

For example, suppose the code is the set {"0", "10", "11"}, and the message is the series "0", "11", "10", "0" (all quotes for clarity only). The sender would transmit the sequence "011100" to the receiver, who would first match "0", then "11", "10", and "0" again.

Because the codewords in a prefix code need not all be the same length, prefix codes are particularly susceptible to transmission errors. A single bit error can cause the sender and receiver to disagree over where codeword boundaries fall, and, once that happens, the receiver will decode gibberish until and unless the sender and receiver happen to resynchronize, meaning that they once again agree on where codeword boundaries fall.

Many prefix codes possess synchronizing sequences, which allow the sender and receiver to resynchronize. If, sometime after a transmission error has occurred, the sender transmits the synchronizing sequence, she can be sure that the receiver will correctly decode the rest of the message after the synchronizing sequence (assuming no further transmission errors occur). A synchronizing sequence is always the concatenation of one or more codewords.

For example, consider again the prefix code {"0", "10", "11"}. After an error, the receiver might think that he is at the beginning of a codeword when the sender thinks he is in the middle of a codeword, or vice versa. However, the single bit "0" is a synchronizing sequence for this prefix code. When the sender transmits a "0", there are two possibilities:

  1. The receiver thinks that he is at the beginning of a codeword and decodes a "0".
  2. The receiver thinks that he is in the middle of a codeword (ie, that he has received the first bit of either "10" or "11") and decodes a "10".
Either way, the sender and receiver now agree that the next bit begins a new codeword. In this example, the synchronizing sequence was a single bit, but in general synchronizing sequences may be of any length.

A minimal prefix code will be presented as a String[]. Create a class PrefixSynchronization containing a method shortest that takes a minimal prefix code codewords and returns the shortest synchronizing sequence (as measured in bits) for codewords, as a String. In the event that more than one synchronizing sequence of minimal length exists, choose the lexicographically first one. If no synchronizing sequences exist, return "NONE" (quotes for clarity only).

Definition

Class:
PrefixSynchronization
Method:
shortest
Parameters:
String[]
Returns:
String
Method signature:
String shortest(String[] codewords)
(be sure your method is public)

Notes

  • Besides flipping bits, possible transmission errors include deleting bits or adding spurious bits, so the sender cannot count on the receiver agreeing on the number of bits that have been transmitted.
  • You may assume that transmission errors will not occur during the synchronizing sequence.

Constraints

  • codewords contains between 3 and 26 elements, inclusive.
  • Each element of codewords contains between 1 and 25 characters, inclusive.
  • Every character is either '0' or '1' (quotes for clarity only).
  • No codeword is a prefix of another codeword.
  • For every proper prefix P of some codeword, P0 is a prefix of some codeword and P1 is a prefix of some codeword, where P0 and P1 are the concatenations of P with the characters '0' and '1', respectively.

Examples

  1. { "0", "10", "11" }

    Returns: "0"

    The example above.

  2. { "0", "100", "101", "11" }

    Returns: "00"

    "0" is not a synchronizing sequence, because if the receiver thinks he has received a "1", then after the "0" he will still be waiting for another bit. "1" is not a synchronizing sequence, because if the receiver thinks he is at the beginning of a codeword, then after the "1" he will still be waiting for another one or two bits. "00" is a synchronizing sequence: if the receiver thinks he is at the beginning of a codeword, then he decodes a "0" followed by a second "0"; if he thinks he has received a "1", then he decodes a "100"; and if he thinks he has received a "10", then he decodes a "100" followed by a "0".

  3. { "00", "01", "10", "11" }

    Returns: "NONE"

  4. { "00", "01", "100", "1010", "10110", "10111", "11" }

    Returns: "00100"

  5. { "1000001", "00", "110", "101", "010", "10001", "1000000001", "10000000001", "100000001", "10000001", "1001", "10000000000001", "1000000000001", "100000000001", "100001", "111", "100000000000000001", "1000000000000001", "100000000000001", "011", "1000000000000000100", "1000000000000000110", "1000000000000000000", "1000000000000000001", "1000000000000000111", "1000000000000000101" }

    Returns: "0000000000000000001000000000000000101"

  6. { "00", "01", "100", "101", "11" }

    Returns: "100"

  7. { "00000","00001","00010","00011","00100","00101","00110","00111", "01000","01001","01010","01011","01100","01101","01110","01111", "1000","1001","1010","1011","1100","1101","1110","11110","11111" }

    Returns: "1000100010001000"

  8. { "000000","000001","00001","0001","001","01","10","110","1110", "11110","111110","1111110","1111111" }

    Returns: "0110"

  9. { "00","0111","0101","0110","0100","11","1000","1010","1011","1001" }

    Returns: "NONE"

  10. { "00","0111","0101","0110","11","1000","1010","1011","1001", "010000","010011","010010","010001" }

    Returns: "NONE"

  11. { "011","010","00111","00110","00100","00101","000", "100","101","1101","1110","1100","1111" }

    Returns: "00101100"

  12. { "0","11","100","1011","10100","101011","1010100","10101011","101010100","1010101011", "10101010100","101010101011","1010101010100","10101010101011","101010101010100", "1010101010101011", "10101010101010100","101010101010101011","1010101010101010100", "10101010101010101011","101010101010101010100","1010101010101010101011", "10101010101010101010100","101010101010101010101011","1010101010101010101010100", "1010101010101010101010101" }

    Returns: "00"

  13. { "01","1","00" }

    Returns: "1"

  14. { "00000", "00001", "00011", "00010", "0010", "00110", "00111", "0100", "01010", "01011", "0111", "01100", "01101", "1011", "1001", "10100", "10000", "10101", "10001", "1111", "11100", "11101", "11000", "11011", "11010", "11001" }

    Returns: "111001000100010"

  15. { "0", "11", "101", "1000", "10010", "100111", "1001101", "10011001", "100110000", "1001100010", "10011000110", "100110001111", "1001100011101", "10011000111001", "100110001110001", "1001100011100000", "10011000111000010", "100110001110000110", "1001100011100001110", "10011000111000011111", "100110001110000111101", "1001100011100001111001", "10011000111000011110001", "100110001110000111100001", "1001100011100001111000000", "1001100011100001111000001" }

    Returns: "01000"

  16. { "1111", "0101", "1010", "1100", "0011", "1001", "0110", "1011", "1101", "0111", "1110", "0001", "1000", "0010", "0100", "00000", "00001" }

    Returns: "1000010000100001"

  17. { "10", "000", "011", "001", "010", "1100", "1101", "1111", "1110" }

    Returns: "01010"

  18. { "0000000000", "0000000001", "000000001", "00000001", "0000001", "000001", "00001", "1111", "0001", "1110", "1101", "1011", "0111", "0010", "0100", "1000", "0011", "1100", "0101", "1010", "1001", "0110" }

    Returns: "10000001"

  19. { "111", "110", "0000", "0001", "010", "011", "1000", "1001", "0011", "0010", "10100", "10101", "10110", "10111" }

    Returns: "110010010"

  20. { "00001", "0001", "001", "01", "1", "00000" }

    Returns: "1"

  21. { "0000", "0001", "0010", "0011", "0100", "0101", "0110", "0111", "1000", "1001", "1010", "1011", "1100", "1101", "1110", "1111" }

    Returns: "NONE"

  22. {"00", "1", "010", "0110", "01110", "011110", "0111110", "01111110", "011111110", "0111111110", "01111111110", "011111111110", "0111111111110", "01111111111110", "011111111111110", "0111111111111110", "01111111111111110", "011111111111111110", "0111111111111111110", "01111111111111111110", "011111111111111111110", "0111111111111111111110", "01111111111111111111110", "011111111111111111111110", "0111111111111111111111110", "0111111111111111111111111"}

    Returns: "111111111111111111111111"

  23. {"00", "100000000000000000000", "110", "101", "010", "111", "011", "1001", "10001", "100001", "1000001", "10000001", "100000001", "1000000001", "10000000001", "100000000001", "1000000000001", "10000000000001", "100000000000001", "10000000000000010", "10000000000000001", "100000000000000001", "1000000000000000001", "10000000000000000001", "100000000000000000001", "10000000000000011"}

    Returns: "10000000000000010000000000000010"

  24. {"00", "100000000000000", "110", "101", "010", "111", "011", "1001", "10001", "100001", "1000001", "10000001", "100000001", "1000000001", "10000000001", "100000000001", "1000000000001", "10000000000001", "100000000000001"}

    Returns: "0000000000000010100000000000000"

  25. {"00", "10000000000000000", "110", "101", "010", "111", "011", "1001", "10001", "100001", "1000001", "10000001", "100000001", "1000000001", "10000000001", "100000000001", "1000000000001", "10000000000001", "100000000000001", "1000000000000001", "10000000000000001"}

    Returns: "00000000000000001010000000000000000"

  26. {"00", "1000000000000000000", "110", "101", "010", "111", "011", "1001", "10001", "100001", "1000001", "10000001", "100000001", "1000000001", "10000000001", "100000000001", "1000000000001", "10000000000001", "100000000000001", "1000000000000001", "10000000000000001", "100000000000000001", "1000000000000000001"}

    Returns: "000000000000000000101000000000000000000"

  27. {"00", "100000000000000000000", "110", "101", "010", "111", "011", "1001", "10001", "100001", "1000001", "10000001", "100000001", "1000000001", "10000000001", "100000000001", "1000000000001", "10000000000001", "100000000000001", "1000000000000001", "10000000000000001", "100000000000000001", "1000000000000000001", "10000000000000000001", "100000000000000000001"}

    Returns: "0000000000000000000010100000000000000000000"

  28. {"00", "100000000000000000000", "110", "101", "1001", "10001", "010", "100001", "111", "011", "1000001", "10000001", "100000001", "1000000001", "10000000001", "100000000001", "1000000000001", "10000000000001", "100000000000001", "1000000000000001", "10000000000000001", "100000000000000001", "1000000000000000001", "10000000000000000001", "100000000000000000001"}

    Returns: "0000000000000000000010100000000000000000000"

  29. {"00", "100000000000000000000", "010", "110", "111", "101", "1001", "10001", "011", "100001", "1000001", "10000001", "100000001", "1000000001", "10000000001", "100000000001", "1000000000001", "10000000000001", "100000000000001", "1000000000000001", "10000000000000001", "100000000000000001", "1000000000000000001", "100000000000000000010", "100000000000000000001", "100000000000000000011"}

    Returns: "1000000000000000000100000000000000000010"

  30. {"000", "100", "010", "0110", "01110", "011110", "11", "101", "0111110", "001", "01111110", "011111110", "0111111110", "01111111110", "011111111110", "0111111111110", "01111111111110", "011111111111110", "0111111111111110", "01111111111111110", "011111111111111110", "0111111111111111110", "0111111111111111111"}

    Returns: "111111111111111111000111111111111111111"

  31. {"000", "100", "010", "0110", "01110", "011110", "0111110", "11", "101", "001", "01111110", "011111110", "0111111110", "01111111110", "011111111110", "0111111111110", "01111111111110", "011111111111110", "0111111111111110", "01111111111111110", "011111111111111110", "0111111111111111110", "01111111111111111110", "011111111111111111110", "011111111111111111111"}

    Returns: "1111111111111111111100011111111111111111111"

  32. {"00", "100000000000000000000", "110", "111", "101", "010", "011", "1001", "10001", "100001", "1000001", "10000001", "100000001", "1000000001", "10000000001", "100000000001", "1000000000001", "10000000000001", "100000000000001", "1000000000000001", "10000000000000001", "100000000000000001", "1000000000000000001", "10000000000000000001", "100000000000000000001"}

    Returns: "0000000000000000000010100000000000000000000"

  33. {"000", "100", "010", "0110", "11", "101", "01110", "001", "011110", "0111110", "01111110", "011111110", "0111111110", "01111111110", "011111111110", "0111111111110", "01111111111110", "011111111111110", "0111111111111110", "01111111111111110", "011111111111111110", "0111111111111111110", "01111111111111111110", "011111111111111111110", "011111111111111111111"}

    Returns: "1111111111111111111100011111111111111111111"

  34. {"00", "1000000000000000000", "110", "111", "010", "101", "1001", "011", "10001", "100001", "1000001", "10000001", "100000001", "1000000001", "10000000001", "100000000001", "1000000000001", "10000000000001", "100000000000001", "1000000000000001", "10000000000000001", "100000000000000001", "1000000000000000001"}

    Returns: "000000000000000000101000000000000000000"

  35. {"00", "100000000000000000000", "110", "101", "1001", "10001", "010", "100001", "011", "111", "1000001", "10000001", "100000001", "1000000001", "10000000001", "100000000001", "1000000000001", "10000000000001", "100000000000001", "1000000000000001", "10000000000000001", "100000000000000001", "1000000000000000001", "10000000000000000001", "100000000000000000001"}

    Returns: "0000000000000000000010100000000000000000000"

  36. {"000", "1000000000", "1100", "0100", "0110", "1010", "1110", "0010", "1111", "1011", "0111", "1101", "0011", "0101", "1001", "10001", "100001", "1000001", "10000001", "100000001", "1000000001"}

    Returns: "00000000010010000000000101000000000"

  37. {"000", "100", "010", "0110", "001", "01110", "011110", "0111110", "11", "101", "01111110", "011111110", "0111111110", "01111111110", "011111111110", "0111111111110", "01111111111110", "011111111111110", "0111111111111110", "01111111111111110", "011111111111111110", "0111111111111111110", "01111111111111111110", "0111111111111111111100", "011111111111111111111", "0111111111111111111101"}

    Returns: "111111111111111111100011111111111111111111"

  38. {"00000", "1000", "1100", "1010", "01000", "00100", "00010", "0110", "00110", "11100", "01010", "0111", "11110", "111110", "1101", "11101", "01001", "00001", "00011", "001110", "1011", "1001", "00101", "001111", "111111", "01011"}

    Returns: "1011111000110"

  39. { "100", "101", "11", "0" }

    Returns: "00"

    "0" is not a synchronizing sequence, because if the receiver thinks he has received a "1", then after the "0" he will still be waiting for another bit. "1" is not a synchronizing sequence, because if the receiver thinks he is at the beginning of a codeword, then after the "1" he will still be waiting for another one or two bits. "00" is a synchronizing sequence: if the receiver thinks he is at the beginning of a codeword, then he decodes a "0" followed by a second "0"; if he thinks he has received a "1", then he decodes a "100"; and if he thinks he has received a "10", then he decodes a "100" followed by a "0".

  40. { "000", "100", "010", "0110", "11000", "1110", "11010", "110010000000", "110011", "001", "110010100", "11001011", "11001001", "11001000100", "1100100001", "1111", "11011", "1100101010", "110010000010", "110010000001", "0111", "110010000011", "1100101011", "101", "1100100011", "11001000101"}

    Returns: "010011100000111000"

  41. { "1000001", "00", "110", "101", "010", "10001", "1000000001", "10000000001", "100000001", "10000001", "1001", "10000000000001", "1000000000001", "100000000001", "100001", "111", "100000000000000001", "1000000000000001", "100000000000001", "011", "1000000000000000100", "1000000000000000110", "1000000000000000000", "1000000000000000001", "1000000000000000111", "1000000000000000101" }

    Returns: "0000000000000000001000000000000000101"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: