September 21, 2020 2020 TCO North America Regionals Algorithm Editorials
EllysBlood
We have folks that need blood, and supplies of blood available, but because of restrictions on types that are compatible, not just any blood can be given to any person. The only thing we need to be careful here is giving blood in the right order, and along the way keeping count of how many people we can give blood to:
- AB blood to those needing AB
- A blood to those needing A, then to those still needing AB
- B blood to those needing B, then to those still needing AB
- O blood to as many remaining people as possible
public int getMax(int[] have, int[] need) {
int[][] canGive = { {3, 3}, {2, 2}, {2, 3}, {1, 1}, {1, 3}, {0, 0}, {0, 1}, {0, 2}, {0, 3} };
int ans = 0;
for (int i = 0; i < 9; i++) {
int use = Math.min(have[canGive[i][0]], need[canGive[i][1]]);
ans += use;
have[canGive[i][0]] -= use;
need[canGive[i][1]] -= use;
}
return ans;
}
PalindromicSubsequences
This is actually a fairly standard DP task, where one needs to keep track of “how many palindromes could be created from the letters between left and right?”
To calculate how many can be made within a segment of the string, search for all pairs of letters (possibly the same letter) and imagine using them as a 2 letter palindrome or else using them on the left and right sides of a palindrome that can be constructed from the letters between them. (And there’s our DP recurrence!)
private int[][] dp = new int[50][50];
private String t;
private int getCount(int left, int right) {
if (right < left) return 0;
if (dp[left][right] > -1) return dp[left][right];
int ret = 0;
for (int i = left; i <= right; i++)
for (int j = i; j <= right; j++)
if (t.charAt(i) == t.charAt(j)) {
ret = (ret + 1 + getCount(i + 1, j - 1)) % 10000019;
}
return dp[left][right] = ret;
}
public int count(String s) {
t = s;
for (int i = 0; i < 50; i++) for (int j = 0; j < 50; j++) dp[i][j] = -1;
return getCount(0, s.length() - 1);
}
EllysIncinerator
Essentially, we need to find the circle of largest radius, with it’s center in the 1000×1000 area, such that it won’t overlap any of the existing circles.
The approach here is to binary search for the maximum radius R of such a circle. For each test, we want to see if there exists a point to place such a circle without intersecting any of the others. One way to do this is use pairs of existing circles to find the points at which a new circle would touch them both, and from all such candidates, make sure there is at least one that doesn’t intersect any circles.
For a somewhat simpler implementation of this, we can alternatively imagine increasing the radius of all existing circles by R, and seeing if there exists any points not yet already covered by a circle. Any such point would be a potential location for the new circle.
public class EllysIncinerator {
static final double EPS = 0.000000001;
class Point {
double x, y;
Point(double x_, double y_) {x = x_; y = y_;}
}
class Circle {
Point center;
double radius;
Circle(double x_, double y_, double r_) {center = new Point(x_, y_); radius = r_;}
}
int n;
Circle[] orig, a;
List<Point> candidates;
double sqDist(Point p1, Point p2) {
return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
}
double sqVal(double val) {
return val * val;
}
Point pointOnLine(Point p1, Point p2, double ratio) {
return new Point(p1.x + (p2.x - p1.x) * ratio, p1.y + (p2.y - p1.y) * ratio);
}
Point findClosest(Point p1, Point p2, Point target, double offset) {
double left = 0.0, right = 1.0;
for (int iter = 0; iter < 100; iter++) {
double m1 = left + (right - left) / 3.0;
double m2 = right - (right - left) / 3.0;
double d1 = Math.abs(sqDist(target, pointOnLine(p1, p2, m1)) - sqVal(offset));
double d2 = Math.abs(sqDist(target, pointOnLine(p1, p2, m2)) - sqVal(offset));
if (d1 < d2) right = m2; else left = m1;
}
return pointOnLine(p1, p2, right);
}
void circleLine(Circle circle, Point p1, Point p2) {
Point closest = findClosest(p1, p2, circle.center, 0.0);
if (sqDist(closest, circle.center) > sqVal(circle.radius))
return;
Point cand1 = findClosest(closest, p1, circle.center, circle.radius);
if (Math.abs(sqDist(cand1, circle.center) - sqVal(circle.radius)) < EPS)
candidates.add(cand1);
Point cand2 = findClosest(closest, p2, circle.center, circle.radius);
if (Math.abs(sqDist(cand2, circle.center) - sqVal(circle.radius)) < EPS)
candidates.add(cand2);
}
Point rotate(Point origin, Point point, double angle) {
double s = Math.sin(angle), c = Math.cos(angle);
Point trans = new Point(point.x - origin.x, point.y - origin.y);
return new Point(origin.x + trans.x * c - trans.y * s, origin.y + trans.x * s + trans.y * c);
}
void circleCircle(Circle circle1, Circle circle2) {
double dist = sqDist(circle1.center, circle2.center);
if (dist > sqVal(circle1.radius + circle2.radius))
return;
if (Math.abs(dist - sqVal((circle1.radius + circle2.radius))) < EPS) {
candidates.add(
pointOnLine(circle1.center, circle2.center, circle1.radius / (circle1.radius + circle2.radius))
);
return;
}
Point p = pointOnLine(circle1.center, circle2.center, circle1.radius / Math.sqrt(dist));
double angle = Math.acos(
(sqVal(circle1.radius) + dist - sqVal(circle2.radius)) / (2.0 * circle1.radius * Math.sqrt(dist))
);
candidates.add(rotate(circle1.center, p, +angle));
candidates.add(rotate(circle1.center, p, -angle));
}
boolean eval(double radius) {
a = new Circle[n];
for (int i = 0; i < n; i++)
a[i] = new Circle(orig[i].center.x, orig[i].center.y, orig[i].radius + radius);
candidates = new ArrayList<>();
candidates.add(new Point(0, 0));
candidates.add(new Point(0, 1000));
candidates.add(new Point(1000, 0));
candidates.add(new Point(1000, 1000));
for (int i = 0; i < n; i++) {
circleLine(a[i], new Point(0, 0), new Point(0, 1000));
circleLine(a[i], new Point(0, 0), new Point(1000, 0));
circleLine(a[i], new Point(1000, 1000), new Point(0, 1000));
circleLine(a[i], new Point(1000, 1000), new Point(1000, 0));
}
for (int c1 = 0; c1 < n; c1++) {
for (int c2 = c1 + 1; c2 < n; c2++) {
circleCircle(a[c1], a[c2]);
}
}
for (Point candidate : candidates) {
if (candidate.x < 0.0 || candidate.x > 1000.0) continue;
if (candidate.y < 0.0 || candidate.y > 1000.0) continue;
boolean okay = true;
for (int c = 0; c < n; c++) {
if (sqDist(candidate, a[c].center) < sqVal(a[c].radius) - EPS) {
okay = false;
break;
}
}
if (okay) {
return true;
}
}
return false;
}
public double getMax(double[] X, double[] Y, double[] R) {
n = X.length;
orig = new Circle[n];
for (int i = 0; i < n; i++)
orig[i] = new Circle(X[i], Y[i], R[i]);
double left = 0.0, right = 2000.0;
for (int iter = 0; iter < 64; iter++) {
double mid = (left + right) / 2.0;
if (eval(mid)) left = mid; else right = mid;
}
return left;
}
}
The solution above uses ternary search to find the closest point on a line to a circle in order to avoid corner cases, but solving a quadratic equation would work as well of course — and will be faster.
UniformingArray
Here, we need to find k-length segments (also called k-windows) of an array in which there are more 1s than 0s, and change them all to 1s. If all such segments of the array have more 0s than 1s, there’s nothing we can do.
Otherwise, we can consider each possible starting segment, and calculate how many further operations we need to do to the left and right in order to completely transform the array into all-ones. Let such a starting segment be between indices L and R. Let us focus on the part which is to the right of R; the part left to L is solved using the same idea. To solve the right part, we apply operations greedily by first transforming 0s to 1s closest to R — each successive operation should be taken as far as possible, i.e., transform as many 0s to 1s as possible.
Here is a basic proof sketch of why this idea works:
- Consider positions of operations to the right of where we place the first k-windows, which spans between indices L and R. Let those positions be R1 < R2 < R3 < …. We want to show that there is a process that applies operations at R1, then at R2 and so on, in that specific order. Let R_0 = L; by construction, we know that the operation at R_0 is applied before operation at any other R_i.
- The proof goes by taking a solution that has the longest sequence of positions where that condition is not violated, i.e., we place R_0, R1, R2, …, R_{i-1} in that order (these k-windows might be interleaved with some other k-windows, say R_{i+2}, but we don’t care), but then R_{i+1} is placed by the algorithm before it places R_i. We will show that this can be improved.
- Let R_{i+1} be the first which doesn’t follow that order, that is, the k-window at R_{i+1} is placed before the k-window at R_i. By assumption, R_{i-1} is placed before R_i.
- Note that to the left of R_i there are at least k ones. So, we can “shift” R_i to the left so that it doesn’t overlap R_{i+1} at all, as there are enough ones to the left of R_i. Let R_i’ be this shifted position. Since R_i’ and R_{i+1} do not overlap, we can as well serve place R_i’ before R_{i+1}. This now contradicts that the solution we choose had the longest sequence of positions R_0, R_1, …, R_{i-1} which are served at that specific order.
Of course, though they are allowed by the problem, there would never be a reason to consider an operation that flips a segment to all 0s, which would take us further from our goal.
import java.util.*;
public class UniformingArray {
private int Areverse[];
private int best(int[] C, int idx, int k) {
int ret = 0;
int n = C.length;
while (idx < n) {
while (idx < n && C[idx] == 1)
idx++;
if (idx == n)
break;
int sum = 0;
int nidx = -1;
for (int i = 0; i < k && idx + i < n; i++) {
if (C[idx + i] == 0)
sum++;
if (sum <= k / 2)
nidx = idx + i;
}
idx = nidx + 1;
ret++;
}
return ret;
}
public int minOperations(int[] A, int k) {
int n = A.length;
Areverse = new int[n];
for (int i = 0; i < n; i++)
Areverse[i] = A[n - i - 1];
int ret = -1;
for (int i = 0; i + k <= n; i++) {
int cnt = 0;
for (int j = i; j < i + k; j++)
cnt += A[j];
if (cnt > k / 2) {
// Found a k-window we can consider starting from
int tmp = best(A, i + k, k) + best(Areverse, n - (i - 1) - 1, k);
if (cnt < k)
tmp++;
// If this is best one yet, keep that result
if (tmp < ret || ret == -1) {
ret = tmp;
}
}
}
return ret;
}
}
EllysThree
If we imagine our matrix as a series of diagonals, each move to the right or down can be seen to move us from one diagonal to the next. Thus, any complete path must go from the first to the last diagonal. This will be important to remember.
We hopefully recall that divisibility by three means the sum of the digits is divisible by three. What this means is that we need to look at all of our digits MOD 3, with one caveat:
The only corner case is to assume that each digit can be changed to any modulo 3 with at most one operation — but are not careful enough to notice that there are two exceptions: 0 to become 2 (mod 3) and 9 to become 1 (mod 3) would each require two operations. This case is fairly easy to see, but important to notice, we intentionally did not cover it in the samples.
We can then look at each diagonal and consider how many changes it would take to have the sum up through that diagonal be equal to 0, 1, or 2 MOD 3. It’s then a fairly simple DP to get down to the bottom corner, in the fewest number of changes.
private static final int MAX = 55;
private static final int INF = 1000000001;
private int n, m;
private char[][] a;
private int[][] dyn;
private int recurse(int idx, int mod) {
if (idx >= n + m - 1)
return mod == 0 ? 0 : INF;
if (dyn[idx][mod] != -1)
return dyn[idx][mod];
int ans = INF;
for (int target = 0; target < 3; target++) {
int add = 0;
for (int row = 0, col = idx; row < n; row++, col--) {
if (col >= 0 && col < m) {
if ((a[row][col] - '0') % 3 != target) {
add++;
if (a[row][col] == '0' && target == 2) add++;
if (a[row][col] == '9' && target == 1) add++;
}
}
}
int cur = recurse(idx + 1, (mod + target) % 3) + add;
ans = ans > cur ? cur : ans;
}
return dyn[idx][mod] = ans;
}
public int getMin(int N, int M, String[] matrix) {
n = N; m = M;
a = new char[n][m];
for (int row = 0; row < n; row++)
for (int col = 0; col < m; col++)
a[row][col] = matrix[row].charAt(col);
dyn = new int[MAX + MAX][3];
for (int idx = 0; idx < MAX + MAX; idx++)
for (int mod = 0; mod < 3; mod++)
dyn[idx][mod] = -1;
return recurse(0, 0);
}
MultiWordSearch
This one is very straightforward. Simply consider each cell of the grid as a possible starting point for the word, check horizontally and vertically, and count how many times the word is found.
This is intentionally basically just a coding exercise warmup before the second problem of the final.
public int countTimes(String[] grid, String word) {
int ret = 0;
for (int i = 0; i < grid.length; i++)
for (int j = 0; j <= grid[i].length() - word.length(); j++) {
boolean good = true;
for (int k = 0; k < word.length(); k++)
if (word.charAt(k) != grid[i].charAt(j + k)) good = false;
if (good) ret++;
}
for (int i = 0; i <= grid.length - word.length(); i++)
for (int j = 0; j < grid[i].length(); j++) {
boolean good = true;
for (int k = 0; k < word.length(); k++)
if (word.charAt(k) != grid[i + k].charAt(j)) good = false;
if (good) ret++;
}
return ret;
}
EllysDiggyDiggyHole
We have a large number of points on a 2D grid, and need to pick a point that minimizes the total Manhattan-distance from each of the other points. Since we’re dealing with Manhattan distance, that means we can consider the x and y coordinates separately, and add together our final result. It also happens to be the case that the median point in each dimension is the optimal location. (If it’s not immediately clear why, consider that once you are above or below the median location, then more points would be further away and less points would be closer.)
Given the large number of points, our concern then becomes finding the median quickly enough, avoiding memory usage issues for the largest cases, and properly using int or long values in the process along the way. We use a counting sort to find the median. Do be sure to use a long (64-bit) integer to calculate the final value.
public class EllysDiggyDiggyHole {
public long getMin(int N, int M, int X, int Y, int A, int B, int C, int D) {
int[] cntX = new int[M];
int[] cntY = new int[M];
for (int i = 0; i < N; i++) {
cntX[X]++; cntY[Y]++;
X = ((X * A + B) & (M - 1));
Y = ((Y * C + D) & (M - 1));
}
int targetX = 0, seenX = cntX[0];
while (seenX * 2 < N)
seenX += cntX[++targetX];
int targetY = 0, seenY = cntY[0];
while (seenY * 2 < N)
seenY += cntY[++targetY];
long ans = 0;
for (int x = 0; x < M; x++)
ans += (long)cntX[x] * Math.abs(x - targetX);
for (int y = 0; y < M; y++)
ans += (long)cntY[y] * Math.abs(y - targetY);
return ans;
}
}
There is a neater way to find the median of a set of numbers in O(N) time and O(sqrt(M)) memory. This problem is one of the popular Interview Problems and its solution would allow us to solve this task with much larger constraints on M (up to around 2^48 instead of 2^24 as it currently is).
The idea is to do two passes over the numbers (in this task, it would be two over X and two over Y). In the first pass we create sqrt(M) buckets (e.g., [0, 4095], [4096, 8191], [8192, 12275], …), and we count how many points fall into each bucket. After that we will know in which of those buckets is the median – and by this its lower and upper bound. On the second pass we only care about numbers which fall in the bucket of the median (between its lower and upper bound), thus we again use an array of sqrt(M) = 4096 cells. Since we know how many numbers are in the buckets smaller than (“to the left of”) the bucket of the median, we know how many points inside the bucket of the median we need to skip in order to find it. This solution was also quite okay for this task (it required much less memory and in practice is even faster, although it does two passes).
Finally, if you wondered about the name of the task, see https://www.youtube.com/watch?v=ytWz0qVvBZ0 or even better https://www.youtube.com/watch?v=34CZjsEI1yU 🙂
KassanErinn
Guest Blogger
