#### Good job! You’re all caught up

Earlier Dismiss All

## March 23, 2020 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:
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&amp;(1<<j)) dp[i] += j;
}
}
for(int i = 0; i < count.size(); i++) {
has[i] = count[i] > 0;
}
bool can = true;
for(int i = 0; i < 16; 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]);
total += newv.back();
}
double draw = 0;
for(int i = 0; i < newv.size(); i++) {
draw += newv[i] * 1.0 / total * dp[mask | (1 << i)];
}
}
return dp[0];
}



a.poorakhavan

Guest Blogger

categories & Tags

UNLEASH THE GIG ECONOMY. START A PROJECT OR TALK TO SALES
Close