Interference
Time limit2sMemory limit256 MB
For each received n-bit string (n up to 34) and target polynomial hash, find a string within minimum Hamming distance whose hash matches, and report the flipped bit indices.
- Level
Hard8 of 10
- Topics
- Math, Dynamic programming, Brute force, Bit manipulation
- Solved
- No attempts yet
Problem
When informational messages are transmitted over communication channels, errors often occur, and the received message turns out to differ from the sent one. Various error-detecting codes and correcting codes that can fix the most likely errors are used to deal with this. One method of error detection is to transmit a hash, a checksum, together with the message, which can be computed for the received message and compared with the checksum of the original message.
In this problem you must implement error correction in the received message using a checksum computed as a polynomial hash. Suppose that some bit string is transmitted, stored as an n-bit binary number. If the bits of the number are numbered from zero starting with the least significant bit, then the polynomial hash is computed by the following formula:
h(a) = (a0 + a1t + a2t 2 + ... + a**i t i + ... + a**n − 1t n − 1) mod M, where a**i is the i-th bit of the number.
In this problem always t = 239, M = 109 + 7.
The receiving side gets a possibly corrupted message and the polynomial hash computed for the sent message. The hash itself is assumed to be transmitted without errors. Error correction is performed by the maximum likelihood method: it is necessary to find a message that differs from the received one in the minimum number of bits and has a hash equal to the received one.
Input
The first line contains a single number K (1 ≤ K ≤ 10), the number of transmitted messages. Each of the following K lines contains a description of a transmitted message: three integers n (1 ≤ n ≤ 34), the length of the message, m (0 ≤ m < 2n ), a number whose binary notation defines the bit string of the received message, and h (0 ≤ h < 109+7), the received hash.
The total length of all transmitted messages in one test does not exceed 100.
Output
For each message, on a separate line, output the single number «−1» if this message cannot be decoded. Otherwise, first output the number d, the minimum number of errors, and then on the same line d numbers, the indices of the bits that were corrupted during transmission. If there are several possible answers, output any of them.