Codeforces Round #359 (Div. 1) - C. Optimal Point

Problem Statement:
http://codeforces.com/contest/685/problem/C

Summary:
Find the minimum point M (x, y, z) in Z^3 such that the maximum Manhattan distance between M and a set of points {(x[i], y[i], z[i]) in Z^3} of size <= 100000 is the minimum. Manhattan distance between two points (x, y, z) and (a, b, c) is defined as |x-a| + |y-b| + |z-c|. Furthermore, x, y and z is in [-10^18, 10^18].

Codeforces Round 285 Div. 1 Problem D - Misha and XOR

Problem Statement:
504D - Misha and XOR

Solution:
Another tedious problem. The strategy is to apply the idea of linear independence. Let's say we already transformed every decimal strings into binaries, and place them in rows such that they form a matrix of 0s and 1s. We want to apply Gauss Elimination such that we achieve linear independence between the rows. Eg :

numbers     binaries
7           111
5           101

initial matrix:
111
101

linear independence between rows, after Gauss Elimination:
111
010

Codeforces Round 285 (Div. 2 C or Div. 1 A) - Misha and Forest

Problem Statement:
501C - Misha and Forest

Solution:
An interesting mix of tree structure and linear algebra. Since we are given the pair \((\text{degree}_v, s_v)\) for each v, we can approach it in an intuitive manner:
1. We will maintain a graph G with vertices v but with no edges just yet. So initially all vertices in G has no neighbouring vertices.
2. Iteratively, we would like to find a vertex v such that the difference between the number of neighbours it currently has and \(\text{degree}_v\) is at most 1. This means that v is short of one vertex. Furthermore, this means that we can determine what vertex is that exactly in O(M) where M is the number of adjacent vertices v currently has, as follows:

a bit of matrix: LUP Decomposition

Scratch note:

Given system of linear equation \(Ax = b\), solve for \(x\).

One of the method to solve this classic linear algebra is described here called "LUP decomposition". LUP is itself an abbreviation for Lower, Upper, and Permutation Matrixes. The idea is that in a Gauss Elimination process, we are actually trying to transform a matrix into its row equivalent upper or lower triangular matrix. The method here owes to the insight from Gauss Elimination.

Recursively:

1. We swap the first row in \(A\) with another row such that the first element in \(A\) is not zero. Call this permutation \(Q\), and hence the resulting matrix \(QA\).
2. Rewrite QA as
\( \left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)

3. Let \(P =
\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)
Q
\)
Where \(P'(A-vw^T/a_{k1})=L'U'\)
Hence we have
\(PA =

\left(
\begin{array}{cc}
1 & 0 \\
0 & P'
\end{array}
\right)

\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & I_{n-1}
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & A - vw^T/a_{k1}
\end{array}
\right)
\)

which simplifies to
\(PA =
\left(
\begin{array}{cc}
1 & 0 \\
v/a_{k1} & L'
\end{array}
\right)

\left(
\begin{array}{cc}
a_{k1} & w^T \\
0 & U'
\end{array}
\right)
\)
Or \(PA = LU\)