March 23, 2020 2020 Humblefool Cup Prelims Editorials

ScoringJudges 

Used as: Division One – Level One:

Value250
Submission Rate205 / 259 (79.15%)
Success Rate162 / 205 (79.02%)
High Scorekaun_meet for 249.98 points (0 mins 15 secs)
Average Score201.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:

Value500
Submission Rate163 / 259 (62.93%)
Success Rate138 / 163 (84.66%)
High Scorekaun_meet for 499.96 points (0 mins 15 secs)
Average Score409.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:

Value1000
Submission Rate62 / 259 (23.94%)
Success Rate42 / 62 (67.74%)
High Scorexiaowuc1 for 976.72 points (4 mins 24 secs)
Average Score720.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


categories & Tags


Close

Sign up for the Topcoder Monthly Customer Newsletter

Thank you

Your information has been successfully received

You will be redirected in 10 seconds