TopCoder problem "SignalIntelligence" used in SRM 480 (Division II Level Three)



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:

  • 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.
After all numbers are allocated within the string properly, the '1' character with the largest index is found and all '0' characters to the right of it are removed. The obtained finite string is the result of the encryption procedure.



Given integers to encrypt in int[] 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.
 

Definition

    
Class:SignalIntelligence
Method:encrypt
Parameters:int[]
Returns:long
Method signature:long encrypt(int[] numbers)
(be sure your method is public)
    
 

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.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=11059

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=14159&pm=11059

Writer:

dolphinigle

Testers:

PabloGilberto , ivan_metelsky , it4.kp

Problem categories:

Encryption/Compression, Greedy, Math, Sorting