March 23, 2020 2020 Humblefool Cup Prelims Editorials
ScoringJudges
Used as: Division One – Level One:
| Value | 250 |
| Submission Rate | 205 / 259 (79.15%) |
| Success Rate | 162 / 205 (79.02%) |
| High Score | kaun_meet for 249.98 points (0 mins 15 secs) |
| Average Score | 201.61 (for 162 correct submissions) |
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:
| Value | 500 |
| Submission Rate | 163 / 259 (62.93%) |
| Success Rate | 138 / 163 (84.66%) |
| High Score | kaun_meet for 499.96 points (0 mins 15 secs) |
| Average Score | 409.48 (for 138 correct submissions) |
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:
| Value | 1000 |
| Submission Rate | 62 / 259 (23.94%) |
| Success Rate | 42 / 62 (67.74%) |
| High Score | xiaowuc1 for 976.72 points (4 mins 24 secs) |
| Average Score | 720.43 (for 42 correct submissions) |
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];
}
Guest Blogger
