Match Editorial

Match summary

The first match after the TCCC was composed of a straightforward Easy, a very easy Medium and an easy but extremely tricky Hard problem, which lead to an eventful challenge phase. Many contestants had to resubmit the Hard problem after discovering an issue with overflows or commercials split over two different days. At the end, xhl_kogitsune won the match with three problems and 125 points in challenges, the second place went to Psyho with the Easy and the Medium and 12 successful challenges and the third place went to nika with three problems and on successful challenges. Congratulations to them.

In Division 2, the problemset was composed of a geometrical Easy and the Easy and Medium from Division 1 as Medium and Hard respectively. At the end of the challenge narri won the match, followed by avayvod and ttashiro, all with three successful problems. Congratulations to them too.

The Problems

Value	250
Submission Rate	571 / 694 (82.28%)
Success Rate	495 / 571 (86.69%)
High Score	mythic_bat for 249.65 points (1 mins 4 secs)
Average Score	183.47 (for 495 correct submissions)

This problem asked to count how many players are inside the hockey rink, where the hockey rink is defined as the union of a rectangle and two circles. Because the height is even, there is no need to use floating-point arithmetic, so we can implement the solution using integer arithmetic only. The first step is make functions to check if a point is inside a rectangle or inside a circle:

// (cx, cy) is the circle's center, r is the circle's radius and
// (px, py) is the point to test
bool insideCircle(int cx, int cy, int r, int px, int py) {
  const int dx = px - cx;
  const int dy = py - cy;
  const int r2 = r * r;
  return dx * dx + dy * dy <= r2;
}

// (x1, y1) is the rectangle's lower-left corner, (x2, y2) is the
// rectangle's upper-right corner and (px, py) is the point to test
bool insideRect(int x1, int y1, int x2, int y2, int px, int py) {
  return (x1 <= px && px <= x2) && (y1 <= py && py <= y2);
}

Then, just loop through all players and check which ones are inside the field:

// check if the point (px, py) is inside any of the three parts
// that compose the field
bool isInside(int W, int H, int x, int y, int px, int py) {
  int R = H / 2;
  return insideCircle(x, y + R, R, px, py)) ||
         insideCircle(x + W, y + R, R, px, py) ||
         insideRect(x, y, x + W, y + H, px, py);
}

int numPlayers(int width, int height, int x, int y,
               vector<int> px, vector<int> py) {
  int count = 0;
  for (int k = 0; k < (int)px.size(); ++k)
    if (isInside(width, height, x, y, px[k], py[k]))
      ++count;
  return count;
}

Value	500
Submission Rate	305 / 694 (43.95%)
Success Rate	75 / 305 (24.59%)
High Score	narri for 465.84 points (7 mins 48 secs)
Average Score	273.67 (for 75 correct submissions)

Value	275
Submission Rate	532 / 554 (96.03%)
Success Rate	264 / 532 (49.62%)
High Score	bmerry for 268.19 points (4 mins 33 secs)
Average Score	207.16 (for 264 correct submissions)

This problem asked to sort an array of words, using its syllablic decompossion. The first step to make a solution is to create a function that split a word in syllables, which can be easily implemented by realizing that the limit between a syllable and the next is when a consonant follows a vowel, so we could just search those points and split the word:

// check if letter c is a vowel
bool isVowel(char c) {
  const string VOWELS = "aeiou";
  return VOWELS.find(c) != string::npos;
}

// split word in syllables
vector<string> splitWord(string word) {
  // initialize the syllable with the first character (it is always a consonant)
  vector<string> syllables;
  string actual = word.substr(0, 1);
  for (int k = 1; k < (int)word.size(); ++k) {
    // get the letter and check if belongs to the next syllable
    char c = word[c];
    if (isVowel(actual[actual.size() - 1]) && !isVowel(c)) {
      syllables.push_back(actual);
      actual.clear();
    }
    actual.push_back(c);
  }
  // push the last syllable (there is always one because each word
  // ends with a vowel) and return
  syllables.push_back(actual);
  return syllables;
}

Now, we have to sort the words. To keep things simple, we could create a class to hold a word with its syllablic decomposition both sorted and unsorted:

struct Word {
  // the constructor stores the word, split it in syllables and store
  // the sequence both sorted and unsorted
  Word(string str) : word(str) {
    syllables = sortedSyl = splitWord(str);
    sort(sortedSyl.begin(), sortedSyl.end());
  }
  string word;               // original word
  vector<string> syllables;  // unsorted syllables
  vector<string> sortedSyl;  // sorted syllables
};

To sort the words, the easiest way is to create a functor that determines if a word goes before another word, it should compare using the sorted syllables if those arrays are different or using the unsorted ones in the other case:

struct WordFunctor {
  bool operator ()(const Word& w1, const Word& w2) const {
    // first compare using the sorted syllables, then using the unsorted ones
    if (w1.sortedSyl != w2.sortedSyl)
      return w1.sortedSyl < w2.sortedSyl;
    return w1.syllables < w2.syllables;
  }
};

Finally, we just have to assemble those parts in a complete solution:

