2020 Humblefool Cup Prelims Editorials

ScoringJudges 

Used as: Division One - Level One:

Sort scores in non-decreasing order. Take the average of first 1/3, and also for the last 1 / 3, and middle elements and sum up.

def overallScore(self, individualScores):
individualScores = list(individualScores)
individualScores.sort()
n = len(individualScores)
t = len(individualScores)/3
fhalf = 0
shalf = 0
for i in range(t):
fhalf += individualScores[i]
shalf += individualScores[n-i-1]
mhalf = sum(individualScores) - fhalf - shalf
fhalf /= float(t)
shalf /= float(t)
mhalf /= float(n - 2*t)

return fhalf + shalf + mhalf

NonSimilarTriangles 

Used as: Division One - Level Two:

For each triple of sticks of length x, y, z (x <= y < z and x + y > z), divide them by their gcd and add them to a set (which deletes duplications). The answer is the number of elements in the set.

We sort sticks in length to avoid repetition by rotating or mirroring. We divide the length by their gcd to avoid repetitions by uniformly scaling.


def count(self, L):
L=sorted(L)
LEN=len(L)
T=set()

for i in range(LEN):
x=L[i]
for j in range(i+1,LEN):
y=L[j]
G=gcd(x,y)
for k in range(j+1,LEN):
z=L[k]
if z=x+y:
break
GCD=gcd(G,z)
if (x//GCD,y//GCD,z//GCD) in T:
continue
else:
T.add((x//GCD,y//GCD,z//GCD))
return len(T)


CardDrawPoints 

Used as: Division One - Level Three:

Consider you are in the middle of the game, having several cards in your hand. You want to decide to terminate the game or not to terminate the game. What matters for your decision? For sure, just the set of cards you picked. As you can not pick the same card twice, we can describe each state with a mask of size n (n bits), where n is size of count[].

Now the solution comes to mind. We are going to use dynamic programming over bitmasks.

What is dp[mask]? Consider we have seen numbers in the mask. Let’s see if it is good to continue or we should terminate the game.

How? By calculating mathematical expectation of the next move. Consider we continue, for each possible card, calculate the score we gain. For example, if i is not present in mask and in the next move the card i is drawn, we gain i scores.

If i is present in mask and the card i is drawn, we lose everything.

Time complexity is O(2^n * n).

double expectedScore(vector <int count) {
for(int i = 0; i < (1<<16); i++) {
dp[i] = 0;
for(int j = 0; j < 16; j++) {
if(i&(1<<j)) dp[i] += j;
}
}
for(int i = 0; i < count.size(); i++) {
has[i] = count[i] 0;
}
for(int mask = -1 + (1 << (count.size())); mask = 0; mask--) {
bool can = true;
for(int i = 0; i < 16; i++) {
if((mask&(1<<i)) && !has[i]) {
can = false;
break;
}
}
if(!can) continue;
vector<int newv;
int total = 0;

for(int i = 0; i < count.size(); i++) {
newv.push_back(count[i]);
if(mask&(1<<i)) newv[i]--;
total += newv.back();
}
double draw = 0;
for(int i = 0; i < newv.size(); i++) {
if(mask&(1<<i)) continue;
draw += newv[i] * 1.0 / total * dp[mask | (1 << i)];
}
dp[mask] = max(dp[mask], draw);
}
return dp[0];
}