Google Code Jam is an annual, international programming competition. Similar to ACM/ICPC but less restrictive since anyone who registers online can compete. Also the contest is not team based. It consists of several stages until its final onsite round. The very first stage qualification round recently took place.

I have checked the problems and proposed some solutions to those.

Disclaimer: Proposed ideas and implementations are not official, ideal, nor coded optimally. Instead, this is only one way to tackle the problem. Feel free to contact me to feedback possible optimizations!

Prerequisite: This explanation assumes that you are familiar with the terms, variables and the problem itself as defined on the official Code Jam page. If you have not read the problem description, please take your time and go through all of it.

Observations

Let say that we represent the rotation of the cube using normal vectors of it’s 3 orthogonal faces: \(\vec{u}, \vec{v}, \vec{w}\). That are initially:

  • \(\vec{u} = \begin{bmatrix}1 & 0 & 0\end{bmatrix}\)
  • \(\vec{v} = \begin{bmatrix}0 & 1 & 0\end{bmatrix}\)
  • \(\vec{w} = \begin{bmatrix}0 & 0 & 1\end{bmatrix}\)

Rotating the cube is equivalent of applying a rotation to these vectors. Luckily the cube is centered at \((0,0,0)\), this simplifies the rotation procedure. To rotate any of \(\vec{u}, \vec{v}, \vec{w}\), we only need to multiply the vector with a rotation matrix.

Info: If the cube was not centered at (0,0,0), we would need to shift it back to origin, apply rotation then shift it back its original center. Rotation matrices rotate with respect to origin of the coordinate system.

Furthermore, let:

  • \(\theta_x\) denote angle of rotation of the cube about the x-axis
  • \(\theta_y\) denote angle of rotation of the cube about the y-axis
  • \(\theta_z\) denote angle of rotation of the cube about the z-axis

We notice that \(\theta_y\) is ineffective on the final value that we want to compute, the area of the shadow, let’s name it \(A\). That is because the normal of the plane we want to project to and y-axis are aligned. Thus, we only need to search for 2 values, \(\theta_x, \theta_z\).

Next questions is, given \(\theta_x, \theta_z\) how do we compute area \(A\)?

The projection is captured with dot product operation in Euclidian spaces. Let \(\vec{n}\) be the normal vector of the plane \(y = -3\) (our target plane in the problem), then area of the shadow/projection is given by \(A = |\vec{n} * \vec{u}| + |\vec{n} * \vec{v}| + |\vec{n} * \vec{w}|\) where \(*\) represents dot product and \(|.|\) represents absolute value operation.

We use the following notation to denote the rotated version of vector \(\vec{v}\):

Let \(\theta\) represent the parameter pair, \( \theta = \begin{bmatrix}\theta_x & \theta_z \end{bmatrix} \)
Let \( \vec{v_\theta} = rot_{\theta_{xy}}(\vec{v}) = rot_x(\theta_x, rot_z(\theta_z, \vec{v})) \), where:

  • \( rot_z(\theta_z, \vec{v}) \) rotates a vector \(\vec{v}\) by \(\theta_z\) degrees about the z-axis.
  • \( rot_x(\theta_x, \vec{v}) \) rotates a vector \(\vec{v}\) by \(\theta_x\) degrees about the x-axis.
  • \(\vec{v_\theta}\), is the resulting vector when \(\vec{v}\) is first rotated \(\theta_z\) degrees about z-axis and then rotated \(\theta_x\) degrees about x-axis.
  • Note that order of rotation matrices applied matters. Applying the the rotation about x-axis first, z-axis second does not necessarily yield the same output vector. You can notice this asymmetry in the definition of rotation matrices.

Next we calculated what \(\vec{v_\theta}\) is equivalent of analytically. It essential is a small series of matrix-matrix-vector multiplication.

\[\vec{v_\theta} = \begin{bmatrix} & x*cos\theta_z - y*sin\theta_z \\ & x*cos\theta_x*sin\theta_z + y*cos\theta_x*cos\theta_z - z*sin\theta_x \\ & x*sin\theta_x*sin\theta_z + y*sin\theta_x*cos\theta_z + z*cos\theta_x \\ \end{bmatrix}\]

where \(\vec{v} = \begin{bmatrix}x & y & z\end{bmatrix}^T\)

Let’s say now we managed to rotate a normal vector of a face of the cube. To compute the area that this face generates on the plane, we will calculate dot product of it with the vector \((0,1,0)\) which is the normal vector of the plane. This is simply selecting the 2nd component of the rotated vector:
\( x * cos\theta_x * sin\theta_z + y * cos\theta_x * cos\theta_z - z * sin\theta_x \)

