2017 TCO Algorithm Austin Regional Round Editorials

The algorithm match editorials of the first regional event of TCO17 are now published. Thanks to Nickolas for writing these interesting problems and also writing the editorials for them. The event was only open to members who attended the event on-site, however if you wish to practice the problems, they are now available in practice rooms.
If you wish to discuss the problems or editorials you may post in the match discussion forum.
 
2017 TCO Algorithm Austin Regional Round - Division I, Level One RainbowSocks

Since there are at most 50 socks, the solution is very simple: you can just try all possible pairs of two different socks that you can get, count the pairs which turn out to be acceptable and in the end divide this number by the total number of different pairs of socks. This has O(N^2) complexity.
public class RainbowSocks {
public double getPairProb(int[] socks, int colorDiff) {
int nP = 0;
for (int i = 0; i < socks.length; ++i)
for (int j = 0; j < i; ++j)
if (Math.abs(socks[i] - socks[j]) <= colorDiff)
nP++;
int totalP = S * (S - 1) / 2;
return nP * 1.0 / totalP;
}
}


2017 TCO Algorithm Austin Regional Round - Division I, Level Two PlusSign

The most straightforward approach is as follows:
Try all possible sizes of the plus (the size of the bounding box and the size of white squares in the corners).
Try all possible positions of the plus (row and column of the center).
Once you have a fixed position and size of the plus, iterate over all pixels of the grid. If a black pixel is outside of the plus (outside of the bounding box or within one of the white pixels in the corners), this size and position can't produce a valid plus. If a white pixel is inside of the plus, increment the number of pixels which have to be painted black to create this plus.
Choose the plus with the smallest number of pixels which have to be painted.
Implemented with no optimizations, this solution has O(N^6) complexity, where N is the larger of the dimensions of the grid, but is sufficiently fast to pass the system testing even in Java.
There is a smarter solution that works in O(N^4):
Try all possible positions of the plus (row and column of the center).
Once you have a fixed position of the plus, iterate over all black pixels of the grid and figure out the smallest dimensions of the plus sign which could cover all black pixels.
Check whether a plus with these dimensions fits within the grid; if it does, calculate the number of pixels to be painted as the number of black pixels in the plus minus the number of black pixels in the original grid.
Choose the plus with the smallest number of pixels which have to be painted.
Here is Java code of this implementation:
import java.util.*;
public class PlusSign {
public int draw(String[] pixels) {
// can't have a plus less than 3 x 3
if (pixels.length < 3 || pixels[0].length() < 3)
return -1;
// store the coordinates of black pixels separately
int nb = 0;
for (int r = 0; r < pixels.length; ++r)
for (int c = 0; c < pixels[0].length(); ++c)
if (pixels[r].charAt(c) == '#')
nb++;
int[] br = new int[nb], bc = new int[nb];
int ind = 0;
for (int r = 0; r < pixels.length; ++r)
for (int c = 0; c < pixels[0].length(); ++c)
if (pixels[r].charAt(c) == '#') {
br[ind] = r;
bc[ind] = c;
++ind;
}
int minExtra = -1;
// try all coordinates of the center of the plus
// don't need to try cells on the border of the grid, as they don't correspond to valid plus anyways
for (int pr = 1; pr + 1 < pixels.length; ++pr)
for (int pc = 1; pc + 1 < pixels[0].length(); ++pc) {
int minLength = 1, minWidth = 0;
for (int i = 0; i < nb; ++i) {
int dr = Math.abs(pr - br[i]);
int dc = Math.abs(pc - bc[i]);
minLength = Math.max(minLength, Math.max(dr, dc));
minWidth = Math.max(minWidth, Math.min(dr, dc));
}
// check that this plus can fit into the grid
if (Math.min(pr, pc) - minLength < 0 || pr + minLength >= pixels.length ||
pc + minLength >= pixels[0].length())
continue;
// check that this is a valid plus (not a square)
if (minLength == minWidth)
continue;
// total size of the plus - number of blacks already there
int nTotal = (1 + 2 * minLength) * (1 + 2 * minLength) - 4 * (minLength - minWidth) * (minLength - minWidth);
if (minExtra == -1 || minExtra > nTotal - nb)
minExtra = nTotal - nb;
}
return minExtra;
}
}


2017 TCO Algorithm Austin Regional Round - Division I, Level Three AroundTheWall

