April 4, 2017 2017 TCO Algorithm Round 1A Editorials

2017 TCO Algorithm Round 1A Editorials are now here. To make sure you get a deep insight to the TCO Algorithm Problems, our veteran members and algorithm rockstars Egor and Nickolas will be helping us with the Editorials for all the TCO Rounds!

A big thanks to Nickolas for writing the editorials for TCO17 Algorithm Round 1A. Also a big thanks to Egor for reviewing them.
You may discuss the problems in the match discussion forum.
 
 




2017 TCO Algorithm Round 1A – Division I, Level One – PingPongQueue
This was a purely implementation-oriented problem: read the statement carefully and simulate the games and the queue exactly as described. There were some corner cases, for example, if there are only two players in total they’ll always play each other, and if N = 1, after each game both players join the queue. But with careful implementation these cases didn’t require separate handling in the code.
 

Java reference solution:
import java.util.*;
 
public class PingPongQueue {
public int[] whoPlaysNext(int[] skills, int N, int K) {
     int p1 = skills[0], p2 = skills[1];
     Queue<Integer> q = new LinkedList<Integer>();
     for (int i = 2; i < skills.length; ++i)
         q.add(skills[i]);
     int winner = -1, loser = -1;
     int nWins = 0;
     for (int i = 1; i < K; ++i) {
         if (Math.max(p1, p2) != winner)
             nWins = 0;
         nWins++;
         winner = Math.max(p1, p2);
         loser = Math.min(p1, p2);
         q.add(loser);
         p1 = q.remove();
         if (nWins == N) {
             q.add(winner);
             p2 = q.remove();
         } else {
             p2 = winner;
         }
     }
     int[] ret = {p1, p2};
     Arrays.sort(ret);
     return ret;
}
}
 

2017 TCO Algorithm Round 1A – Division I, Level Two CheeseSlicing
This problem can be solved using classic dynamic programming: create a 3D array dp, with dp[X][Y][Z] storing the maximal area of good slices which can be obtained from piece X x Y x Z. Transitions between states correspond to cuts you do; it makes sense to only do cuts which produce a slice of thickness between S and 2*S-1. The answer will be the largest value from the array up to A x B x C piece. Java reference solution:
import java.util.*;
 

public class CheeseSlicing {
public int totalArea(int A, int B, int C, int S) {
     int dp[][][] = new int[A+1][B+1][C+1];   // dp[i][j][k] stores the max area of pieces which can be obtained from i x j x k
     // calculate DP array upwards from S x S x S
     // the return will be the largest value from <= A x B x C
     int max = 0;
     for (int i = S; i <= A; i++)
     for (int j = S; j <= B; j++)
     for (int k = S; k <= C; k++) {
         // this piece can be viewed as one large slice
         int[] dim = {i, j, k};
         Arrays.sort(dim);
         dp[i][j][k] = Math.max(dp[i][j][k], dim[1] * dim[2]);
         max = Math.max(max, dp[i][j][k]);
 
         // try to extend this piece in each direction by doing 1 cut
         // the extending slice must have the smallest dimension >=S
         // but <2*S (otherwise two slices can be done from it)
         for (int sm = S; sm < 2*S && sm <= Math.min(j, k) && i + sm <= A; sm++)
             dp[i + sm][j][k] = Math.max(dp[i + sm][j][k], dp[i][j][k] + j * k);
         for (int sm = S; sm < 2*S && sm <= Math.min(i, k) && j + sm <= B; sm++)
             dp[i][j + sm][k] = Math.max(dp[i][j + sm][k], dp[i][j][k] + i * k);
         for (int sm = S; sm < 2*S && sm <= Math.min(i, j) && k + sm <= C; sm++)
             dp[i][j][k + sm] = Math.max(dp[i][j][k + sm], dp[i][j][k] + i * j);
     }
     return max;
}
}
 

Alternatively, there is a short and beautiful solution which doesn’t require any iteration:

 
import java.util.*;
 
