commit 0f2cc3f9f728a5d2bc1aa3d3046f265b01bcb9d3
parent 81840729c1df7021c2e7018a5817f6f93a64fcac
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date: Sat, 16 Sep 2023 12:41:40 +0000
Daily Problem and 5 Random Problems
Diffstat:
7 files changed, 152 insertions(+), 0 deletions(-)
diff --git a/Problems/0562.cpp b/Problems/0562.cpp
@@ -0,0 +1,33 @@
+class Solution {
+ typedef array<array<int, 16>, 16> cache_t;
+ static inline constexpr const cache_t cache = []() constexpr -> cache_t {
+ cache_t cache = {{0}};
+ for (int i = 1; i <= 15; i++) {
+ cache[i].fill(INT_MAX);
+ int count = 0;
+ for (int j = 1; j <= 15; j++) {
+ if (i % j == 0 || j % i == 0) cache[i][count++] = j;
+ }
+ }
+ return cache;
+ }();
+
+ int dp[16][65536];
+
+ public:
+ Solution() { memset(dp, 0xFF, sizeof(dp)); }
+
+ int countArrangement(int n, int crnt = 1, uint16_t mask = 0) {
+ if (crnt > n) return 1;
+ if (dp[crnt][mask] != -1) return dp[crnt][mask];
+
+ int res = 0;
+ for (int num : cache[crnt]) {
+ if (num > n) break;
+ if (mask & (1 << num)) continue;
+ res += countArrangement(n, crnt + 1, mask | (1 << num));
+ }
+
+ return dp[crnt][mask] = res;
+ }
+};
diff --git a/Problems/1247.cpp b/Problems/1247.cpp
@@ -0,0 +1,11 @@
+class Solution {
+ public:
+ int minimumSwap(const string &s1, const string &s2) {
+ int count[2] = {0};
+ for (int i = 0; i < s1.size(); i++)
+ if (s1[i] != s2[i]) count[s1[i] & 1]++;
+
+ if ((count[0] + count[1]) % 2) return -1;
+ return (count[0] + 1) / 2 + (count[1] + 1) / 2;
+ }
+};
diff --git a/Problems/1306.cpp b/Problems/1306.cpp
@@ -0,0 +1,26 @@
+class Solution {
+ public:
+ bool canReach(const vector<int> &arr, int start) {
+ bitset<50001> bs;
+ queue<int> q({start});
+ while (!q.empty()) {
+ const int idx = q.front();
+ q.pop();
+ const int left = idx - arr[idx], right = idx + arr[idx];
+
+ if (right < arr.size() && !bs[right]) {
+ if (!arr[right]) return true;
+ bs.set(right);
+ q.push(right);
+ }
+
+ if (left >= 0 && !bs[left]) {
+ if (!arr[left]) return true;
+ bs.set(left);
+ q.push(left);
+ }
+ }
+
+ return false;
+ }
+};
diff --git a/Problems/1600.cpp b/Problems/1600.cpp
@@ -0,0 +1,25 @@
+class ThroneInheritance {
+ unordered_map<string, vector<string>> children;
+ unordered_set<string> dead;
+
+ const string king;
+
+ public:
+ ThroneInheritance(const string &king) : king(king) {}
+ void birth(const string &parent, const string &child) { children[parent].push_back(child); }
+ void death(const string &name) { dead.insert(name); }
+
+ vector<string> getInheritanceOrder() {
+ order.clear();
+ rec(king);
+ return order;
+ }
+
+ private:
+ vector<string> order;
+ void rec(const string &name) {
+ if (!dead.count(name)) order.push_back(name);
+ for (const string &s : children[name])
+ rec(s);
+ }
+};
diff --git a/Problems/1631.cpp b/Problems/1631.cpp
@@ -0,0 +1,33 @@
+class Solution {
+ typedef tuple<unsigned, uint8_t, uint8_t> tile;
+
+ public:
+ int minimumEffortPath(const vector<vector<int>> &heights) {
+ static unsigned efforts[101][101];
+ const int n = heights.size(), m = heights[0].size();
+ static const int dirs[5] = {-1, 0, 1, 0, -1};
+
+ memset(efforts, 0xFF, sizeof(efforts));
+ priority_queue<tile, vector<tile>, greater<tile>> pq;
+
+ pq.push({0, 0, 0});
+ while (!pq.empty()) {
+ const auto [effort, x, y] = pq.top();
+ pq.pop();
+
+ if (x == n - 1 && y == m - 1) return effort;
+
+ for (int k = 0; k < 4; k++) {
+ const int i = x + dirs[k], j = y + dirs[k + 1];
+ if (i < 0 || i >= n || j < 0 || j >= m) continue;
+ const unsigned crnt = max(effort, (unsigned)abs(heights[x][y] - heights[i][j]));
+ if (crnt < efforts[i][j]) {
+ efforts[i][j] = crnt;
+ pq.push({crnt, i, j});
+ }
+ }
+ }
+
+ return -1;
+ }
+};
diff --git a/Problems/2517.cpp b/Problems/2517.cpp
@@ -0,0 +1,18 @@
+class Solution {
+ public:
+ int maximumTastiness(vector<int> &price, int k) {
+ sort(begin(price), end(price));
+ int low = 0, high = price.back() - price.front();
+ while (low <= high) {
+ int mid = low + (high - low) / 2, cnt = 1;
+ for (int i = 1, j = 0; i < price.size(); i++) {
+ if (price[i] - price[j] >= mid) cnt++, j = i;
+ }
+ if (cnt >= k)
+ low = mid + 1;
+ else
+ high = mid - 1;
+ }
+ return high;
+ }
+};
diff --git a/README.md b/README.md
@@ -314,6 +314,7 @@ for solving problems.
| 0516 | Medium | [Longest Palindromic Subsequence](Problems/0516.cpp) |
| 0518 | Medium | [Coin Change II](Problems/0518.cpp) |
| 0520 | Easy | [Detect Capital](Problems/0520.cpp) |
+| 0526 | Medium | [Beautiful Arrangement](Problems/0526.cpp) |
| 0529 | Medium | [Minesweeper](Problems/0529.cpp) |
| 0530 | Easy | [Minimum Absolute Difference in BST](Problems/0530.cpp) |
| 0535 | Medium | [Encode and Decode TinyURL](Problems/0532.cpp) |
@@ -510,6 +511,7 @@ for solving problems.
| 1232 | Easy | [Check If It Is a Straight Line](Problems/1232.cpp) |
| 1233 | Medium | [Remove Sub-Folders from the Filesystem](Problems/1233.cpp) |
| 1237 | Medium | [Find Positive Integer Solution for a Given Equation](Problems/1237.cpp) |
+| 1247 | Medium | [Minimum Swaps to Make Strings Equal](Problems/1247.cpp) |
| 1249 | Medium | [Minimum Remove to Make Valid Parentheses](Problems/1249.cpp) |
| 1254 | Medium | [Number of Closed Islands](Problems/1254.cpp) |
| 1261 | Medium | [Find Elements in a Contaminated Binary Tree](Problems/1261.cpp) |
@@ -520,6 +522,7 @@ for solving problems.
| 1290 | Easy | [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp) |
| 1302 | Medium | [Deepest Leaves Sum](Problems/1302.cpp) |
| 1305 | Medium | [All Elements in Two Binary Search Trees](Problems/1305.cpp) |
+| 1306 | Medium | [Jump Game III](Problems/1306.cpp) |
| 1310 | Medium | [XOR Queries of a Subarray](Problems/1310.cpp) |
| 1311 | Medium | [Get Watched Videos by Your Friends](Problems/1311.cpp) |
| 1312 | Hard | [Minimum Insertion Steps to Make a String Palindrome](Problems/1312.cpp) |
@@ -605,6 +608,7 @@ for solving problems.
| 1575 | Medium | [Count All Possible Routes](Problems/1575.cpp) |
| 1579 | Hard | [Remove Max Number of Edges to Keep Graph Fully Traversable](Problems/1579.cpp) |
| 1584 | Medium | [Min Cost to Connect All Points](Problems/1584.cpp) |
+| 1600 | Medium | [Throne Inheritance](Problems/1600.cpp) |
| 1601 | Hard | [Maximum Number of Achievable Transfer Requests](Problems/1601.cpp) |
| 1603 | Easy | [Design Parking System](Problems/1603.cpp) |
| 1605 | Medium | [Find Valid Matrix Given Row and Column Sums](Problems/1605.cpp) |
@@ -613,6 +617,7 @@ for solving problems.
| 1625 | Medium | [Lexicographically Smallest String After Applying Operations](Problems/1625.cpp) |
| 1626 | Medium | [Best Team With No Conflicts](Problems/1626.cpp) |
| 1630 | Medium | [Arithmetic Subarrays](Problems/1630.cpp) |
+| 1631 | Medium | [Path With Minimum Effort](Problems/1631.cpp) |
| 1637 | Medium | [Widest Vertical Area Between Two Points Containing No Points](Problems/1637.cpp) |
| 1638 | Medium | [Count Substrings That Differ by One Character](Problems/1638.cpp) |
| 1639 | Hard | [Number of Ways to Form a Target String Given a Dictionary](Problems/1639.cpp) |
@@ -759,6 +764,7 @@ for solving problems.
| 2487 | Medium | [Remove Nodes From Linked List](Problems/2487.cpp) |
| 2492 | Medium | [Minimum Score of a Path Between Two Cities](Problems/2492.cpp) |
| 2497 | Medium | [Maximum Star Sum of a Graph](Problems/2497.cpp) |
+| 2517 | Medium | [Maximum Tastiness of Candy Basket](Problems/2517.cpp) |
| 2527 | Medium | [Find Xor-Beauty of Array](Problems/2527.cpp) |
| 2542 | Medium | [Maximum Subsequence Score](Problems/2542.cpp) |
| 2545 | Medium | [Sort the Students by Their Kth Score](Problems/2545.cpp) |
