November 26, 2019 TCO19 Algorithm Semi Final 2 Editorials
DiverseFlowers
First, let’s solve this problem for K=3.
We get an upper bound of min(#reds, #blues, #greens, #bigs, #smalls, N/K).
Once we know the answer, we can try to reconstruct it by taking some valid set of three flowers, and checking if the upper bound decreases by exactly one. We can show that at least one such move always exists.
To solve the problem with arbitrary K, we can notice that in any bouquet, there are three flowers that satisfy the condition. Thus, we can first solve this problem for K=3, then pad the remaining flowers to get arbitrary K.
Sample code below:
int score(int cnt[]) {
assert(cnt.length == 6);
for(int x : cnt) {
if(x < 0) {
return -2;
}
}
int tmp = min(cnt[0] + cnt[3], min(cnt[1] + cnt[4], cnt[2] + cnt[5])); // colors
return min(tmp, min(cnt[0] + cnt[1] + cnt[2], cnt[3] + cnt[4] + cnt[5])); // big/small
}
public String[] solve(String S, int K) {
int[] cnt = new int[6];
for(int i = 0; i < S.length(); ++i) {
cnt[which(S.charAt(i))]++;
}
int current = score(cnt);
int should_be_answer = min(current, S.length() / K);
List<String> answer = new ArrayList();
String[] moves = {"RGb", "RgB", "rGB", "Rgb", "rGb", "rgB"};
while(current >= 1 && K * (answer.size() + 1) <= S.length()) {
for(String move : moves) {
int[] maybe = cnt.clone();
for(int i = 0; i < move.length(); ++i) {
maybe[which(move.charAt(i))]--;
}
if(score(maybe) == current - 1) {
answer.add(move);
current -= 1;
cnt = maybe.clone();
break;
}
}
}
String[] ret = new String[answer.size()];
for(int i = 0; i < answer.size(); ++i) {
ret[i] = answer.get(i);
while(ret[i].length() < K) {
for(int j = 0; j < 6; ++j) {
if(cnt[j] >= 1) {
cnt[j]--;
ret[i] += alphabet.charAt(j);
break;
}
}
}
}
assert(should_be_answer == ret.length);
return ret;
}
BagsOfNumbers
There are two parts of this problem. The first is finding the sprague grundy values of each bag, then, we just need to count the number of subsets of these grundy values that have nonzero xor.
For the first, we can write a brute force and notice some patterns. It turns out the grundy value is equal to the maximum number of moves we can make in a single bag. We can prove this using induction on the grundy value. Clearly this is true for bags with grundy value zero. Now, let’s suppose it’s true for all grundy values < k, and consider a bag that we can do k moves on. We need to show that we can reach a state with i < k moves for all i, and we can’t reach a state with k moves. The first statement is true, since if we have k moves we can do, we can take k-i of those subsets of numbers and reach a state with at most i moves. The second statement is true, since if we could do a move to reach another state with k moves, this is a contradiction on the fact that the original state had at most k moves. Thus, this proves the claim.
The exact formula can be written as #4s + (#1s + #3s + 2*#2s +2*(min(#1s, #3s))) / 4.
For the second, we can use guassian elimination If we consider the numbers as bit vectors in F2, we want to find the size of the nullspace. We can use the rank-nullity theorem to reduce the problem of finding the rank of the set of vectors.
class BagsOfNumbers:
def wonByAlice(self, n, a, b, c, d):
def f(ax, bx, cx, dx):
if ax > cx:
return f(cx, bx, ax, dx)
return ax + ((bx + ((cx - ax) / 2)) / 2) + dx
nim = [f(*g) for g in zip(a,b,c,d)]
res = []
for i in range(n):
for j in res:
nim[i] = min(nim[i], j^nim[i])
if nim[i]:
res.append(nim[i])
res = sorted(res)[::-1]
return (1<<n) - (1<<(n-len(res)))
FourDistinctDigits
The solution uses randomization. We prove a solution always exists as follows.
Consider numbers with only zeros and ones of length D. Consider the remainders of these numbers modulo N. If any of these remainders coincide, then we can subtract these two numbers to get a number with digits 0, 1, B-2, and B-1 that is divisible by N.
The hard part now is to find any two numbers whose remainders coincide. This can be done randomly. Due to the birthday paradox, we can expect we will need to generate about sqrt(N) candidates before getting a collision. This is fast enough since N <= 10^11, and in fact, the worst case is hard to reach in practice.
It is important here to take the difference, and not the sum, since finding a collision where x=y is different from finding a collision when x+y = 0 mod n.
import java.util.*;
import java.math.*;
public class FourDistinctDigits {
Random rnd;
long hi, lo, hi2, lo2;
void newRandomBits(int D) {
hi = rnd.nextInt(1<<30);
hi <<= 30;
hi |= rnd.nextInt(1<<30);
lo = rnd.nextInt(1<<30);
lo <<= 30;
lo |= rnd.nextInt(1<<30);
if (D <= 60) {
hi = 0;
lo &= (1L << D) - 1;
} else {
hi &= (1L << (D-60)) - 1;
}
}
long getRemainder(long N, int B) {
long remainder = 0;
for (int b=59; b>=0; --b) remainder = (B * remainder + ((hi >> b) & 1)) % N;
for (int b=59; b>=0; --b) remainder = (B * remainder + ((lo >> b) & 1)) % N;
return remainder;
}
String constructSolution(int D, int B) {
int[] d1 = new int[120];
int[] d2 = new int[120];
for (int d=0; d<60; ++d) d1[d] = (int)((lo >> d) & 1);
for (int d=0; d<60; ++d) d1[60+d] = (int)((hi >> d) & 1);
for (int d=0; d<60; ++d) d2[d] = (int)((lo2 >> d) & 1);
for (int d=0; d<60; ++d) d2[60+d] = (int)((hi2 >> d) & 1);
boolean shouldSwap = false;
for (int d=119; d>=0; --d) {
if (d1[d] > d2[d]) break;
if (d1[d] < d2[d]) { shouldSwap = true; break; }
}
if (shouldSwap) for (int d=0; d<120; ++d) { int t = d1[d]; d1[d] = d2[d]; d2[d] = t; }
for (int d=0; d<D; ++d) {
d1[d] -= d2[d];
if (d1[d] < 0) { d1[d] += B; --d1[d+1]; }
}
String allDigits = "";
for (int d=0; d<10; ++d) allDigits += (char)('0'+d);
for (int d=0; d<26; ++d) allDigits += (char)('A'+d);
for (int d=0; d<26; ++d) allDigits += (char)('a'+d);
String answer = "";
boolean printed = false;
for (int d=119; d>=0; --d) {
if (d1[d] == 0 && !printed) continue;
printed = true;
answer += allDigits.charAt( d1[d] );
}
while (answer.length() < D) answer += '0';
return answer;
}
public String find(long N, int D, int B) {
rnd = new Random();
HashMap<Long,Long> HI = new HashMap<Long,Long>();
HashMap<Long,Long> LO = new HashMap<Long,Long>();
while (true) {
newRandomBits(D);
long remainder = getRemainder(N,B);
if (HI.containsKey(remainder)) {
hi2 = HI.get(remainder);
lo2 = LO.get(remainder);
if (hi == hi2 && lo == lo2) continue;
System.out.println("Hash table size: " + HI.size());
return constructSolution(D,B);
} else {
HI.put(remainder,hi);
LO.put(remainder,lo);
}
}
}
}
Harshit Mehta
Sr. Community Evangelist
