SignalIntelligence
SRM 480 · 2009-11-12 · by dolphinigle
SRM 480 · 2009-11-12 · by dolphinigle · Encryption/Compression, Greedy, Math, Sorting
Problem Statement
Problem Statement
Gogo has been hired by the newly founded TopCoder Security Agency (TSA) and has been tasked to encrypt a signal code generated by a radar.
The signal will consist of several positive integers. The order of integers within the signal is not important and therefore should not be preserved during encryption. However, there may be duplicate integers, and the number of occurrences of each integer is important and must be preserved during encryption.
Gogo's idea is to encrypt these integers into a String that consists only of digits '1' and '0'. The encryption scheme is as follows:
Given integers to encrypt inint[] numbers, return the length of the shortest string that encrypts them and can be obtained according to the scheme described above. It is guaranteed that this length will not exceed 2^62.
The signal will consist of several positive integers. The order of integers within the signal is not important and therefore should not be preserved during encryption. However, there may be duplicate integers, and the number of occurrences of each integer is important and must be preserved during encryption.
Gogo's idea is to encrypt these integers into a String that consists only of digits '1' and '0'. The encryption scheme is as follows:
- Start with an infinite String consisting solely of '0' characters. The characters within the string are indexed from left to right 1, 2, 3, ... .
- For each input integer X in the signal, Gogo will allocate it within the string. To do this, he will select an index 2^p, where p is a non-negative integer that he may choose arbitrarily, but in such way that characters at indices between 2^p and 2^p + X - 1, inclusive, are all equal to '0'. The allocating procedure consists of replacing all these characters with '1's. This newly created sequence of consecutive '1' characters is said to represent the allocated integer X.
- In order to allow unique decryption, the following property must hold after all numbers from the signal are allocated. For every two integers from the input signal, there must be at least one '0' character between the sequences of '1's that represent these integers.
Given integers to encrypt in
Constraints
- numbers will contain between 1 and 50 elements, inclusive.
- Each element of numbers will be between 1 and 1,000,000,000, inclusive.
- The answer will not exceed 2^62.
Examples
0)
{1,2,3}
Returns: 8
The string "11011101" encrypts the given numbers and has a length of 8. There is no shorter string that encrypts these numbers.
1)
{4,4,2,2}
Returns: 19
The elements in numbers might not be distinct.
2)
{1000000000,1000000000,1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,1000000000,1000000000,
1000000000,1000000000,1000000000,1000000000,1000000000}
Returns: 281475976710655
The answer may be very big, but it will not exceed 2^62.
3)
{1,3,7,15,31,63,127,255,511,1023,2047}
Returns: 4094
4)
{1000000000,1}
Returns: 1000000003
Submissions are judged against all 121 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SignalIntelligence with a public method long long encrypt(vector<int> numbers) · 121 test cases · 2 s / 256 MB per case