2018 S5 + 2019 S5

kingMonkeh · Apr 3, 2023 · a2830e3 · a2830e3
1 parent 654969a
commit a2830e3
Show file tree

Hide file tree

Showing 2 changed files with 244 additions and 0 deletions.
diff --git a/2018 S5 - Maximum Strategic Savings.cpp b/2018 S5 - Maximum Strategic Savings.cpp
@@ -0,0 +1,147 @@
+/*
+
+2018 S5 - Maximum Strategic Savings
+
+Difficulty: Hard
+
+I highly recommend that you read the editorial posted on dmoj for this problem
+Still, it's a bit confusing and so I'll try my best to explain it in further detail
+
+Basically we could try performining kruskals on every single individual edge
+But the graph gets too big, so instead we think about it this way:
+
+Take a single inputted edge, this edge is either repeated across every row, or every column
+So instead of iterating over each duplicate of this edge, we can instead do them all at once.
+
+To calculate the minimum number of edges we would need to use out of all the duplicates,
+We keep track of how many rows or columns need to be merged, and this is exactly how many edges we need to connect the two rows or edges,
+Therefore we multiply the weight w, by this amount, since all edges in the batch have weight w
+
+To determine cycles in our Kruskals, we will have two union find sets
+One representing the rows, named vertical, vertical[0] is the top row or row 0 and vertical[N] representing the last row/planet
+The other union find set is called horizontal, it represents the cities from left to right
+
+One may wonder how 2 1-D structures could possibly represent the large 2-D structure that the problem presents
+But, recall that each edge we observe in Kruskals, takes into consideration all of its duplicates as well to ensure that either 2 rows are completely connected
+or 2 columns are completely connected
+
+This means, we only need to keep track of whether an entire row or column is merged
+
+*/
+
+#include <iostream>
+#include <vector>
+#include <algorithm>
+#include <numeric>
+
+//Kruskal's comparison operator
+struct compare{
+    bool operator() (std::vector<int> a, std::vector<int> b){
+        return a[0] < b[0];
+    }
+} cmp;
+
+//Cycle finding and Union Find
+struct unionFind{
+
+    std::vector<int> parent = std::vector<int> (100001);
+    std::vector<int> size = std::vector<int> (100001, 1);
+
+    //Root function
+    int find(int x){
+        if (parent[x] == x){
+            return x;
+        }
+        else{
+            return find(parent[x]);
+        }
+    }
+
+    //Union
+    void Union(int a, int b){
+        int roota = find(a);
+        int rootb = find(b);
+
+        if (size[roota] > size[rootb]){
+            parent[rootb] = roota;
+            size[roota] += size[rootb];
+        }
+
+        else{
+            parent[roota] = rootb;
+            size[rootb] += size[roota];
+        }
+
+    }
+
+} horizontal, vertical;
+
+int main(){
+
+    int N, M, P, Q;
+    scanf("%d%d%d%d", &N, &M, &P, &Q);
+
+    //Edge = {cost, a, b, type}
+    std::vector<std::vector<int>> edges (P + Q);
+
+    long long total = 0; //Total cost of all edges, including the ones we don't want
+
+    //Flights
+    for (int i = 0; i < P; i++){
+        int a, b, c;
+        scanf("%d%d%d", &a, &b, &c);
+        edges[i] = {c, a, b, 0};
+        total += 1LL * c * N; //Note that the numbers get quite big
+    }
+
+    //Portals
+    for (int i = 0; i < Q; i++){
+        int a, b, c;
+        scanf("%d%d%d", &a, &b, &c);
+        edges[P + i] = {c, a, b, 1};
+        total += 1LL * c * M;
+    }
+
+    //Initialize parent arrays of the union find structures
+    for (int i = 1; i <= N; i++){
+        vertical.parent[i] = i;
+    }
+
+    for (int i = 1; i <= M; i++){
+        horizontal.parent[i] = i;
+    }
+
+    //The following 2 lines can be ignored, they also initialize the parent arrays, just in a much cleaner method
+    //std::iota(vertical.parent.begin(), vertical.parent.begin() + 1 + N, 0);
+    //std::iota(horizontal.parent.begin(), horizontal.parent.begin() + 1 + M, 0);
+
+    std::sort(edges.begin(), edges.end(), cmp);
+
+    //rowsRemaining and colsRemaining, this will let us know how many of duplicate edges we need to fully connect two rows or columns
+    int rowsRemaining = N, colsRemaining = M;
+    long long optimalCost = 0; //Cost of the MST
+
+    for (auto& edge: edges){
+
+        //If a flight and no cycle created
+        if (edge[3] == 0 && horizontal.find(edge[1]) != horizontal.find(edge[2])){
+            horizontal.Union(edge[1], edge[2]);
+            optimalCost += 1LL * edge[0] * rowsRemaining;
+            colsRemaining--; //By connecting two cities in every planet, we can imagine it that these two columns in the 2-D array have been merged, meaning when we're adding a portal, it technically only needs to stem connect to one of these columns, since this city also connects to the other city and vice verca
+        }
+
+        //If a portal and no cycle created
+        else if (edge[3] == 1 && vertical.find(edge[1]) != vertical.find(edge[2])){
+            vertical.Union(edge[1], edge[2]);
+            optimalCost += 1LL * edge[0] * colsRemaining;
+            rowsRemaining--; //By connecting two planets, we only need flights connecting the cities on per groups of rows since from the cities in the planet with the flights, you can just take a portal to reach the same city on the other planet
+        }
+
+    }
+
+    //Output answer, the difference in cost, aka how much was saved
+    std::cout << total - optimalCost << '\n';
+
+    return 0;
+
+}
diff --git a/2019 S5 - Triangle Data Structure.cpp b/2019 S5 - Triangle Data Structure.cpp
@@ -0,0 +1,97 @@
+/*
+
+2019 S5 - Triangle Data Structure
+
+Difficulty: Hard
+
+This problem has a very interesting solution. 
+Essentially, we notice that if we brute force the problem by searching through each cell of each subtriangle
+There's a lot of unnecessary overlap.
+
+To avoid this, we will determine the max element in a sub triangle by dividing it into 3 smaller subtriangles and picking the max of the 3
+This reduces our overlap and allows us to build upon our solved triangles to reach the desired subtriangle size
+
+Notice that to split a triangle into 3 smaller subtriangles, each subtriangle must have a minimum height of atleast ceil(triangle size * (2 / 3))
+Sub triangles any larger, create too much overlap and are inefficient
+
+With this knowledge, we will write a recursive function called solve() which takes a triangle size as a parameter
+This function will determine the max value for each triangle of the given size using 3 smaller subtriangles
+
+Note that if we're attempting to calculate triangle size 2, the minimum size of each subtriangle is 1, not ceil(size * 2 / 3)
+This is the only edge case, if we're passed triangle size 1, we do nothing since thats the base
+
+IMPORTANT NOTE:
+INPUT SIZE IS VERY LARGE, USE SCANF AS IT'S MUCH FASTER THAN CIN, (ABOUT 3x FASTER ON MY SUBMISSION)
+
+*/
+
+#include <iostream>
+#include <vector>
+#include <math.h>
+
+std::vector<std::vector<int>> triangle; //Our original triangle, note that as we run solve(), it will overwrite the actual values of this triangle
+
+//subtriangle_size is the size of the current triangle we're trying to solve for
+void solve(int subtriangle_size){
+
+    //If subtriangles of size 1, just do nothing
+    if (subtriangle_size == 1){
+        return;
+    }
+
+    //Otherwise, we calculate the size of the 3 sub triangles of this sub triangle
+    int subsize = ceil(subtriangle_size * 2.0 / 3.0);
+
+    //Edge case, if subtriangle_size = 2, we actually only need subsize 1
+    if (subtriangle_size == 2){
+        subsize = 1;
+    }
+
+    solve(subsize); //Solve for all the smaller subtriangles that will make up the triangles of our current size
+    //Note that for every triangle we solve, we put the max value of a triangle at its head node, (the top corner)
+
+    //Update the triangles using triplets of smaller subtriangles
+    for (int i = 0; i <= triangle.size() - subtriangle_size; i++){
+        for (int j = 0; j <= i; j++){
+            //The first top subtriangle has the same head as the current triangle, the bottom left subtriangle has its head at i + subtriangle_size - subsize
+            //Lastly, the bottom right subtriangle is located at [i + subtriangle_size - subsize][j + subtriangle_size - subsize]
+            //If you don't believe me, try this on paper
+            triangle[i][j] = std::max(triangle[i][j], std::max(triangle[i + subtriangle_size - subsize][j], triangle[i + subtriangle_size - subsize][j + subtriangle_size - subsize]));
+        }   
+    }
+
+}
+
+int main(){
+
+    int N, K;
+    scanf("%d%d", &N, &K);
+
+     triangle.resize(N);
+
+    //Get triangle
+    for (int i = 0; i < N; i++){
+        for (int j = 0; j <= i; j++){
+            int value;
+            scanf("%d", &value); //USE SCANF, DO NOT USE CIN
+            triangle[i].push_back(value);
+        }
+    }
+
+    //Solve
+    solve(K);
+    long long sum = 0; //Use long long, number gets very big
+
+    //For each subtriangle of size K
+    for (int i = 0; i <= N - K; i++){
+        for (int j = 0; j <= i; j++){
+            //Add max value for this sub triangle size generated from solve() function call
+            sum += triangle[i][j]; 
+        }
+    }
+
+    std::cout << sum << '\n';
+
+    return 0;
+
+}