April 18, 2020 2020 TCO Algorithm Round 1A
AveragePrice
Let’s process the prices one by one. For each of them, we check if we have seen it before and if not, we add it to the sum.
For example, for { 10, 20, 10 }:
- We see 10. We didn’t ever see 10 before. So add 10 to sum.
- We see 20. We didn’t ever see 20 before. So add 20 to sum.
- We see 10. We have seen it before. So do not add 10 to sum.
- Sum = 30
To check if we have seen a number before, we use for loop on previous seen elements.
public double nonDuplicatedAverage(int[] prices) {
Arrays.sort(prices);
int last = prices[0];
double sum = prices[0];
int count = 1;
for (int i = 1; i < prices.length; i++)
if (prices[i] > prices[i - 1]) {
sum += prices[i];
count++;
}
return sum / count;
}
def nonDuplicatedAverage(self, prices):
prices = set(prices)
return 1. * sum(prices) / len(prices)
BlindBoxSets
Suppose we are in the middle of the routine. For each item let’s keep how many times we’ve seen it. If we have seen an item more than numSets times, consider we have seen it numSets times.
This way, we can check if the state is final. There is only one final state where the count of each of the items equals numSets.
The transactions between states are simple. For each state, we uniformly at random choose an item and if its number of occurrences is less than numSets, we jump to the state which has this item one time more.
This leads to a slow solution.
To make it faster we should change the definition of states. We keep tuple (a[0], a[1], a[2], a[3], …, a[numSets]). a[i] shows how many types of items like x that there that number of occurrences of x.
def solve(self, distribution):
distribution = tuple(distribution)
if distribution not in self.memo:
if distribution[-1] == self.collectionSize:
self.memo[distribution] = 0
else:
rhs = 0
for type_drawn in range(self.numSets):
if distribution[type_drawn] == 0: continue
prob = 1. * distribution[type_drawn] / self.collectionSize
new_distribution = list(distribution)
new_distribution[type_drawn] -= 1
new_distribution[type_drawn+1] += 1
rhs += prob * self.solve(new_distribution)
prob_remains = 1. * distribution[-1] / self.collectionSize
# E = 1 + prob_remains*E + rhs
self.memo[distribution] = (rhs + 1.) / (1 - prob_remains)
return self.memo[distribution]
def expectedPurchases(self, numSets, collectionSize):
self.memo = {}
self.numSets = numSets
self.collectionSize = collectionSize
distribution = [collectionSize] + [0] * numSets
return self.solve(distribution)
double[][][][] expected = new double[51][51][51][51];
int S;
int N;
private double solve(int n1, int n2, int n3, int n4) {
if (expected[n1][n2][n3][n4] > 0) return expected[n1][n2][n3][n4];
if (n1 == 0 && n2 == 0 && n3 == 0 && n4 == 0) return 0;
double ret = 1;
int sum = 0;
if (n1 > 0) {
sum += n1;
ret += (1.0 * n1 / N) * solve(n1 - 1, n2, n3, n4);
}
if (n2 > 0) {
sum += n2;
ret += (1.0 * n2 / N) * solve(n1 + 1, n2 - 1, n3, n4);
}
if (n3 > 0) {
sum += n3;
ret += (1.0 * n3 / N) * solve(n1, n2 + 1, n3 - 1, n4);
}
if (n4 > 0) {
sum += n4;
ret += (1.0 * n4 / N) * solve(n1, n2, n3 + 1, n4 - 1);
}
ret *= N;
ret /= sum;
// System.out.println(n1 + "," + n2 + "," + n3 + "," + n4 + ": " + ret);
return expected[n1][n2][n3][n4] = ret;
}
public double expectedPurchases(int numSets, int collectionSize) {
N = collectionSize;
S = numSets;
if (numSets == 4) return solve(0, 0, 0, collectionSize);
if (numSets == 3) return solve(0, 0, collectionSize, 0);
if (numSets == 2) return solve(0, collectionSize, 0, 0);
if (numSets == 1) return solve(collectionSize, 0, 0, 0);
return 0;
}
ThreeNeighbors
There are several ways to solve this problem. Let’s find a pattern and solve the problem. Consider the following table:
…………………………………………..
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
…………………………………………..
It has width = 50. Exactly 96 cells are there that will become alive in the next turn. If we repeat this pattern we can achieve 50 // 3 * 96 such cells that is more than 500.
The remaining part is to handle when N is not divisible by 96. We add something like this:
…………………………………………..
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
…………………………………………..
It has 19 X’s and thus it creates (19 – 2) * 2 cells that will become alive in the next turn. So we handled when N is even.
Just to handle when N is odd, we add this:
XX
X.
public String[] construct(int N) {
ArrayList<String> ret = new ArrayList<String>();
while (N >= 96) {
ret.add("..................................................");
ret.add("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX");
ret.add("..................................................");
N -= 96;
}
ret.add("..................................................");
String s = "XX";
while (N > 1) {
s += "X";
N -= 2;
}
while (s.length() < 50) s += ".";
ret.add(s);
ret.add("..................................................");
if (N == 1) {
ret.add("..................................................");
ret.add("XX................................................");
ret.add("X.................................................");
}
return ret.toArray(new String[0]);
}
Guest Blogger