public class CheeseSlicing {
    public int totalArea(int A, int B, int C, int S) {
     if (A < S || B < S || C < S)
     return 0;
     int[] dim = new int[] {A % S + S, B % S + S, C % S + S};
     Arrays.sort(dim);
     dim[0] -= S;
     return (A * B * C - dim[0] * dim[1] * dim[2]) / S;
    }
}

2017 TCO Algorithm Round 1A – Division I, Level Three PolygonRotation
One way to solve this problem is to find approximate solution using disk integration. Split the solid of revolution into narrow slices perpendicular to the Y axis. A slice at coordinate Y0 can be approximated as a conical frustum or a cylinder; to find its radius, check the coordinates at which Y = Y0 line intersects left and right sides of the polygon and pick the one which has larger absolute value. Add up the volumes of these slices, and if they are small enough, the result will be within 1E-9 of the exact answer.
Here is K.A.D.R’s tester solution which uses this technique:

#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
 
inline double ds(pii p1, pii p2, double sy) {
    if (p1.y == p2.y) return abs(max(p1.x, p2.x));
    return abs(p1.x + (double)(p2.x - p1.x) / (p2.y - p1.y) * (sy - p1.y));
}
 
double f(double sy, const vector<int>& X, const vector<int>& Y) {
    int n = L(X);
    double mx = 0.0;
    for(int i = 0; i < n; ++i) {
     if (abs(Y[i] - sy) < 1e-9) {
     mx = max<double>(mx, abs(X[i]));
     }
     int nx = i < n - 1 ? i + 1 : 0;
     if (min(Y[i], Y[nx]) > sy) continue;
     if (max(Y[i], Y[nx]) < sy) continue;
     double cur = ds(mp(X[i], Y[i]), mp(X[nx], Y[nx]), sy);
     mx = max(mx, cur);
    }
 
    return pi * mx * mx;
}
 
class PolygonRotation {
public:
    double getVolume(vector <int> X, vector <int> Y) {
     double a = *min_element(all(Y)), b = *max_element(all(Y));
     const int N = 1000000;
     double s = 0;
     double h = (b - a) / N;
     for (int i = 0; i <= N; ++i) {
     double y = a + h * i;
     s += f(y, X, Y) * ((i == 0 || i == N) ? 1 : ((i & 1) == 0) ? 2 : 4);
     }
     s *= h / 3;
     return s;
    }
};
 

Alternatively, you could find exact answer. One way to do it was to mirror the left side of the polygon with respect of the Y axis, so that you’d have two polylines going from (0, Ymax) to (0, Ymin) in semiplane x >= 0 (one of them could belong to the Y axis). Now draw planes perpendicular to the Y axis that go through each of the vertices of these polylines, as well as through any intersection points of these two polylines. The area of the solid of revolution between any two adjacent planes would be a conical frustum, which can have its area calculated exactly. But the geometry is very tricky to get right, and the code is longer than the one that uses numerical integration approach.
 
Here is the reference solution used for this problem:

import java.util.*;
 
class P {
public int x,y;
P(int x, int y) { this.x=x; this.y=y; }
public P substr(P other) {
     return new P(this.x - other.x, this.y - other.y);
}
public int cross(P other) {
     return this.x * other.y - this.y * other.x;
}
}
 
