システム開発試合の難問
最近トップコーダーと言う会社が提供する試合に参加して面白い問題に挑戦しました。
ジャンルは並べ替える事と最適化だと思います。
Basically, solving this problem involved determining several nuances and how to handle them in code.
The problem statement was: given a list of integers, determine the length of the shortest encryption string for them. The encryption string would result from: for each number n, generate a string of n ones and insert this string somewhere in the final string at an index that is a power of 2 (i.e. 2^p). In addition, there must be at least one 0 between any two strings of ones. Lastly, the last number need not be followed by any zeroes. Basically, the algorithm involves two steps: 1. determine which of the numbers will be last, which depends on the components of numbers. 2. determine the length of the string obtained by placing all other numbers in ascending order and then the last number. The reason for the first step is that which number will be last depends on which number causes the fewest zeroes to be wasted when it is in the last position (in some cases, this could be the smallest number, in some cases, this could be the largest). For example, in the case of {1,2,3}, 1 is the number which is placed at the end. However, for {2,4}, 4 is the number which should be placed at the end (1101111 vs 111100011). The second step is based on the fact that, given the last element is chosen, there is no benefit to placing the other elements in any order other than ascending. This is because by swapping a smaller and longer number, we could save 0s in the smaller number's slot, but we would waste as many more in the larger number's slot. e.g. swap 1 and 2 in 1001100->1101000.
Note that the getNextInd method involves two possible increments of the exponent. The first increment could occur, because the log method returns a double. This double might be an approximation of an integer such as 3.999999999999999 for 4. In this case truncating the log result would obtain 3, when the actual integral log value is 4. The second reason for an increment is that the earliest possible index value (ind+val+1), which accounts for the number of 1s and 1 zero, may not be a power of 2. If this is the case, we need to find the log base 2 (a non-integer), take its integral component, increment this, and take two to the power of this incremented exponent.
Note that the encrypt method tries every possible last index. This is feasible, since the code in the inner loop will then be executed O(50*50) times. As the inner loop is O(62) (for the logarithm of 2^62), the number of executions of the inner loop is O(20000) which easily runs within the 2 second time limit.
The code is as follows:
#include
#include
#include
#include
#include
class SignalIntelligence{
public:
long long encrypt(vector
int len = numbers.size();
long long minEnd = (1LL<<62)+1LL;
sort(numbers.begin(),numbers.end());
for(int i=0;i
logInt++;
}
long long powVal = (1LL<
*1:long long)lastEl-1LL);
if(ind
