May 11, 2019 2019 Topcoder Collegiate Contest Qualifiers Editorials

MaxPlanting

A few key observations are necessary to make this problem a lot easier. Fortunately, gut instinct can take the place of a more rigorous proof in coming up with a formulaic way to solve this.

We start by imagining dividing up the field into several size x size subareas, possibly with some leftover smaller areas to the right and bottom. assuming that every size x size subarea will be filled to maximum capacity.

The important thing to note here is that if we use exactly the same pattern to fill each of those sub-areas, then any size x size area, even one that isn’t aligned, will still have a maximum fill.

The total number of full-size sub areas will be: floor(height / size) * floor(width / size). The subareas leftover on the side are all (width % size) wide and size tall. The leftover areas on the bottom are (height % size) talls and size wide.

So the last thing to do is to assume our fill pattern for each sub area maximizes how many crops will be planted in the leftover corner area, then the leftover areas along the side or bottom (depending on which there are more of).

  public int most(int width, int height, int size, int max) {
    if (max > size * size) max = size * size;
    int wb = width / size;
    int hb = height / size;
    int wr = width % size;
    int hr = height % size;
    int ret = wb * hb * max;
    int dc = wb + hb + 1;
    int dx = Math.min(wr * hr, max);
    max -= dx;
    int wx = Math.min(wr * size - dx, max);
    max -= wx;
    int hx = Math.min(hr * size - dx, max);
    max -= hx;
    ret += dx * dc;
    ret += wx * hb;
    ret += hx * wb;
    return ret;
  }

TreeLine

This problem is actually in some ways more straightforward than the easy problem, but does require a bit more mathematical intuition and care to implement correctly.

Of course, if there are only one or two trees, then we know they are already collinear and are done. If there’s more than that, we actually have to do the math. The actual idea behind it is simple… consider all possible lines on which trees could be collinear. In other words, for each pair of trees (which of course are two points that uniquely define a line), see if any other trees are on that same line.

The simplest way to do that, of course, is to calculate the slope between two points, dy/dx. Then, for the first point, calculate the slope against any of the other points. If it’s the same, that point must be collinear with the other two.

A few things to be careful of. Calculating using floating point is dangerous territory, as precision errors could creep in. So, if the two slopes are dy/dx and ddy/ddx, we can insead check equality by comparing ddx * dy with ddy * dx. But, there’s still one more wrinkle to watch out for. If the test line is vertical (dy == 0) or horizontal (dx == 0), that check may fail, so it’s better to look for cases where dy == ddy == 0 or dx == ddx == 0 separately.

public int most(int[] x, int[] y) {
    if (x.length < 3) return x.length;
    int best = 2;
    for (int i = 0; i < x.length - 2; i++)
      for (int j = i + 1; j < x.length - 1; j++) {
        int count = 2;
        int dx = x[j] - x[i];
        int dy = y[j] - y[i];
        for (int k = j + 1; k < x.length; k++) {
          int ddx = x[k] - x[i];
          int ddy = y[k] - y[i];
          if ((dx == 0 && ddx == 0) || (dy == 0 && ddy == 0)) {
            count++;
            continue;
          }
          if (dy * ddx == ddy * dx) count++;
        }
        best = Math.max(best, count);
      }
    return best;
  }

ThreeTrees

Naturally, we saved the best for last, and this problem, while easy to understand the task, is not very simple to calculate. Essentially we want to imagine starting with our 10×10 grid, shading in the (up to) three circles of given radius at the given points, then calculating the unshaded area.

One approach, guaranteed to work, but exceedingly hard to code, is to calculate the area of overlap of each circle with the square, and add those three areas together. Then, calculate the area of overlap of each pair of circles with the square, and subtract those, since we would have double counted them in the first step. Then finally, calculate the area of overlap of all three circles with the square, and add that back in, since we subtracted it in step two. This would work, but the formulas to calculate this are at best messy, and very error prone.

Another approach, used here, might be less obvious, but is far easier to code. We start by dividing the whole area into 1×1 squares. For each such square, we determine if it is overlapped entirely by a single circle, by no circles at all, or partially by one or more circles. If it’s entirely overlapped by a single circle we no that none of that area is good. If it’s not overlapped at all, we know that area is good, and can add it to a running total. If the overlap is partial, we divide the square into 4 smaller units, recurse, and try again, bailing out once the subdivided squares are simply too small. Eventually, we get a precise enough total.

double ret;
double r;
double[] x;
double[] y;
public double area(int[] x, int[] y, int radius) {
    this.x = new double[x.length];
    for (int i = 0; i < x.length; i++) this.x[i] = x[i];
    this.y = new double[y.length];
    for (int i = 0; i < y.length; i++) this.y[i] = y[i];
    this.r = radius * radius;
    this.ret = 0;
    for (int i = 0; i < 10; i++)
      for (int j = 0; j < 10; j++)
        calculate(i, j, i + 1, j + 1);
    return this.ret;
}