Qualification Round 2 Saturday, February 9, 2008 Match summaryThis problemset was more traditional than the last one. At least a fast 250 and a successful challenge were required to advance. Nobody managed to do it with only challenges, some even failed to do it with slow solutions to the 500. The most surprising fact about the results is that there was almost no discontinuity between those who managed to solve Nand those with N + 1problems. This made challenges a lot more important than usual because the loss of 25 points or gain of 50 points could have changed ones rank considerably. Among the advancers were 18 red coders (they were required to compete in the qualifications because they were not active enough), 256 yellows, 190 blue coders, 81 green coders and 5 grey ones. Three fast solutions secured the first place for pparys with a 82.76 point lead in front of g201513. With the extra help of a successful challenge chEEtah managed to finish third. The ProblemsBusAwaitingUsed as: Division One  Level One:
Notation N= number of buses M= average COUNT O(N) solution There are two cases:
int waitingTime(vector <string> buses, int arrivalTime) { unsigned result = 0xffffffff; // maximum value, equal to 1 in signed form for(int i = 0; i < buses.size(); ++i) { int start, interval, count; istringstream(buses[i]) >> start >> interval >> count; if(arrivalTime <= start) result = min(result, unsigned(start  arrivalTime)); else { int t = (arrivalTime  start + interval  1) / interval; if(t > 0 && t < count) result = min(result, unsigned(start + t * interval  arrivalTime)); } } return result; } O(N*M) solution This was the solutions used by most people and was less error prone because there were no cases you could miss.Since N ≤ 50and M ≤ 100you can just iterate over all possible buses and choose the best one. C++ code: int waitingTime(vector <string> buses, int arrivalTime) { unsigned result = 0xffffffff; // maximum value, equal to 1 in signed form for(int i = 0; i < buses.size(); ++i) { int start, interval, count; istringstream(buses[i]) >> start >> interval >> count; for(int j = 0; j < count; ++j) { unsigned x = start + j * interval; if(x >= arrivalTime) result = min(result, x  arrivalTime); } } return result; }PhoneNumbers Used as: Division One  Level Two:
One of the easiest solutions to this problem is to recursively generate the assignments in lexicographical order and then choose the one that scores the highest. To generate the assignments in lexicographical order one has to use a dash ('') as soon as possible. To make sure that you are not wasting your time looking at the end parts of an assignment the like of which you have already analyzed you can stop when you reach the same position in the number with the same score. This solutions is intuitively correct, but as a good exercise you can find a solution with better complexity. C++ implementation: struct PhoneNumbers { bool visited[100][200]; string number, result; int res_score; void Solve(int pos, int score, string cur) { if(visited[pos][score]) return; visited[pos][score] = true; if(pos == number.size()) { if(score > res_score) { res_score = score; result = cur; } return; } set <char> S; for(int i = 0; i < 3; ++i, ++pos) { if(pos >= number.size()) break; if(i == 0 && cur != "") cur += ""; cur += number[pos]; S.insert(number[pos]); if(i == 1) Solve(pos + 1, score + (S.size() == 1? 2: 0), cur); else if(i == 2) Solve(pos + 1, score + 3  S.size(), cur); } } string bestNumber(string n) { memset(visited, 0x00, sizeof(visited)); number = n; res_score = 1; Solve(0, 0, ""); return result; } };BlackWhiteRectangles Used as: Division One  Level Three: In this problem one had to place rectangles with certain patterns of black cells. Since the maximum size of a rectangle is 40000^{2} cells then it was not possible to directly simulate the process. Instead one could divide paper into a maximum of 2N*2N parts and then add the patters of all rectangles that cover that particular part. A relatively easy way to do that is to use bitmasks of 2*2 bits which represents the lower left corner of the part of the sheet being calculated. Once you have the bitmask you know that area 0 on the picture contains ⌊width / 2⌋ * ⌊height / 2⌋ * number_of_bits(bitmask)black cells. Then you can use parts of the bitmask to calculate the number of black cells in areas 1, 2 and 3. A C++ implementation of the described approach: int mask[2][2][4]; struct rect1 { int x1, y1, x2, y2, type; }; struct BlackWhiteRectangles { void createMasks() { memset(mask, 0x00, sizeof(mask)); for(int sy = 0; sy < 2; ++sy) for(int sx = 0; sx < 2; ++sx) { for(int y = 0; y < 2; ++y) for(int x = 0; x < 2; ++x) { mask[sy][sx][0] = (1 << (2 * y + x)); if((sy + y) % 2 == 1) mask[sy][sx][1] = (1 << (2 * y + x)); if((sx + x) % 2 == 1) mask[sy][sx][2] = (1 << (2 * y + x)); if((sy + y) % 2 == (sx + x) % 2) mask[sy][sx][3] = (1 << (2 * y + x)); } } } int blackCount(vector <string> rectangles) { createMasks(); set <int> X, Y; vector <rect1> rect(rectangles.size()); foreach(i, 0, rectangles) { istringstream sis(rectangles[i]); sis >> rect[i].x1 >> rect[i].y1 >> rect[i].x2 >> rect[i].y2 >> rect[i].type; X.insert(rect[i].x1); X.insert(rect[i].x2); Y.insert(rect[i].y1); Y.insert(rect[i].y2); } vector <int> x(X.begin(), X.end()); vector <int> y(Y.begin(), Y.end()); int result = 0; foreach(i, 1, x) foreach(j, 1, y) { int black = 0, w = x[i]  x[i  1], h = y[j]  y[j  1]; foreach(k, 0, rect) { if((rect[k].x1 >? x[i  1]) >= (rect[k].x2 <? x[i])) continue; if((rect[k].y1 >? y[j  1]) >= (rect[k].y2 <? y[j])) continue; black = mask[(y[j  1]  rect[k].y1 + 1) % 2][(x[i  1]  rect[k].x1 + 1) % 2][rect[k].type  1]; } // .. // 0. result += __builtin_popcount(black) * (w / 2) * (h / 2); // .. // .1 if(w % 2 == 1) result += __builtin_popcount(black & 10) * (h / 2); // 2. // .. if(h % 2 == 1) result += __builtin_popcount(black & 12) * (w / 2); // .3 // .. if(w % 2 == 1 && h % 2 == 1) result += __builtin_popcount(black & 8); } return result; } }; 
