November 19, 2020 Rookie Single Round Match 1 Editorials

ColorWheel

A basic solution might look something like:

• Check if the two colors are the same
• Check if they’re adjacent
• Check if they’re complementary
• Otherwise, they’re none of these

There are only six colors, so in the worst case, we could simply write about a dozen if-statements to cover all possible cases for adjacent and complementary.

Slightly easier, however, would be to convert each possible color Red…Purple into an index value 0…5; then, we can subtract the index value of the two colors, and simply check that difference: 0 = same color, 3 = complementary, 1 or 5 = adjacent, otherwise none.

private int findIndex(String s) {
  for (int i = 0; i < colors.length; i++)
    if (colors[i].equals(s))
      return i;
  return -1;
}

public String describePair(String color1, String color2) {
  int diff = Math.abs(findIndex(color1) - findIndex(color2));
  if (diff == 0) return "Same";
  if (diff == 1 || diff == 5) return "Adjacent";
  if (diff == 3) return "Complementary";
  return "None";
}

OverallScores

This problem is also straightforward, only we have to do a little simple math first. We need to add up the total score for each player. Then, we can look at the total scores to figure out which one is the largest, and return the index, being careful to prefer lower index in the case of a tie.

For any given index i in scores, we can determine which player it belongs to by calculating i % N.

public int findWinner(int N, int[] scores) {
  int[] total = new int[N];
  for (int i = 0; i < scores.length; i++) total[i % N] += scores[i];
  int bestIndex = -1;
  int bestScore = -1;
  for (int i = 0; i < total.length; i++)
    if (total[i] > bestScore) {
      bestScore = total[i];
      bestIndex = i;
    }
  return bestIndex;
}

OneForYou

This is a pretty straightforward simulation, at least for smaller values of N. Give one coin to the second person, then i coins to the first person, for increasing values of i, until all the coins have been distributed. The thing to be careful about here is the case where there aren’t enough coins left to give the first person a full i coins.

The only problem with a straight simulation comes in for very large values of N… there is some potential risk that it will take too long to run. So what do we do? If you’re thinking maybe we can find a formula, you are right, and that’s exactly what we will do.

After x rounds of distributing coins, the second person will have x coins total, and the first person will have Sum(1, 2, …, x) coins. We might recall that this equals x * (x + 1) / 2. So, in total, we will have distributed (x^2 + 3x) / 2 coins after x rounds.

We just need to answer the question, how many complete rounds of distributing coins can we do? If it seems like we might use the quadratic formula here, you’re right again, good job!

(x^2 + 3x) / 2 = N

=> x^2 + 3x – 2N = 0

=> x = (-3 + sqrt(9 + 8N)) / 2

=> x = sqrt(2.25 + 2N) – 1.5

Now, this may not give us a whole number, as there could be a partial round of coins. Knowing how many rounds we have done, however, we know exactly how many coins have been distributed to each person. Of those remaining, we give one more to the second person, if possible, and any leftover to the first person. 

And it turns out, our code is actually quite simple, once we have done the math.

public long coinCount(long N) {
  long x = (long)Math.floor(Math.sqrt(2.25 + 2 * N) - 1.5);
  long c = (x * x + x) / 2;
  long rem = N - c - x - 1;
  if (rem > 0) c += rem;
  return c;  
}