[DAAP] Added exercises from second exam

5 files changed, 367 insertions, 0 deletions

diff --git a/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-FirstTry.cpp b/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-FirstTry.cpp
new file mode 100644
index 0000000..00e5eab
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-FirstTry.cpp
@@ -0,0 +1,129 @@
+#include <iostream>
+#include <string>
+#include <queue>
+#include <vector>
+#include <algorithm>
+#include <utility>
+using namespace std;
+
+/*
+ * .....# 6 + 7 + 8 + 9 + 10 = 21 + 19 = 40
+ * .###.# 5
+ * ...#.# 4 + 5 + 6 = 15
+ * .##### 3
+ * ..^..# 2 + 1 + 0 + 1 + 2 = 6
+ * ######
+ *
+ *
+3 3 1
+.##
+...
+##.
+1 1
+
+
+10 10 10
++.####...#
+####.#.##.
+...#....##
+.###......
+###.....#.
+..#.......
+##.......#
+..#.##.###
+...###.##.
+.#...#...#
+1 1
+1 7
+2 10
+3 1
+6 1
+8 1
+9 10
+10 8
+5 2
+1 3
+
+
+ */
+
+typedef pair<long long, long long> loc;
+
+long long N, M, K;
+loc dir[] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
+
+loc operator+(const loc& p1, const loc& p2) {
+	return { p1.first + p2.first, p1.second + p2.second };
+}
+
+
+vector<vector<long long>> djikstra(loc s, vector<string>& matrix) {
+	priority_queue<pair<long long, loc>, vector<pair<long long, loc>>, less<pair<long long, loc>>> q;
+	vector<vector<bool>> visited(N, vector<bool>(M));
+	vector<vector<long long>> dist(N, vector<long long>(M, -1));
+	dist[s.first][s.second] = 0;
+	q.push({ 0, s });
+	while (!q.empty()) {
+		loc c = q.top().second;
+		q.pop();
+
+		visited[c.first][c.second] = true;
+		for (int i = 0; i < 4; i++) {
+			loc ne = c + dir[i];
+			if (0 > ne.first || ne.first >= N || 0 > ne.second || ne.second >= M || visited[ne.first][ne.second] || matrix[ne.first][ne.second] == '#') continue;
+
+			if (dist[ne.first][ne.second] == -1 || dist[c.first][c.second] + 1 < dist[ne.first][ne.second]) {
+				dist[ne.first][ne.second] = dist[c.first][c.second] + 1;
+				q.push({ dist[ne.first][ne.second], ne});
+			}
+		}
+	}
+	return dist;
+}
+
+int main() {
+	ios::sync_with_stdio(false);
+	cin.tie(NULL);
+	cout.tie(NULL);
+
+	cin >> N >> M >> K;
+	string s;
+	vector<string> matrix;
+	for (long long i = 0; i < N; i++) {
+		cin >> s;
+		matrix.push_back(s);
+	}
+	vector<pair<long, long>> food;
+	for (long long i = 0; i < K; i++) {
+		long long ri, ci;
+		cin >> ri >> ci;
+		food.push_back({ri-1, ci-1});
+	}
+
+	long long sum = 0;
+	for (long long i = 0; i < N; i++) {
+		for (long long j = 0; j < M; j++) {
+			if (matrix[i][j] == '#') continue;
+
+			vector<vector<long long>> dist = djikstra({i,j}, matrix);
+			// cout << endl << i << " " << j << " is at" << endl;
+			// for (long long i = 0; i < N; i++) {
+			//	 for (long long j = 0; j < M; j++) {
+			//		 cout << i << " " << j << " dist " << dist[i][j] << endl;
+			//	 }
+			// }
+			long long mind = -1;
+			for (auto f : food) {
+				if (matrix[f.first][f.second] == '#') continue;
+				if (mind == -1) {
+					mind = dist[f.first][f.second];
+					continue;
+				}
+				mind = min(mind, dist[f.first][f.second]);
+			}
+			// cout << "mind " << mind << endl;
+			sum += mind;
+		}
+	}
+	cout << sum << endl;
+}
diff --git a/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-SecondTry.cpp b/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-SecondTry.cpp
new file mode 100644
index 0000000..cc9a73e
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Practicum/Exam2/1-Office-SecondTry.cpp
@@ -0,0 +1,115 @@
+#include <iostream>
+#include <string>
+#include <queue>
+#include <vector>
+#include <algorithm>
+#include <utility>
+using namespace std;
+
+/*
+ * .....# 6 + 7 + 8 + 9 + 10 = 21 + 19 = 40
+ * .###.# 5
+ * ...#.# 4 + 5 + 6 = 15
+ * .##### 3
+ * ..^..# 2 + 1 + 0 + 1 + 2 = 6
+ * ######
+ *
+ *
+3 3 1
+.##
+...
+##.
+1 1
+
+
+10 10 10
++.####...#
+####.#.##.
+...#....##
+.###......
+###.....#.
+..#.......
+##.......#
+..#.##.###
+...###.##.
+.#...#...#
+1 1
+1 7
+2 10
+3 1
+6 1
+8 1
+9 10
+10 8
+5 2
+1 3
+
+
+ */
+
+typedef pair<long long, long long> loc;
+loc operator+(const loc& l1, const loc& l2) {
+	return { l1.first + l2.first, l1.second + l2.second };
+}
+
+long long N, M, K;
+loc dir[] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}};
+
+
+int main() {
+	ios::sync_with_stdio(false);
+	cin.tie(NULL);
+	cout.tie(NULL);
+
+	cin >> N >> M >> K;
+	string s;
+	vector<string> matrix;
+	for (long long i = 0; i < N; i++) {
+		cin >> s;
+		matrix.push_back(s);
+	}
+	for (long long i = 0; i < K; i++) {
+		long long ri, ci;
+		cin >> ri >> ci;
+		ri--; ci--;
+		if (matrix[ri][ci] != '#') matrix[ri][ci] = '+';
+	}
+
+	long long sum = 0;
+	for (long long i = 0; i < N; i++) {
+		for (long long j = 0; j < M; j++) {
+			if (matrix[i][j] != '.') continue;
+
+			vector<vector<bool>> visited(N, vector<bool>(M, false));
+			queue<loc> bfs;
+			bfs.push({ i, j });
+			bfs.push({-1, -1});
+			long long level = 1;
+			bool stop = false;
+			while (!bfs.empty() && !stop) {
+				if (bfs.front() == loc({-1,-1})) {
+					level++;
+					bfs.pop();
+					continue;
+				}
+				loc c = bfs.front();
+				bfs.pop();
+				visited[c.first][c.second] = true;
+				bool added = false;
+				for (int i = 0; i < 4; i++) {
+					loc ne = c + dir[i];
+					if (0 > ne.first || ne.first >= N || 0 > ne.second || ne.second >= M || visited[ne.first][ne.second] || matrix[ne.first][ne.second] == '#') continue;
+					if (matrix[ne.first][ne.second] == '+') {
+						stop = true;
+						break;
+					}
+					bfs.push(ne);
+					added = true;
+				}
+				if (added) bfs.push({ -1, -1 });
+			}
+			sum += level;
+		}
+	}
+	cout << sum << endl;
+}
diff --git a/Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp b/Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp
new file mode 100644
index 0000000..4ea0d35
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Practicum/Exam2/2-Interstellar.cpp
@@ -0,0 +1,60 @@
+#include <iostream>
+#include <string>
+#include <queue>
+#include <vector>
+#include <algorithm>
+#include <utility>
+using namespace std;
+
+/*
+ * 6 <-- 11 -- 7
+ * 7 <-- 19 -- 6
+ *   -- -19 -> 6
+ *
+ */
+
+bool topo(long long c, long long& temp, vector<vector<pair<long long, long long>>>& graph, vector<long long>& mark) {
+	if (mark[c] == 2) return true;
+	if (mark[c] == 1) return false;
+	mark[c] = 1;
+	for (pair<long long, long long>& p : graph[c]) {
+		if (p.second < 0) continue;
+		bool res = topo(p.first, temp, graph, mark);
+		if (!res && temp < p.second) {
+			mark[c] = 0;
+			p.second *= -1;
+			for (pair<long long, long long>& pa : graph[p.first]) {
+				if (pa.first == c) {
+					pa.second *= -1;
+					break;
+				}
+			}
+			res = topo(p.first, temp, graph, mark);
+			if (!res) return false;
+		}
+	}
+	mark[c] = 2;
+	return true;
+}
+
+int main() {
+	ios::sync_with_stdio(false);
+	cin.tie(NULL);
+	cout.tie(NULL);
+
+	long long N, M;
+	cin >> N >> M;
+	vector<vector<pair<long long, long long>>> graph(N+1, vector<pair<long long, long long>>());
+	for (long long i = 0; i < M; i++) {
+		long long ai, bi, ci;
+		cin >> ai >> bi >> ci;
+		graph[bi].push_back({ ai, ci });
+		graph[ai].push_back({ -bi, ci });
+	}
+	for (long long t = 0; t < 20; t++) {
+		vector<long long> mark(N+1);
+		if (topo(1, t, graph, mark)) {
+			cout << t << endl;
+		}
+	}
+}
diff --git a/Year 2/Design and analysis of algorithms/Practicum/Exam2/3-Game.cpp b/Year 2/Design and analysis of algorithms/Practicum/Exam2/3-Game.cpp
new file mode 100644
index 0000000..ea29789
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Practicum/Exam2/3-Game.cpp
@@ -0,0 +1,55 @@
+#include <iostream>
+#include <string>
+#include <queue>
+#include <vector>
+#include <algorithm>
+#include <utility>
+using namespace std;
+
+struct Edge {
+	long long end;
+	long long cmp;
+	long long points;
+};
+
+long long N, M, K;
+
+long long djikstra(long long s, vector<vector<Edge>>& graph) {
+	priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, less<pair<long long, long long>>> q;
+	vector<bool> visited(N);
+	vector<long long> dist(N);
+	dist[s] = 0;
+	q.push({ 0, s });
+	while (!q.empty()) {
+		auto c = q.top();
+		q.pop();
+
+		visited[c.second] = true;
+		for (Edge& e : graph[c.second]) {
+			if (visited[e.end]) continue;
+			long long nd = dist[c.second] + e.cmp;
+			if (dist[e.end] == 0 || nd > dist[e.end]) {
+				dist[e.end] = nd;
+				q.push({ nd, e.end });
+			}
+		}
+	}
+	return dist[N-1];
+}
+
+int main() {
+	ios::sync_with_stdio(false);
+	cin.tie(NULL);
+	cout.tie(NULL);
+
+	cin >> N >> M >> K;
+	vector<vector<Edge>> graph(N, vector<Edge>());
+	for (long long i = 0; i < M; i++) {
+		long long k1, k2, pi, ti;
+		cin >> k1 >> k2 >> pi >> ti;
+		k1--; k2--;
+		graph[k1].push_back({ k2, pi - ti, pi });
+		graph[k2].push_back({ k1, pi - ti, pi });
+	}
+	cout << K + djikstra(0, graph);
+}
diff --git a/Year 2/Design and analysis of algorithms/Practicum/Exam2/README.md b/Year 2/Design and analysis of algorithms/Practicum/Exam2/README.md
new file mode 100644
index 0000000..dff821d
--- /dev/null
+++ b/Year 2/Design and analysis of algorithms/Practicum/Exam2/README.md
@@ -0,0 +1,8 @@
+# [Exam 2](https://www.hackerrank.com/2-16)
+
+|#|Exercise|Difficulty|Score|
+|-|--------|----------|-----|
+|1|[Office](https://www.hackerrank.com/contests/2-16/challenges/1-6-5)|Medium|0|
+|2|[Interstelar](https://www.hackerrank.com/contests/2-16/challenges/2-1-32)|Medium|0|
+|3|[Game](https://www.hackerrank.com/contests/2-16/challenges/3-1-16)|Medium|100|
+|4|[Repair](https://www.hackerrank.com/contests/2-16/challenges/4-1-13)|Medium|0|