-
Notifications
You must be signed in to change notification settings - Fork 1
/
2005 S3.cpp
147 lines (85 loc) · 4.82 KB
/
2005 S3.cpp
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
/*
2005 S3 - Quantum Operations
Difficulty: Medium
For this problem, there's no special algorithm, you quite litearly just implement the situation
Multiplying the matrices will require decent knowledge of array manipulation
As for checking the min/max values and the rows as well as the columns
It suffices to search linearly with 2 for loops since the final matrice will be 1024x1024 at most
*/
#include <iostream>
#include <vector>
#include <set>
int main(){
int N;
std::cin >> N;
//Matrix 1 will represent the first/original matrix, Matrix 2 will the matrix we're multiplying by
std::vector<std::vector<int>> matrix1;
std::vector<std::vector<int>> matrix2;
int matrix1_height, matrix1_width, matrix2_height, matrix2_width;
//Get matrix 1
//I will be creating the first matrix on its own. There's no gurantee that there's going to be at least 2 matrices
std::cin >> matrix1_height >> matrix1_width;
matrix1.resize(matrix1_height, std::vector<int> (matrix1_width)); //Resize to prevent having to repeatedly resize the vector with push back
for (int i = 0; i < matrix1_height; i++){
for (int j = 0; j < matrix1_width; j++){
std::cin >> matrix1[i][j];
}
}
//For the additional matrices if they exist
//N - 1 since we've already done the first matrix
for (int n = 0; n < N - 1; n++){
//Get next matrix
std::cin >> matrix2_height >> matrix2_width;
matrix2.clear(); //Very important to clear the vector before using it again. Forgetting to do so will result in some really wonky errors like invalid pointer or munchunk
matrix2.resize(matrix2_height, std::vector<int> (matrix2_width));
//Obtain the next matrix values
for (int i = 0; i < matrix2_height; i++){
for (int j = 0; j < matrix2_width; j++){
std::cin >> matrix2[i][j];
}
}
//Multiply the matrices
std::vector<std::vector<int>> matrix1_copy = matrix1; //I will be changing matrix1's values directly, therefore I need a copy of it before it was changed to perform multiplication
matrix1.clear(); //REMEMBER TO CLEAR MEMORY BEFORE USING
matrix1.resize(matrix1_height * matrix2_height, std::vector<int> (matrix1_width * matrix2_width));
//To multiply them I will be using 4 for loops, the first 2 for loops correspond to the value of matrix1 whereas the other 2 for loops correspond to the values of the second matrix
for (int i = 0; i < matrix1_height; i++){
for (int j = 0; j < matrix1_width; j++){
for (int y = 0; y < matrix2_height; y++){
for (int x = 0; x < matrix2_width; x++){
//I can't really prove to you this formula. But intuitively it makes sense. A value in matrix1 at i, j will be transformed to position i * matrix2_height + the current row number in matrix 2, j + matrix1 width + the current column number in matrix 2
matrix1[i * matrix2_height + y][j * matrix2_width + x] = matrix1_copy[i][j] * matrix2[y][x];
}
}
}
}
matrix1_height *= matrix2_height; //Remember to adjust the height and width values so that you can resize the vector correctly later
matrix1_width *= matrix2_width;
}
//Finding the min/max element, row sum and column sum
//Remember that set is always ordered, so naturally if we just insert everything into a set, the minimum will be the first element and the maximum will be the last element
std::set<int> elements;
std::set<int> rowSums;
std::set<int> colSums;
int rowSum = 0, colSum = 0;
//Find row sums and elements in the final matrix
for (int i = 0; i < matrix1_height; i++){
for (int j = 0; j < matrix1_width; j++){
elements.insert(matrix1[i][j]);
rowSum += matrix1[i][j];
}
rowSums.insert(rowSum);
rowSum = 0; //Clean up, prepare for the next row
}
//Find the column sums
for (int j = 0; j < matrix1_width; j++){
for (int i = 0; i < matrix1_height; i++){
colSum += matrix1[i][j];
}
colSums.insert(colSum);
colSum = 0; //Clean up, prepare for next column
}
//Output the answer
std::cout << *elements.rbegin() << '\n' << *elements.begin() << '\n' << *rowSums.rbegin() << '\n' << *rowSums.begin() << '\n' << *colSums.rbegin() << '\n' << *colSums.begin();
return 0;
}