Tuesday, November 6, 2007 Match summaryThe 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 ProblemsHockeyFaultUsed as: Division Two  Level One:
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 floatingpoint 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 lowerleft corner, (x2, y2) is the // rectangle's upperright 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; }SyllableSorting Used as: Division Two  Level Two: Used as: Division One  Level One:
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". PlayerExtractionUsed as: Division Two  Level Three: Used as: Division One  Level Two:
This problem can be be solved easily using BreadthFirst Search over the grid to search connected components colored with the kth 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 xaxis, then by yaxis 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; }CommercialPlanner Used as: Division One  Level Three:
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:
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:
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 64bits 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; } 
