Problem 673497 · medium · Level 06 Heuristics & Optimization

Putting the Towns on a Two-Number Map

PCA · standardisation · projection · power iteration · deflation · dimensionality reduction

A travel magazine describes every town by numbers in very different units (population in thousands, rainfall in millimetres, temperature in degrees, ...) and wants to print a map on which similar towns sit close together. Give every town k coordinates.

Write map_coordinates(rows, k, rounds) that returns one list of k floats per row, computed exactly like this:

  1. Standardise every feature: subtract its mean and divide by its standard deviation (divide by n inside the square root).
  2. Build the covariance matrix C of the standardised rows (divide by n).
  3. Find k components one after another: start from v = [1.0, 2.0, ..., d], repeat rounds times w = C·v, v = w / |w|, let λ = v·(C·v), and then deflate: C[i][j] ← C[i][j] - λ·v[i]·v[j].
  4. A direction and its opposite are equally good, so fix the sign: if the first entry of v whose absolute value exceeds 1e-6 is negative, flip every entry of v. (Deflation gives the same matrix for either sign.)
  5. A town's coordinate j is the dot product of its standardised row with component j.

town_table(n, seed) builds the tables the tests use; it is available in your code.

Examples

Input:  rows = [[1, 10], [2, 30], [3, 20]], k = 2, rounds = 50
Output: [[-1.7320508075688772, 0.0], [0.8660254037844386, -0.8660254037844386],
         [0.8660254037844386, 0.8660254037844386]]
Explanation: both features have mean 2 and 20 and standard deviations 0.8165 and 8.165, so the
standardised rows are [-1.2247, -1.2247], [0, 1.2247] and [1.2247, 0]. C = [[1, 0.5], [0.5, 1]];
its components are [0.7071, 0.7071] and, after flipping the sign, [0.7071, -0.7071].
(Coordinates that are 0 may come out as tiny numbers such as 1e-17; that is fine.)

Input:  rows = [[120, 800, 11.5], [2400, 650, 12.0], [45, 1400, 9.0], [900, 700, 13.5], [300, 1100, 10.0]],
        k = 2, rounds = 100
Output: [[0.032033495198026715, -0.8018752538937305], [1.8801172363483591, 1.1111054090841395],
         [-2.281703675567643, 0.3784965409809733], [1.4620651398231352, -0.7637484255869887],
         [-1.0925121958018766, 0.07602172941560562]]

Constraints

  • 2 <= n <= 1000, 2 <= d <= 6, 1 <= k <= d, 1 <= rounds <= 200; no feature is constant
  • the tests make sure that C·v is never the zero vector
  • floats are compared with a tolerance of 1e-6

Goals

  • Standardise features with different units before PCA
  • Find the top principal components by power iteration and deflation
  • Fix the sign of each component and project every row onto the components
Starting Python…