We need to do this for normals of all three faces of the cube: \((1,0,0)\), \((0,1,0)\) and \((0,0,1)\). This effectively means that:

  • Set \(x = 1, y = 0, z = 0\) in the equation and compute area due to this face of the cube.
  • Set \(x = 0, y = 1, z = 0\) in the equation and compute area due to this face of the cube.
  • Set \(x = 0, y = 0, z = 1\) in the equation and compute area due to this face of the cube.

We calculate areas due to each the of the 3 faces of the cube and add them together. We get the following equation that gives us the total area \(A_\theta\) after a rotation \(\theta\) applied to the cube:

\[A_\theta = |cos\theta_x*sin\theta_z| + |cos\theta_x*cos\theta_z| + |-sin\theta_x|\]

Let’s plot a heatmap of this function with respect to \(\theta_x\) and \(\theta_z\):


Approach

We would ideally like to find an analytical solution which would run in \(O(1)\), but notice that if we fix \(A\) and leave \(\theta_x\) and \(\theta_z\) variable, we have an underdetermined problem. One equation and two variables. One can also notice the same phenomenon in the heatmap shown above: there are multiple (in fact infinitely many) locations with the same color.

  • One global minimimum is located at \(\theta_x = 0\) and \(\theta_z = 0\)
  • The global maximum is observed when \(\theta_z = 45\) and for some value of \(\theta_x\)
  • Notice that the heatmap is not symmetric with respect to both variables.

A path going from a global minimum to the global maximum observes all possible values along the way. The path in this case path would imply an extra constraint, which makes this problem determined. For analytical ease, we would like a follow two simple paths, as shown on on the heatmap with two arrows: horizontal and the vertical.

In general, the idea is:

  • When we are asked an \(A\) that is less than the value at the end of horizontal arrow:
    • Fix \(\theta_x\) to 0 degrees and solve analytically for \(\theta_z\).
    • We calculated the analytical solution for this case as following:
    • \(\theta_z = \frac{sin^{-1}(A^2-1)}{2}\)
  • Similarly, when we are asked an \(A\) that is greater than or equal to the value at the end of horizontal arrow:
    • Fix \(\theta_z\) to 45 degrees and solve analytically for \(\theta_x\).
    • We calculated the analytical solution for this case as following:
    • \(\theta_x = 2*tan^{-1} \left( \frac{\sqrt{3-A^2}+1}{A+\sqrt{2}} \right)\)

Implementation

The following is a C++ implementation of the approach mentioned.

/**
 * Ans is a wrapper class to store answers
 * Case is a wrapper class to store cases
 */

Ans solveCase(Case &cs){
    Ans ans;

    double x = 0;		// theta_x (in radians)
    double z = PI/4;		// theta_z (in radians)
    double thres = area(x,z);	// threshold area
    
    if(cs.A < thres){
    	// analytic soln for the points along horizontal arrow
        z = asin(cs.A*cs.A-1)/2; 
    }else{
    	// analytic soln for the points along vertical arrow
        double num = sqrt(3-cs.A*cs.A)+1;
        double denom = cs.A + sqrt(2);
        x = 2*atan(num/denom);
    }
    
    double angleX = rad2deg(x);
    double angleZ = rad2deg(z);    

    // initialize face vectors
    Point p1(0.5,   0,   0);
    Point p2(  0, 0.5,   0);
    Point p3(  0,   0, 0.5);

    // rotate face vectors
    ans.p1 = rotate(x, z, p1); 
    ans.p2 = rotate(x, z, p2);
    ans.p3 = rotate(x, z, p3);

    return ans;
}

And the helper functions are defined as following:

double area(double x, double z){
    return abs(cos(x)*sin(z)) + abs(cos(x)*cos(z)) + abs(sin(x));
}

Point rotate(double x, double z, Point& p){
    Point pr;
    pr.x = p.x * cos(z) - p.y * sin(z);
    pr.y = p.x * cos(x) * sin(z) + p.y * cos(x) * cos(z) - p.z * sin(x);
    pr.z = p.x * sin(x) * sin(z) + p.y * sin(x) * cos(z) + p.z * cos(x);
    return pr;
}

Remarks

Math/geometry based problems are often encountered in programming contests. For this particular instance, we sought an analytical solution that comes with the benefit of the short implementation and runtime. The drawback of this approach is that we had to know/find the mathematical equalities and further notice the simplifying characteristics of those in order to hash out the final closed form equation on paper.