vector<string> sortWords(vector<string> words) {
  // split the words in syllables
  vector<Word> V;
  for (int k = 0; k < (int)words.size(); ++k)
    V.push_back(Word(words[k]));

  // sort the words, assemble them and return
  sort(V.begin(), V.end());
  for (int k = 0; k < (int)words.size(); ++k)
    words[k] = V[k].word;
  return words;
}

One of the most common mistakes found on this problem was comparing the string directly as a tiebreaker instead of comparing the sequence of unsorted syllables. Thas approach fails when comparing "baaba" with "babba", because after splitting both words into syllables we get the sequences {"baa", "ba"} and {"ba", "baa"} respectively, and if we compare them lexicographically we can see that "babba" comes before "baaba".

Value	1000
Submission Rate	46 / 694 (6.63%)
Success Rate	34 / 46 (73.91%)
High Score	narri for 797.39 points (15 mins 8 secs)
Average Score	532.14 (for 34 correct submissions)

Value	500
Submission Rate	432 / 554 (77.98%)
Success Rate	397 / 432 (91.90%)
High Score	Petr for 462.37 points (8 mins 14 secs)
Average Score	314.58 (for 397 correct submissions)

This problem can be be solved easily using Breadth-First Search over the grid to search connected components colored with the k-th digit. For each connected component we calculate its area and bounding box, and return only those with area greater or equal than threshold.

