解題區/解題區 - UVa

UVa 12271 - Comparing answers

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

抄答案如何快速檢查？題目是這樣子的，給定任兩點之間的路徑數，輸出從 i->j 兩步可到達的方法數。

現在只需要比對答案是否正確。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
3
2 0 1
1 0 3
1 1 0
5 1 2
5 3 1
3 0 4
3
2 0 1
1 0 3
1 1 0
5 1 2
5 3 2
3 0 4
0

Sample Output

1
2
YES
NO

Solution

從矩陣乘法可以知道兩步內到達的方法數恰好是矩陣 $A \ast A$，假設答案是 B，A 和 B 都是 $n \ast n$ 矩陣，驗證 $A \ast A = B$ 是否正確，$A \ast A$ 用一般的矩陣乘法需要耗費 O(n^3) 的時間。

為了快速驗證，採用一個隨機算法，同乘上一個隨機的 n * 1 矩陣 C，那麼將問題轉換成

$(A \ast (A \ast C)) = B * C$

發現每一步操作可以在 O(n^2) 時間內完成。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <math.h>
#include <iostream>
#include <map>
using namespace std;
// random algroithm, identify A * A = B
// (A * (A * C)) = B * C => O(n^2)
#define MAXN 1024
int A[MAXN][MAXN], B[MAXN][MAXN];
int C[MAXN], D[MAXN], E[MAXN], F[MAXN];
int main() {
    int n;
    while (scanf("%d", &n) == 1 && n) {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &A[i][j]);
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &B[i][j]);
        for (int i = 0; i < n; i++)
            C[i] = rand() + 1;
        for (int i = 0; i < n; i++) {
            int x = 0, y = 0;
            for (int j = 0; j < n; j++)
                x += C[j] * A[i][j], y += C[j] * B[i][j];
            D[i] = x, E[i] = y;
        }
        int ok = 1;
        for (int i = 0; i < n && ok; i++) {
            int x = 0;
            for (int j = 0; j < n; j++)
                x += D[j] * A[i][j];
            F[i] = x;
            ok &= F[i] == E[i];
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}
/*
 */