Match summary

This 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

and those with

N + 1

problems. 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 Problems

BusAwaiting

Used as: Division One - Level One:

Value 250

Submission Rate 1335 / 1392 (95.91%)

Success Rate 1102 / 1335 (82.55%)

High Score Valco for 248.43 points (2 mins 15 secs)

Average Score 205.45 (for 1102 correct submissions)

Notation

= number of buses

= average

COUNT

O(N) solution

There are two cases:

arrivalTime ≤ START

: you have to wait

START - arrivalTime

units.

```
arrivalTime > START
```
: you have to take the first bus that comes:
```
n = ⌈(arrivalTime - START) / INTERVAL⌉
```
.
The bus will not exist if
```
n = COUNT
```
, otherwise you will have to wait
```
START + n * INTERVAL - arrivalTime
```
units.

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;
        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 ≤ 50

and

M ≤ 100

you 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:

Value 500

Submission Rate 854 / 1392 (61.35%)

Success Rate 536 / 854 (62.76%)

High Score Loner for 464.88 points (7 mins 55 secs)

Average Score 285.82 (for 536 correct submissions)

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:

Value 1000

Submission Rate 147 / 1392 (10.56%)

Success Rate 62 / 147 (42.18%)

High Score pparys for 686.81 points (21 mins 20 secs)

Average Score 457.68 (for 62 correct submissions)

In this problem one had to place rectangles with certain patterns of black cells. Since the maximum size of a rectangle is 40000² 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.

Shows positions of 1,2,3&4

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;
  }
};

By otinn
TopCoder Member