Problem
In a place in Southwestern Europe, the name of which I do not wish to recall, not long ago there were $n$ cities connected by unidirectional roads, with possibly more than one road connecting a city to another one, or even to itself. As a homework assignment for your geography class, you need to calculate the number of paths of length exactly two that were between each pair of cities. However, you’ve been too busy celebrating the Spanish victory in the World Cup, so now you are copying the answers from your friend. You would like to make sure his answers are correct before handing in your homework.
Input
The input consists of several test cases, separated by single blank lines. Each test case begins with a line containing the integer $n$ $(1 \leqslant n \leqslant 1000)$. The following $n$ lines contain $n$ elements each, with element $j$ of line $i$ being the number of roads from city $i$ to city $j$ (a number between $0$ and $10$, inclusive). After that, there will be $n$ lines. Each will contain $n$ elements, with element $j$ of line $i$ being the answer from your friend for the number of length-$2$ paths from city $i$ to city $j$; it will be an integer between $0$ and $100000$ inclusive.
The test cases will finish with a line containing only the number zero (also preceded by a blank line).
Note: Large input file; use fast I/O routines.
Output
For each case, your program should output a line. The content of this line should be «YES» if your classmate’s solution to the assignment is right, and «NO» otherwise.
Tests
| № | Input | Output |
| 1 | 3 2 0 1 1 0 3 1 1 0 5 1 2 5 3 1 3 0 43 2 0 1 1 0 3 1 1 0 5 1 2 5 3 2 3 0 40 |
YES NO |
| 2 | 5 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 54 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1435 1 2 7 8 9 4 5 8 7 3 1 0 2 5 6 1 0 0 5 4 1 7 2 5 9 33 75 55 142 170 42 4 90 157 154 14 44 23 73 95 10 30 15 53 65 45 100 85 137 1430 |
YES NO |
| 3 | 1 2 21 2 40 |
NO YES |
| 4 | 9 1 5 7 9 10 6 3 3 6 10 2 0 5 10 4 3 3 5 7 10 4 1 4 0 4 4 2 5 4 0 1 7 0 5 3 2 7 0 6 1 7 5 2 2 2 7 4 0 1 1 8 6 6 3 0 4 9 2 1 8 0 3 7 8 7 7 3 5 0 10 8 2 1 0 5 8 8 8 3 3 1 287 178 173 129 293 196 195 180 134 182 123 203 174 287 214 150 143 144 202 143 163 158 261 150 126 128 148 125 78 153 108 182 137 82 89 109 156 141 157 108 183 149 120 120 105 166 145 166 147 192 199 157 161 147 207 159 98 105 176 141 159 149 81 243 232 270 182 300 197 184 192 201 213 152 128 61 176 142 160 147 1000 |
YES |
Code
|
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 |
#define _CRT_SECURE_NO_WARNINGS // preprocessor property for Visual Studio #include <stdio.h> using namespace std; inline void array_input(int **&arr, int &n) { // input function to avoid code repetition; it is optional for (int i = 0; i < n; ++i) { arr[i] = new int[n]; for (int j = 0; j < n; ++j) { scanf("%d", &arr[i][j]); } } } inline void array_delete(int **&arr, int &n) { // array deletion to prevent memory leaks for (int i = 0; i < n; ++i) { delete[]arr[i]; } delete[]arr; } int main() { int n; // processing 1 testcase at a time while (scanf("%d", &n) && n) { // testcases are processed until the delimiter 0 occurs int **number_of_roads = new int *[n]; // array to square array_input(number_of_roads, n); int **friend_answers = new int *[n]; // array to compare calculated values to array_input(friend_answers, n); int correct_answer; // the actual number of length-2 routes isn't stored bool is_correct = true; // flag to stop calculation when error detected for (int i = 0; i < n; ++i) { for (int j = 0; j < n && is_correct; ++j) { // if an error is detected the is_correct flag stops the cycle, if no error is detected j reaches n correct_answer = 0; for (int k = 0; k < n; ++k) { correct_answer += number_of_roads[i][k] * number_of_roads[k][j]; // a single element of squared matrix } if (friend_answers[i][j] != correct_answer) { is_correct = false; // set the flag to stop calculation } } } printf(is_correct ? "YES\n" : "NO\n"); // output array_delete(number_of_roads, n); array_delete(friend_answers, n); } return 0; } |
Solution
The problem statement says that element $j$ of line $i$ of the matrix corresponds to the number of unidirectional roads from city $i$ to city $j$. Thus, we have an adjacency matrix of a directed unweighted graph. We need to find the number of paths of fixed length $k = 2$ for each pair of cities and compare them to our friend’s answer from the output. Adjacency matrix $g_{n \times n}$ of a directed unweighted graph contains the number of routes of length $k = 1$ between each pair of vertices. The solution is iterative: adjacency matrix $g$ corresponds to paths of length $k = 1$. Let $g = d_k$. For $k + 1$ we have: $d_{k+1}[i][j] = \sum\limits_{p=1}^n d_k[i][p] \cdot g[p][j]$, i.e. the product of matrices $d_k$ and $g$. Conclusion: to count the routes of fixed length we have to raise the adjacence matrix to the correspondent power.
Testcases are processed one at a time and after each the answer is given. Firstly, two 2D arrays of size $n \times n$ are initialized and entered: one for storing the matrix with the amounts of paths and the other with our friend’s answers. There is a warning about a big input file in the problem statement. Thus we use C style for I/O operations. Secondly, the first matrix is squared and the results are compared to the friend’s answers one by one. Once an error is detected the loop ends and the answer «NO» is displayed. Otherwise the loop reaches its end and «YES» is displayed. It is necessary that both arrays are deleted before processing the next testcase to prevent memory leaks.
