May 23, 2022 TCO22 Round 2A Editorial
PlugStuffIn
Whenever we have an unplugged power cord, we can always plug it into a socket that has power: we lose exactly one powered socket (the one into which we plugged the cord) and we gain at least one powered socket (those offered by our power cord).
Thus, we can always proceed as follows:
- Plug in all the power cords.
- Count all available sockets (sum of all sockets, including the one in the wall, minus the number of cords).
- Count all devices and find out whether you have enough sockets for them.
- If yes, plug the devices into sockets arbitrarily.
public int[] plug(int[] gadgets) {
// count everything
int N = gadgets.length;
int cordCount = 0, socketCount = 0;
for (int g : gadgets) if (g > 0) { ++cordCount; socketCount += g; }
int maxPlugged = socketCount - cordCount + 1;
int deviceCount = N - cordCount;
if (deviceCount > maxPlugged) return new int[0];
// plug in all cords
int[] answer = new int[N];
int lastSocket = N;
int[] available = new int[N+1];
for (int n=0; n<N; ++n) available[n] = gadgets[n];
available[N] = 1;
for (int n=0; n<N; ++n) if (gadgets[n] > 0) {
answer[n] = lastSocket;
--available[lastSocket];
lastSocket = n;
}
// plug in all the devices
int nextCord = 0;
for (int n=0; n<N; ++n) if (gadgets[n] == 0) {
while (available[nextCord] == 0) ++nextCord;
answer[n] = nextCord;
--available[nextCord];
}
return answer;
}
RearrangeAndIncrement
Rearranging can sometimes make the number of digits smaller. Notably, any 10^k can be rearranged to 1.
Rearranging can never make the number of digits larger. The only way to increment the number of digits is to produce a number that is almost 10^k and then use an increment operation to get it over 10^k.
We can set a k-digit number to a number consisting of k 9s in O(k) operations as follows: while it’s not of that form, set the last digit to 9 (this is an increment or an identity, so it’s always allowed – identity is an rearrangement) and then rearrange digits into descending order.
We can start any construction by doing this, then doing +1 to get a power of 10, and then rearranging that into 1. (This isn’t necessary, but it’s an easy simplification. Now we only need to go from 1 to an arbitrary Y.)
One way to proceed is as follows:
We will start with a technical trick that will make the construction simpler: If Y is a single digit, we produce it directly. If Y ends in a 0, we will produce Y-1 and then add 1 as the last step. Below, assume Y has at least two digits and doesn’t end in a zero. Let k be the number of digits in Y.
We can repeat the above procedure (set the number to all nines, then add 1) to turn 1 into 10^(k-1). Now we have the right number of digits, we just need to set them to their correct values. One way to do that is to set the last digit to the desired leading digit, rearrange that to the front, and then rotate and set all other digits (changing the original initial 1 to the desired non-zero last digit in the last step).
ThreeWaySplit
Split the items into two halves, each with at most 12 items.
For each half, iterate over all 3^size ways to split it. For each difference (Alice – Bob), remember the largest possible sum (Alice + Bob) and the split that produced it.
Now, iterate over all differences D that are possible in the first half. In order to have Alice = Bob in the end, if we choose a split with difference D for the first half, we must pair it with a split with difference -D for the second half. In both cases we take the remembered one to maximize the total sum Alice and Bob get (which is the same as maximizing what each of them gets).
The time complexity of this solution is O(3^(N/2)) expected time if we use hashmaps to store information about each half of the input.
void solveHalf(int[] half, HashMap<Long, Long> bestSum, HashMap<Long, Integer> bestPattern) {
int[] pow3 = new int[] { 1, 3, 9, 27, 81, 243, 729, 2187, 6561,
19683, 59049, 177147, 531441 };
int H = half.length;
for (int pattern = 0; pattern < pow3[H]; ++pattern) {
long sum = 0, diff = 0;
int tmp = pattern;
for (int h=0; h<H; ++h) {
int curr = tmp % 3;
tmp /= 3;
if (curr == 0) continue;
if (curr == 1) diff += half[h];
if (curr == 2) diff -= half[h];
sum += half[h];
}
if (bestSum.containsKey(diff)) {
long bestSoFar = bestSum.get(diff);
if (bestSoFar >= sum) continue;
bestSum.put(diff,sum);
bestPattern.put(diff,pattern);
} else {
bestSum.put(diff,sum);
bestPattern.put(diff,pattern);
}
}
}
public String split(int[] loot) {
int N = loot.length;
int H1 = N/2, H2 = N - H1;
int[] half1 = new int[H1];
int[] half2 = new int[H2];
for (int h=0; h<H1; ++h) half1[h] = loot[h];
for (int h=0; h<H2; ++h) half2[h] = loot[H1 + h];
HashMap<Long, Long> bestSum1 = new HashMap<Long, Long>();
HashMap<Long, Integer> pattern1 = new HashMap<Long, Integer>();
solveHalf(half1, bestSum1, pattern1);
HashMap<Long, Long> bestSum2 = new HashMap<Long, Long>();
HashMap<Long, Integer> pattern2 = new HashMap<Long, Integer>();
solveHalf(half2, bestSum2, pattern2);
long bestSol = 0;
int bestp1 = 0, bestp2 = 0;
for (long diff1 : bestSum1.keySet()) {
if (!bestSum2.containsKey(-diff1)) continue;
long sum = bestSum1.get(diff1) + bestSum2.get(-diff1);
if (sum <= bestSol) continue;
bestSol = sum;
bestp1 = pattern1.get(diff1); bestp2 = pattern2.get(-diff1);
}
String answer = "";
String who = "CAB";
for (int h=0; h<H1; ++h) { answer += who.charAt(bestp1%3); bestp1 /= 3; }
for (int h=0; h<H2; ++h) { answer += who.charAt(bestp2%3); bestp2 /= 3; }
return answer;
}
misof