public class PolygonRotation {
static double interX, interY;
static boolean intersect(P A, P B, P C, P D) {
     //does line A-B intersect line C-D ?
     //if it does, the point of intersection is stored in global "inter" variables
 
     if (Math.min(A.x,B.x) > Math.max(C.x,D.x)) return false;
     if (Math.max(A.x,B.x) < Math.min(C.x,D.x)) return false;
     if (Math.min(A.y,B.y) > Math.max(C.y,D.y)) return false;
     if (Math.max(A.y,B.y) < Math.min(C.y,D.y)) return false;
 
     int den =  (D.y-C.y)*(B.x-A.x) - (D.x-C.x)*(B.y-A.y);
     int num1 = (D.x-C.x)*(A.y-C.y) - (D.y-C.y)*(A.x-C.x);
     int num2 = (B.x-A.x)*(A.y-C.y) - (B.y-A.y)*(A.x-C.x);
 
     if (den == 0)
         return false;   //lines are either parallel or overlap, but this doesn't add NEW intersection points, only old ones
     if (den < 0) {
         den *= -1;
         num1 *= -1;
         num2 *= -1;
     }
     if (num1 <= 0 || num1 >= den || num2 <= 0 || num2 >= den)
         return false;
     interX = A.x + num1 * (B.x-A.x) * 1.0 / den;
     interY = A.y + num1 * (B.y-A.y) * 1.0 / den;
 
     return true;
}
static double volume(double h, double x1, double x2) {
     return h * (x1*x1 + x2*x2 + x1*x2) / 3.0;
}
public double getVolume(int[] xpar, int[] ypar)
{
     int N = xpar.length;
     int iPlus = 0, iMinus = 0;
     int y = ypar[0];
     double x = 0.0;
     double vol = 0.0;
     // on each step we look for the next slice between two adjacent values of y
     // here ys are integer and correspond to vertices
     // iplus and iminus give the indices of previous vertex on each curve
     // we start with (0, Ymax) and continue until both reach (0, Ymin)
     do {
         // figure out next y which will define end of the slice: the smallest of the next ones
         // and which of the indices will advance (possibly both)
         int iPlusNext = iPlus, iMinusNext = iMinus;
         int yNext = Math.max(ypar[iPlus + 1], ypar[(N + iMinus - 1) % N]);
         if (yNext == ypar[iPlus + 1])
             iPlusNext++;
         if (yNext == ypar[(N + iMinus - 1) % N])
             iMinusNext = (N + iMinus - 1) % N;
 
         // x of the next slice is max of xs on each polyline
         // x on polyline can be achieved either as vertex or as intersection with edge
         // and there will be at most one intersection x (one of the points is always a vertex)
         double xNext = 0.0;
         // plus polyline
         if (yNext == ypar[iPlusNext])
             xNext = Math.max(xNext, xpar[iPlusNext]);
         else {
             // find intersection of horizontal line with yNext and segment of plus polyline
             intersect(new P(-101, yNext), new P(101, yNext),
                     new P(xpar[iPlus], ypar[iPlus]), new P(xpar[iPlus + 1], ypar[iPlus + 1]));
             xNext = Math.max(xNext, interX);
         }
         // minus polyline
         if (yNext == ypar[iMinusNext])
             xNext = Math.max(xNext, -xpar[iMinusNext]);
         else {
             // find intersection of horizontal line with yNext and segment of minus polyline
             intersect(new P(-101, yNext), new P(101, yNext),
                     new P(xpar[iMinus], ypar[iMinus]), new P(xpar[(N + iMinus - 1) % N], ypar[(N + iMinus - 1) % N]));
             xNext = Math.max(xNext, -interX);
         }
 
         // figure out whether the slice is a single conical frustum or a combination of two
         if (!intersect(new P(xpar[iPlus], ypar[iPlus]), new P(xpar[iPlus + 1], ypar[iPlus + 1]),
                 new P(-xpar[iMinus], ypar[iMinus]), new P(-xpar[(N + iMinus - 1) % N], ypar[(N + iMinus - 1) % N]))) {
             // one conical frustum
             vol += volume(y - yNext, x, xNext);
         } else {
             // two
             vol += volume(y - interY, x, interX);
             vol += volume(interY - yNext, interX, xNext);
         }
 
         // advance
         iPlus = iPlusNext;
         iMinus = iMinusNext;
         y = yNext;
         x = xNext;
     } while (iPlus == 0 || iMinus == 0 || xpar[iPlus] != 0 && xpar[iMinus] != 0);
 
     return Math.PI * vol;
}
}