Let's create a class to hold a player's information (area and bounding box's center) and a function to extract a player that contains the pixel in the position (x, y):

// structure to hold a player's information
struct Player {
  Player(int x_, int y_, int area_)
    : x(x_), y(y_), area(area_) {}
  int x, y, area;
};

// extract the player that contains the (x, y) pixel
Player extractPlayer(vector<string>& photo, int x, int y, int k) {
  // initialize the bounding box and the area with the (x, y) pixel
  const int M = (int)photo.size(), N = (int)photo[0].size();
  int x1 = 2 * x, y1 = 2 * y, x2 = x1 + 2, y2 = y1 + 2, area = 4;

  // erase the (x, y) pixel and insert it in the queue
  queue<pair<int, int> > cqueue;
  cqueue.push(make_pair(x, y));
  photo[y][x] = '.';

  // process all pixels that enter the queue
  while (!cqueue.empty()) {
    // get the pixel and remove it from the queue
    int x = cqueue.front().first, y = cqueue.front().second;
    cqueue.pop();
    
    // put in the queue all adjacent pixels to the actual that have the color k
    const int dx[4] = {-1, +1, 0, 0};
    const int dy[4] = {0, 0, -1, +1};
    for (int i = 0; i < 4; ++i) {
      // check if the new position is outside or isn't colored with k
      const int nx = x + dx[k], ny = y + dy[k];
      if (nx < 0 || nx >= N || ny < 0 || ny >= M || photo[ny][nx] != k + '0')
        continue;
      
      // update the bounding box and the area with the new pixel
      x1 = min(x1, nx * 2);
      y1 = min(y1, ny * 2);
      x2 = max(x2, (nx + 1) * 2);
      y2 = max(y2, (ny + 1) * 2);
      area += 4;
      
      // erase the pixel from the photo and insert it in the queue
      photo[ny][nx] = '.';
      cqueue.push(make_pair(nx, ny));
    }
  }
  
  // calculate the player's center and return it
  const int cx = (x1 + x2) / 2, cy = (y1 + y2) / 2;
  return Player(cx, cy, area);
}

We also need a functor to sort the players in the final result:

struct PlayerFunctor {
  bool operator ()(const Player& p1, const Player& p2) {
    // sort first by x-axis, then by y-axis
    if (p1.x != p2.x) return p1.x < p2.x;
    return p1.y < p2.y;
  }
};

Finally, we only need to search each pixel with the color from the required team, extract the players, filter them using the area and threshold and finally format the output:

vector<string> extractPlayers(vector<string> photo, int k, int threshold) {
  // process all the image and extract each player using flood fill
  const int M = (int)photo.length, N = (int)photo[0].size();
  typedef multiset<Player, PlayerFunctor> PlayerSet;
  PlayerSet players;
  for (int i = 0; i < M; ++i) for (int j = 0; j < N; ++j) {
    if (image[i][j] == k + '0') {
      // extract the player and add it only if it have enough area
      const Player nextPlayer = extractPlayer(photo, j, i, k);
      if (nextPlayer.area >= threshold)
        players.insert(nextPlayer);
    }
  }

  // format each player and return
  vector<string> result;
  for (PlayerSet::iterator it = players.begin(); it != players.end(); ++it) {
    ostringstream oss;
    oss << it->x << " " << it->y;
    result.push_back(oss.str());
  }
  return result;
}

Value	1000
Submission Rate	205 / 554 (37.00%)
Success Rate	16 / 205 (7.80%)
High Score	Orange_Cloud for 605.62 points (26 mins 56 secs)
Average Score	426.90 (for 16 correct submissions)

This problem was seemingly easy but had a lot of tricky parts and border cases inside it that made many coders resubmit their codes and brought many opportunities during the challenge phase. An interesting property about a commercial is that it will be played at:

start_k = start + k * T

where start is the second at which the commercial starts, k is an integer and T is secondsPerDay. Using this property, we can transform the input so:

• Detecting if our commercial overlaps with another can be done in an easy way: First, it is easier to work with time intervals of the form [start, end) to check if a pair of them intersects. Second, the last commercial might be split in two days. Splitting it in two separate commercials can difficult the task of calculating how many seconds a commercial will be remembered, an easier solution is repeat the last scheduled commercial one day before (using k = -1).
• Calculating how many second will be remembered our commercial can be done in an easy way: To calculate this value is as "simple" as finding the n-th commercial that will play after ours and subtract its start time from our start time. However, that n-th commercial can be on the next day, so we could repeat the first n scheduled commercials one day after (using k = +1). Finally, care must be taken when people can remember all scheduled commercials, in that case we should just return secondsPerDay.
• Operations don't overflow: All input values (except n) should be converted to 64-bits integers before doing anything, because when both starts[i] and durations[i] are 1999999999 an overflow will occur when trying to calculate in which second ends the i-th commercial.

After applying this transformations, we could code a function to calculate how many time will be remembered our commercial if scheduled at a certain second (and return -1 if it impossible to schedule it at that position):

// type definition to not copy long long over all the code
typedef long long i64;

// V is the array of sorted commercials and start and end are the
// interval of the commercial to check
bool IsPossible(const vector<pair<i64, i64< <& V, i64 start, i64 end) {
  // check each commercial and check if it overlaps
  for (int k = 0; k < (int)V.size(); ++k) {
    if (start >= V[k].first && start < V[k].second) return false;
    if (V[k].first >= start && V[k].first < end) return false;
  }
  return true;
}

// V is the array of sorted commercials, start is the position where we will
// schedule our commercial, duration is our commercial's duration, N is the
// number of commercials remembered by people, M is the number of scheduled
// commercials per day and T is the number of seconds per day
i64 GetTime(const vector<pair<i64, i64> >& V, i64 start, i64 duration,
            int N, int M, i64 T) {
  // check if it doesn't overlap with other commercial and if
  // it is remembered through all day
  if (!IsPossible(V, start, start + duration)) return -1;
  if (N > M) return T;

  // find the first commercial that if after ours and calculate
  // the time elapsed until the start of the N commercial
  for (int k = 0; k < (int)V.size(); ++k) {
    if (V[k].first > start)
      return V[k + N - 1].first - start;
  }

  // the function should never end here
  return -1;
}

However, we can't test our commercial at every position possible because there can be up to 2000000000 seconds per day in the worst case. The solution is to try to schedule our commercial only at certain points:

• Exactly after another commercial. Why? Suposse we schedule our commercial at the T-th and it will be remembered for X seconds and the T-1-th second is free. We could schedule our commercial at the T-1-th and make our commercial be remembered for X+1 seconds, because the next n-th commercial after ours will be the same. Therefore, the schedule at the T-th second is not maximal.
• At second 0. Why? In the case where people remember all commercials, we only have to search the earliest second where we can schedule our commercial. Suposse we schedule our commercial at the T-th with T > 0. If the T-1-th second is not free, then it is covered by the previous point. If the T-1-th second is free, then we can move our commercial there and get a lower second. Therefore, the only second left to test not covered by the previous point is 0.

Now, all left is test each important second and return the better:

int bestMinute(vector<int> starts_, vector<int> durations_, int ourDuration_,
               int secondsPerDay_, int N) {
  // check border case
  if (starts_.empty()) return 0;

  // cast all intergers to 64-bits
  vector<i64> starts, durations;
  for (int k = 0; k < (int)starts_.size(); ++k) {
    starts.push_back(starts_[k]);
    durations.push_back(durations_[k]);
  }
  const i64 ourDuration = ourDuration_, T = secondsPerDay_;

  // sort all commercials by start time
  const int M = (int)starts.size();
  vector<pair<i64, i64> > V(M);
  for (int k = 0; k < (int)V.size(); ++k)
    V[k] = make_pair(starts[k], starts[k] + durations[k]);
  sort(all(V));

  // add the last commercial once at the beggining and the first
  // N commercials at the end
  const pair<i64, i64> last = V.back();
  V.insert(V.begin(), make_pair(last.first - T, last.second - T));
  for (int k = 1; k <= N; ++k)
    V.push_back(make_pair(V[k].first + T, V[k].second + T));

  // try to put the commercial at 0
  i64 bestSecond = -1, bestRemembered = 0;
  const i64 remAtZero = GetTime(V, 0, ourDuration, N, M, T);
  if (remAtZero != -1) bestSecond = 0, bestRemembered = remAtZero;

  // try to put the commercial after each other commercial
  for (int k = 1; k <= M; ++k) {
    const i64 second = V[k].second % T;
    const i64 remembered = GetTime(V, V[k].second, ourDuration, N, M, T);
    if (remembered == -1) continue;
    if (remembered > bestRemembered ||
        (remembered == bestRemembered && second < bestSecond))
      bestRemembered = remembered, bestSecond = second;
  }
  return (int)bestSecond;
}