xiaq's Blog

[USACO:58] clocks

原题

Consider nine clocks arranged in a 3x3 array thusly:

|-------|    |-------|    |-------|    
|       |    |       |    |   |   |    
|---O   |    |---O   |    |   O   |          
|       |    |       |    |       |           
|-------|    |-------|    |-------|    
    A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

Move	Affected clocks
1	ABDE
2	ABC
3	BCEF
4	ADG
5	BDEFH
6	CFI
7	DEGH
8	GHI
9	EFHI

Example

Each number represents a time accoring to following table:

9 9 12       9 12 12       9 12 12        12 12 12      12 12 12 
6 6 6  5 ->  9  9  9  8->  9  9  9  4 ->  12  9  9  9-> 12 12 12 
6 3 6        6  6  6       9  9  9        12  9  9      12 12 12

[But this might or might not be the `correct' answer; see below.]

PROGRAM NAME: clocks

INPUT FORMAT

Lines 1-3:

Three lines of three space-separated numbers; each number represents the start time of one clock, 3, 6, 9, or 12. The ordering of the numbers corresponds to the first example above.

SAMPLE INPUT (file clocks.in)

9 9 12
6 6 6
6 3 6

OUTPUT FORMAT

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).

SAMPLE OUTPUT (file clocks.out)

4 5 8 9

解题报告

这道题是有所谓的“数学解法”的。注意到：

钟的数量和可能的 move 的数量都是 9。
钟只有四个状态（12, 3, 6, 9）。这四个状态可以用同模域 ℤ₄ （在有限域算术中也记作 GF(2²)）上的 0, 1, 2, 3 表示。把钟“往后播一格”的操作就是简单的加 1。

定义钟的初始状态是向量 a，钟 A-G 分别对应于下标 1-9。定义向量 x，x_i = 执行 Move i 的次数，这是我们要求解的向量。x_i 和 a_i 都是 ℤ₄ 的成员。方程是：

A⋅x = −a ⇒ x = −A^-1⋅a

其中 A 是一 9×9 矩阵，为

matrix([[1, 1, 0, 1, 0, 0, 0, 0, 0],
        [1, 1, 1, 0, 1, 0, 0, 0, 0],
        [0, 1, 1, 0, 0, 1, 0, 0, 0],
        [1, 0, 0, 1, 1, 0, 1, 0, 0],
        [1, 0, 1, 0, 1, 0, 1, 0, 1],
        [0, 0, 1, 0, 1, 1, 0, 0, 1],
        [0, 0, 0, 1, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 1, 0, 1, 1, 1],
        [0, 0, 0, 0, 0, 1, 0, 1, 1]])

矩阵用的是 numpy 的记法（直接复制的……），不过应该是自明的。各行对应的系数就是题目对各 Move 的说明。所以我们要做的就是在 ℤ₄ 上求矩阵 A 的逆。

不过……numpy 貌似并没有提供对有限域算术的支持。所以只能先算出矩阵的行列式和伴随矩阵，然后手工做 ℤ₄ 上的除法。然后……numpy 貌似也不能直接直接计算伴随矩阵，那就只能先算逆再乘上行列式了：

% ipython2 --pylab
...
In [21]: a
Out[21]:
matrix([[1, 1, 0, 1, 0, 0, 0, 0, 0],
        [1, 1, 1, 0, 1, 0, 0, 0, 0],
        [0, 1, 1, 0, 0, 1, 0, 0, 0],
        [1, 0, 0, 1, 1, 0, 1, 0, 0],
        [1, 0, 1, 0, 1, 0, 1, 0, 1],
        [0, 0, 1, 0, 1, 1, 0, 0, 1],
        [0, 0, 0, 1, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 1, 0, 1, 1, 1],
        [0, 0, 0, 0, 0, 1, 0, 1, 1]])

In [22]: det(a)
Out[22]: 4.9999999999999982

In [23]: int_(round_(-inv(a) * 5) % 4)
Out[23]:
array([[1, 2, 1, 2, 2, 3, 1, 3, 0],
       [1, 1, 1, 1, 1, 1, 2, 0, 2],
       [1, 2, 1, 3, 2, 2, 0, 3, 1],
       [1, 1, 2, 1, 1, 0, 1, 1, 2],
       [1, 2, 1, 2, 3, 2, 1, 2, 1],
       [2, 1, 1, 0, 1, 1, 2, 1, 1],
       [1, 3, 0, 2, 2, 3, 1, 2, 1],
       [2, 0, 2, 1, 1, 1, 1, 1, 1],
       [0, 3, 1, 3, 2, 2, 1, 2, 1]])

于是……用得到的矩阵乘上 a 就可以了。写法的话，可以把系数存成数组然后实现一下乘法，或者手写也行（因为维数也只有 9）。

Ref

USACO 答案中的 Pascal 程序……以及这里。