kick start 2022 Coding Practice solutions

jefersonf · Feb 17, 2022 · ba690b5 · ba690b5
1 parent 45a50cd
commit ba690b5
Show file tree

Hide file tree

Showing 15 changed files with 348 additions and 0 deletions.
diff --git a/Kick Start/2022/A/sample.in b/Kick Start/2022/A/sample.in
@@ -0,0 +1,5 @@
+2
+7 3
+1 2 3 4 5 6 7
+5 10
+7 7 7 7 7
diff --git a/Kick Start/2022/A/sample.out b/Kick Start/2022/A/sample.out
@@ -0,0 +1,2 @@
+Case #1: 1
+Case #2: 5
diff --git a/Kick Start/2022/A/sol.cpp b/Kick Start/2022/A/sol.cpp
@@ -0,0 +1,20 @@
+//Sample Problem
+//Solution: Simple modular arithmetic application
+#include <iostream>
+using namespace std;
+
+int main() {
+    int t, i, j;
+    cin >> t;
+    for (i=1; i <= t; i++) {
+        int n, m, s = 0;
+        cin >> n >> m;
+        for (j=0; j<n; j++) {
+            int c;
+            cin >> c;
+            s += c;
+        } 
+        cout << "Case #" << i << ": " << (s % m) << endl;
+    }
+    return 0;
+}
diff --git a/Kick Start/2022/B/sample.in b/Kick Start/2022/B/sample.in
@@ -0,0 +1,4 @@
+3
+Mollaristan
+Auritania
+Zizily
diff --git a/Kick Start/2022/B/sample.out b/Kick Start/2022/B/sample.out
@@ -0,0 +1,3 @@
+Case #1: Mollaristan is ruled by Bob.
+Case #2: Auritania is ruled by Alice.
+Case #3: Zizily is ruled by nobody.
diff --git a/Kick Start/2022/B/sol.cpp b/Kick Start/2022/B/sol.cpp
@@ -0,0 +1,28 @@
+//Centauri Prime
+//Solution: Implementation
+#include <iostream>
+#include <map>
+using namespace std;
+int main() {
+
+    string vowels = "AEIOUaeiou";
+    map<char, bool> v;
+    for (int i=0; i<vowels.size(); i++) v[vowels[i]] = true;
+
+    int t; cin >> t;
+    cin.ignore();
+    for (int i=1; i<=t; i++) {
+        string s;
+        getline(cin, s);
+        cout << "Case #" << i << ": " << s;
+        int n = s.size();
+        if (s[n-1] == 'y' || s[n-1] == 'Y') {
+            cout << " is ruled by nobody.\n";
+        } else if (v.count(s[n-1])) {
+            cout << " is ruled by Alice.\n";
+        } else {
+            cout << " is ruled by Bob.\n";
+        }
+    }
+    return 0;
+}
diff --git a/Kick Start/2022/C/sample.in b/Kick Start/2022/C/sample.in
@@ -0,0 +1,5 @@
+2
+3
+5 1 2
+6
+1 3 3 2 2 15
diff --git a/Kick Start/2022/C/sample.out b/Kick Start/2022/C/sample.out
@@ -0,0 +1,2 @@
+Case #1: 1 1 2
+Case #2: 1 1 2 2 2 3
diff --git a/Kick Start/2022/C/sol.cpp b/Kick Start/2022/C/sol.cpp
@@ -0,0 +1,49 @@
+//H-Index
+//Solution: Fenwick Tree + Binary Search
+#include <iostream>
+#include <vector>
+#include <map>
+#define br(n) " \n"[n]
+using namespace std;
+const int N = 100100;
+int tree[N];
+
+void add(int i) {
+    while (i < N) tree[i] += 1, i += i&(-i);
+}
+
+int query(int i) {
+    int c = 0;
+    while (i > 0) c += tree[i], i -= i&(-i);
+    return c;
+}
+
+int main() {
+    int t; cin >> t;
+    for (int i=1; i<=t; i++) {
+        int n; cin >> n;
+        for (int k=0; k<N; k++) tree[k]=0;
+        cout << "Case #" << i << ": ";
+        int h = 1, m = 0;
+        for (int j=0; j<n; j++) {
+            int a;
+            cin >> a;
+            add(a);
+            m = max(m, a);
+            if (j > 0) {
+                int count = query(m + 1);
+                int lo = 1, hi = j + 1;
+                while (lo <= hi) {
+                    int k = (lo + hi) / 2;
+                    int q = count - query(k-1);
+                    if (q >= k) {
+                        h = max(h, k);
+                        lo = k + 1;
+                    } else hi = k - 1;
+                }
+            }
+            cout << h << br(j==n-1);
+        }
+    }
+    return 0;
+}
diff --git a/Kick Start/2022/D/sample.in b/Kick Start/2022/D/sample.in
@@ -0,0 +1,27 @@
+7
+1
+.
+1
+B
+1
+R
+2
+BR
+BB
+4
+BBBB
+BBB.
+RRR.
+RRRR
+4
+BBBB
+BBBB
+RRR.
+RRRR
+6
+......
+..R...
+BBBBBB
+..R.R.
+..RR..
+......
diff --git a/Kick Start/2022/D/sample.out b/Kick Start/2022/D/sample.out
@@ -0,0 +1,7 @@
+Case #1: Nobody wins
+Case #2: Blue wins
+Case #3: Red wins
+Case #4: Impossible
+Case #5: Blue wins
+Case #6: Impossible
+Case #7: Blue wins
diff --git a/Kick Start/2022/D/sol.cpp b/Kick Start/2022/D/sol.cpp
@@ -0,0 +1,106 @@
+//Hex
+//Solution: Implementation + Vertex Cutting
+#include <bits/stdc++.h>
+using namespace std;
+
+const int M = 6;
+const char BLUE  = 'B';
+const char RED   = 'R';
+
+int dx[M] = {1,-1, 0, 0,  1, -1};
+int dy[M] = {0, 0, 1,-1, -1,  1};
+
+bool hasWinningPath(vector<string>& board, char color) {
+    int size = board.size();
+    vector<vector<bool>> seen(size, vector<bool>(size, false));
+    queue<pair<int, int>> q;
+    int i, j;
+    for (i=0; i<size; i++) {
+        if (color == BLUE) {
+            if (board[i][0] == BLUE)
+                q.push({i, 0}), seen[i][0] = true;
+        } else if (color == RED) {
+            if (board[0][i] == RED)
+                q.push({0, i}), seen[0][i] = true;
+        }
+    }
+
+    while (!q.empty()) {
+        auto t = q.front();
+        q.pop();
+        for (j=0; j<M; j++) {
+            int row = t.first + dy[j];
+            int col = t.second + dx[j];
+            if (row<0 || row>=size|| col<0 || col>=size) continue;
+            if (seen[row][col] || board[row][col] != color) continue;
+            seen[row][col] = true;
+            q.push({row, col});
+        }
+    }
+
+    for (i=0; i<size; i++) {
+        if (seen[i][size-1] && color == BLUE) return true;
+        if (seen[size-1][i] && color == RED) return true;
+    }
+    return false;
+}
+
+bool hasCuttingStone(vector<string>& board, char color) {
+    int size = board.size();
+    int i, j;
+    for (i=0; i<size; i++) {
+        for (j=0; j<size; j++) {
+            if (board[i][j] == color) {
+                board[i][j] = '.';
+                bool stillHaveWinningPath = hasWinningPath(board, color);
+                board[i][j] = color;
+
+                if (!stillHaveWinningPath) {
+                    return true;
+                }
+            }
+        }
+    }
+    return false;
+}
+
+string FindBoardStatus(int size) {
+    vector<string> board(size);
+    int i, j, n = size;
+    int bStones = 0, rStones = 0;
+    for (i=0; i<n; i++) {
+        cin >> board[i];
+        for (j=0; j<n; j++) {
+            if (board[i][j] == BLUE)
+                bStones += 1;
+            else if (board[i][j] == RED)
+                rStones += 1;
+        }   
+    }
+
+    bool hasBlueWinningPath = hasWinningPath(board, BLUE);
+    bool hasBlueCuttingStone = hasCuttingStone(board, BLUE);
+    bool hasRedWinningPath = hasWinningPath(board, RED);
+    bool hasRedCuttingStone = hasCuttingStone(board, RED);
+
+    if (abs(bStones - rStones) > 1 
+        || (hasBlueWinningPath && (!hasBlueCuttingStone || rStones > bStones))
+        || (hasRedWinningPath && (!hasRedCuttingStone || bStones > rStones))) {
+        return "Impossible";
+    } else if (hasBlueWinningPath) {
+        return "Blue wins";
+    } else if (hasRedWinningPath) {
+        return "Red wins";
+    }
+    return "Nobody wins";
+}
+
+int main() {
+    int T, tc; cin >> T;
+    for (tc=1; tc<=T; tc++) {
+        int n;
+        cin >> n;
+        cout << "Case #" << tc << ": " << FindBoardStatus(n) << endl;
+    }
+    return 0;
+}
diff --git a/Kick Start/2022/E/sample.in b/Kick Start/2022/E/sample.in
@@ -0,0 +1,13 @@
+2
+3 1 4
+1100
+1010
+0000
+1000
+2 4 4
+1111
+1111
+1111
+0111
+1011
+1101
diff --git a/Kick Start/2022/E/sample.out b/Kick Start/2022/E/sample.out
@@ -0,0 +1,2 @@
+Case #1: 4
+Case #2: 2
diff --git a/Kick Start/2022/E/sol.cpp b/Kick Start/2022/E/sol.cpp
@@ -0,0 +1,75 @@
+// Milk Tea
+// Solution: Hash table + MinHeap over possible complaints
+#include <bits/stdc++.h>
+using namespace std;
+int main() {
+    int T, tc; cin >> T;
+    for (tc=1; tc<=T; tc++) {
+        int n, m, p;
+        cin >> n >> m >> p;
+        vector<int> u(p, 0), z(p, 0);
+        int i, j;
+        for (i=0; i<n; i++) {
+            string s;
+            cin >> s;
+            for (j=0; j<p; j++) {
+                if (s[j]=='1') u[j]++;
+                else z[j]++;
+            }
+        }
+        set<__int128_t> fo;
+        for (i=0; i<m; i++) {
+            string s;
+            cin >> s;
+            __int128_t w = (__int128_t)0;
+            for (j=0; j<p; j++) {
+                if (s[p-j-1]=='1') w |= ((__int128_t)1 << (__int128_t)j);
+            }
+            fo.insert(w);
+        }
+
+        int c = 0;
+        __int128_t st = (__int128_t)0;
+        for (i=0; i<p; i++) {
+            if (z[i] > u[i]) {
+                c += u[i];
+            } else {
+                st |= ((__int128_t)1 << (__int128_t)(p-i-1)); 
+                c += z[i];
+            }
+        }
+
+        set<__int128_t> seen;
+        priority_queue<pair<int, __int128_t>> pq;
+        seen.insert(st);
+        pq.push({-c, st});
+        while (!pq.empty()) {
+            auto t = pq.top();
+            pq.pop();
+            __int128_t opt = t.second;
+            int complaints = -t.first;
+            if (fo.find(opt) == fo.end()) {
+                cout << "Case #" << tc << ": " << complaints << endl;
+                break;
+            }
+            for (i=0; i<p; i++) {
+                __int128_t cpy = opt;
+                int comp = complaints;
+                __int128_t pos = (__int128_t)1 << (__int128_t)(p-i-1);
+                if (opt & pos) {
+                    comp += u[i];
+                    comp -= z[i];
+                } else {
+                    comp += z[i];
+                    comp -= u[i];
+                }
+                cpy ^= pos;
+                if (seen.find(cpy) == seen.end()) {
+                    seen.insert(cpy);
+                    pq.push({-comp, cpy});
+                }
+            }
+        }
+    }
+    return 0;
+}
-Original file line number
+Diff line change
@@ -0,0 +1,27 @@
+    .
+    B
+    R
+    BR
+    BB
+    BBBB
+    BBB.
+    RRR.
+    RRRR
+    BBBB
+    BBBB
+    RRR.
+    RRRR
+    ......
+    ..R...
+    BBBBBB
+    ..R.R.
+    ..RR..
+    ......
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,13 @@
		2
		3 1 4
		1100
		1010
		0000
		1000
		2 4 4
		1111
		1111
		1111
		0111
		1011
		1101