As is often the case with computational geometry, the idea of the solution is fairly obvious but it takes a lot of time and care to implement it considering all the corner cases.
The first insight necessary to solve the problem is that the round robot or radius R going around a linear wall can be replaced with a point (robot’s center) going around a wall of a more complex structure: a circle of radius R with center at (0,0) plus an impassable area of width R to the both sides of positive direction of X axis. Hereafter we’ll refer to this structure of the wall as just “the wall”.
The second insight is that the robot always takes one of the two possible paths from (x1,y1): either it goes directly to the point (x2,y2) in a straight line (if this route doesn’t intersect the wall) or it goes in a straight line to some point on the circular part of the wall (at distance R from origin), goes along a section of the circle and then goes in a straight line to (x2,y2).
The robot can take a direct route if two conditions hold:
The segment (x1,y1)-(x2,y2) doesn’t intersect the line (0,0)-(1001,0) (the wall is infinite but since both points have x-coordinates less than or equal to 1000, we don’t need to check for intersection with longer part of the wall).
The distance from (0,0) to the segment (x1,y1)-(x2,y2) must be greater than or equal to R.
If the robot takes the direct route, its length is just the length of the segment (x1,y1)-(x2,y2). Till this point all calculations can be done in integers to avoid any imprecision arising from floating-point calculations.
If the robot can’t take the direct route, we need to find tangents from point (x1,y1) to the circle of radius R with center (0,0) which touch the circle in points with negative x-coordinates (there can be one or two of them), do the same for point (x2,y2), and for each combination of these tangents calculate the length of the path which uses them. This requires a lot of care, since depending on how you calculate the tangents there can be various special cases. One such case to remember is the points (x1,y1) and/or (x2,y2) can lie on the circle itself.
Here is commented Java code:
import java.util.*;
class P {
public long x, y;
public P(long x1, long y1) {
x = x1;
y = y1;
}
public long d2() {
return x*x + y*y;
}
public P minus(P other) {
return new P(x - other.x, y - other.y);
}
}
class Pd {
public double x, y;
public Pd(double x1, double y1) {
x = x1;
y = y1;
}
}
public class AroundTheWall {
static final long maxX = 1001;
static long dot(P p1, P p2) {
return p1.x * p2.x + p1.y * p2.y;
}
static long cross(P p1, P p2) {
return p1.x * p2.y - p2.x * p1.y;
}
// check whether a-b segment intersects c-d segment (1-dimension)
static boolean boundBoxIntersect(long a, long b, long c, long d) {
return Math.max(Math.min(a, b), Math.min(c, d)) <=
Math.min(Math.max(a, b), Math.max(c, d));
}
// calculate oriented area of ABC triangle
static long orientedAreaSign(P a, P b, P c) {
long area = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
return area == 0 ? 0 : area / Math.abs(area);
}
// check whether segment AB intersects segment CD
static boolean intersect(P a, P b, P c, P d) {
// two segments intersect if 1) their bounding boxes intersect and 2) oriented areas of triangles have different signs
return boundBoxIntersect(a.x, b.x, c.x, d.x) &&
boundBoxIntersect(a.y, b.y, c.y, d.y) &&
orientedAreaSign(a, b, c) * orientedAreaSign(a, b, d) <= 0 &&
orientedAreaSign(c, d, a) * orientedAreaSign(c, d, b) <= 0; } static boolean canGoStraight(P p1, P p2, int r) { // robot can go straight if segment p1-p2 is at distance >= r from the wall
// we know that the distance from each point to the wall is >= r, so only need to check
// 1. whether p1-p2 intersects (0,0)-(maxX,0)
P p0 = new P(0, 0);
P pEnd = new P(maxX, 0);
if (intersect(p1, p2, p0, pEnd))
return false;
// 1. whether distance from (0,0) to p1-p2 is < r // this can only happen if this distance is achieved in the middle of the segment (not at ends) if (dot(p0.minus(p1), p1.minus(p2)) > 0)
// p1 is the nearest point of the segment to p0 - distance is >= r
return true;
if (dot(p0.minus(p2), p2.minus(p1)) > 0)
// p2 is the nearest point of the segment to p0 - distance is >= r
return true;
P segm = p2.minus(p1);
long cp = cross(segm, p0.minus(p1));
return cp * cp >= r * r * segm.d2();
}
// finds endpoints of tangents from P to circle (0,0)-r
Pd[] tangents(P v, int r) {
// always return both endpoints, they will be checked and ignored later
Pd[] ret = new Pd[2];
// if the point is on the circle, return the point itself (twice)
if (v.d2() == r*r) {
ret[0] = new Pd(v.x, v.y);
ret[1] = new Pd(v.x, v.y);
} else if (v.y == 0) {
double x = r * r * 1.0 / v.x;
double y = r * Math.sqrt(1 - r * r * 1.0 / v.x / v.x);
ret[0] = new Pd(x, y);
ret[1] = new Pd(x, -y);
} else {
double rt1 = v.x * 1.0 / v.y;
double rt2 = r * r * 1.0 / v.y;
double d4 = Math.pow(rt1 * rt2, 2) - (rt2 * rt2 - r * r) * (1 + rt1 * rt1);
double x = (rt1 * rt2 + Math.sqrt(d4)) / (1 + rt1 * rt1);
double y = rt2 - x * rt1;
ret[0] = new Pd(x, y);
x = (rt1 * rt2 - Math.sqrt(d4)) / (1 + rt1 * rt1);
y = rt2 - x * rt1;
ret[1] = new Pd(x, y);
}
return ret;
}
// find distance on circle between points p1 and p2
double circDist(Pd p1, Pd p2, int r) {
double alpha1 = Math.atan2(p1.y, p1.x);
if (alpha1 < 0)
alpha1 += 2 * Math.PI;
double alpha2 = Math.atan2(p2.y, p2.x);
if (alpha2 < 0)
alpha2 += 2 * Math.PI;
return Math.abs(alpha1 - alpha2) * r;
}
public double minDistance(int r, int x1, int y1, int x2, int y2) {
P p1 = new P(x1, y1);
P p2 = new P(x2, y2);
if (canGoStraight(p1, p2, r)) {
return Math.sqrt(p1.minus(p2).d2());
}
// otherwise, have to go around the wall
// find tangent from p1 and p2 to the circle (0,0)-r which does NOT intersect (0,0)-(maxX,0)
// (or which intersects X axis at negative point)
// add lengths of tangents and part of the circle between them
Pd[] tan1 = tangents(p1, r);
Pd[] tan2 = tangents(p2, r);
double minDist = maxX * maxX;
for (int i = 0; i < 2; ++i)
for (int j = 0; j < 2; ++j) { // check whether this pair of points can produce a valid path if (tan1[i].x > 0 || tan2[j].x > 0)
continue;
double d = circDist(tan1[i], tan2[j], r);
d += Math.sqrt(Math.pow(p1.x - tan1[i].x, 2) + Math.pow(p1.y - tan1[i].y, 2));
d += Math.sqrt(Math.pow(p2.x - tan2[j].x, 2) + Math.pow(p2.y - tan2[j].y, 2));
minDist = Math.min(minDist, d);
}
return minDist;
}
}