If we try to use brute-force algorithm to solve this problem, we will find O(2^n) in complexity. But, since max of n is 40, it’s too long to pass. Namely, $2^{40}\sim 10^{12}$. Also, although it looks like a dynamic programming problem, it’s not working either.
Surprisingly, it’s easier than I thought. All we have to do is divide it into half. That way, the complexity will became $2^{n/2}+2^{n/2}$, which has a maximum of $2^{20}+2^{20}=2^{21}\sim 2*10^{6}$.
But, that only include time of 2 brute-force divide. We have to also conquer it. There’s the procedure,
for each map1 value, find a value in map2 that satisfy val1 + val2 = target.
combinations
how many combinations in nums1 can construct that sum
Therefore, we get the total complexity is $Time=2*2^{n}*lg(2^n)+2^{n}*lg(2^n)={3}*2^{n}*n$ , where n has a maximum of 20. Namely, we obtain the worse case run time is $$O_w({3}*2^{n}*n)={3}*2^{20}*20\sim {6}*10^7$$
Since the total informant can only be up to 20, we can use an integer to represent if it’s reliable by :
1 2 3 4 5
reliable table 00001 : A is reliable 00010 : B is reliable 00110 : B and C is reliable ...etc.
So as the unreliables.
Brute force : pull out every possibilities
Since we discover that n informant has to represent with n bits, the full range of the possibles is $0$ ~ $2^n-1$ with it represented in int.
And per possibilities, we have to verify it with every informant that is reliable to tell if it’s a valid possible reliable informants allocation.
Therefore, we can calculate a time complexity of: $$O(2^N*N)$$ Where $N$ is the number of informants. Since $N$ has maximum value of 20, it cost at most $2^{20}*20 \sim {2}*10^7$, which will not TLE at most judge.
intmain() { int nums[21], fnums[21]; int n, m; while (cin >> n >> m && n) { // reset memset(nums, 0, sizeof(nums)); memset(fnums, 0, sizeof(fnums)); // handle input int x, y; for (int i = 0; i < m; i++) { cin >> x >> y; if (y > 0) nums[x - 1] |= 1 << y - 1; else fnums[x - 1] |= 1 << -y - 1; } // solve int hightest = (1 << n), res = 0; for (int i = 0; i < hightest; i++) { int now = __builtin_popcount(i), ni = (~i); if (res >= now) continue; bool flag = true; for (int j = 0; j < n; j++) if ((i & (1 << j)) && ((fnums[j] & ni) != fnums[j] || (nums[j] & i) != nums[j])) { flag = false; break; } if (flag) res = now; } cout << res << endl; } }
This problem gives us two numbers, num1, num2. Suppose num1 < num2, although might be arbitrary. Therefore, it’s actually calculate 0 ~ num2 - 0 ~ num1 in every number.
The Problem : Calculate 1 ~ num
To calculate various numbers in 1 ~ num, I use 3 steps. Let b be the maximum that satisfy num / pow(10,b) > 0.
calculate 1 ~ pow(10,b)-1, or 1 ~ 999...99, we can recursively solve this by use count_numbers(pow(10,b)-1).
calculate the midst of the number, or 10...00 ~ X0...00 - 1, where X is the leading number of num.
From row8 to row1, We can find an interesting fact : if we assign id 1 ~ 8 to row 8 ~ row 1, respectfully. Let’s say the red balloon in id i is bal[i]. We can get a interesting formula bal[i] = bal[i/2]*2.
Also, $\sum^{2^n}bal[i]$ can be respresent as $3^{n-1}$.
Intuition
We can also see $\sum^{M}bal[i]$ in a very different way that can provide time complexity to O(log(n)): Use $\sum^{2^n}bal[i] = 3^{n-1}$
That is, compute $\sum^{M}bal[i] = \sum^{2^{x_1}}bal[i] + \sum^{2^{x_2}}bal[i] + … + \sum^{2^{x_k}}bal[i]$, where $M=2^{x_1}+2^{x_2}+…+2^{x_k}$.
Contruct a tower of Babylon use Blocks. Since Blocks can be flip, we got 6 different cases with one type of block. Put them into a vector, sort them, and it’s a simple LIS problem.
p.s. One difference from typical LIS problem is that it’s wants maximum height.
#include<bits/stdc++.h> usingnamespace std; #define ll long long
intmain() { ll x; while (cin >> x && x) { ll res = 0; cout << "The parity of "; bool y = false; for (int i = 32; i >= 0; i--) if ((x >> i) & 1) { res++; cout << 1; y = true; } elseif (y) cout << 0; cout << " is " << res << " (mod 2).\n"; } }
UVA-10789 Prime Frequency
Since every case can only put 2001 size of string, I just pre-calculate every case.(from exist 1 ~ 2001 times). Then, use map to calculate individual alphabat exist n times, and it will auto sort too.
intmain() { bool nums[2002]; nums[0] = nums[1] = false; for (int i = 2; i < 2002; i++) { nums[i] = true; for (int j = sqrt(i); j > 1; j--) if (i % j == 0) nums[i] = false; } int t, n; cin >> t; for (int i = 0; i < t; i++) { cout << "Case " << i + 1 << ": "; string s; cin >> s; map<char, int> mp; for (char c : s) mp[c]++; bool isEmpty = true; for (auto it : mp) if (nums[it.second]) { isEmpty = false; if (it.first < 10) cout << int(it.first); else cout << it.first; } if (isEmpty) cout << "empty"; cout << "\n"; } }
UVA-10903 Rock-Paper-Scissors Tournament
Firstly, I define rock paper scissors to 0,1,2, respectfully. (call it t1, t2, for person 1, 2, respectfully.) We observed that this game has 3^2 = 9 ways to perform, to get result. To get result, I use a 3*3 matrix to store result, 1 for win, -1 for loss, 0 for even. result = pos[t1][t2], so to speak. Then, I put result into arrays ,and therefore get answers we wanted.
constint dir[5] = {0, -1, 0, 1, 0}; int m, n; vector<vector<char>> v;
voiddfs(int x, int y) { if (v[x][y] == 0) return; char val = v[x][y]; v[x][y] = 0; for (int i = 0; i < 4; i++) { int nx = x + dir[i]; int ny = y + dir[i + 1]; if (nx >= 0 && nx < m && ny >= 0 && ny < n && v[nx][ny] == val) dfs(nx, ny); } }
intmain() { int t; cin >> t; for (int cnt = 1; cnt <= t; cnt++) { cin >> m >> n; v.resize(m, vector<char>(n)); map<char, int> mp; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) cin >> v[i][j]; int res = 0; for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (v[i][j] != 0) mp[v[i][j]]++, dfs(i, j); cout << "World #" << cnt << "\n"; vector<pair<int, char>> ans; for (auto &it : mp) ans.push_back(make_pair(it.second, it.first)); sort( ans.begin(), ans.end(), [](const pair<int, char> &it1, const pair<int, char> &it2) -> bool { if(it1.first != it2.first) return it1.first > it2.first; return it1.second < it2.second; }); for (auto &it : ans) cout << it.second << ": " << it.first << "\n"; } }
We use Dynamic Programming to address this problem. That is, dp[i] means from s[0] to s[i-1], the minimum partition. Therefore, dp[s.size()] or dp.back() is the result.
intmain() { int t; cin >> t; while (t--) { string s; cin >> s; vector<int> dp(s.size() + 1); for (int i = 0; i <= s.size(); i++) dp[i] = i; // that is, dp 1 ~ s.size() is s: 0 ~ s.size()-1 for (int i = 1; i < s.size(); i++) { // even numbers of characters kind of palindrome int x = i - 1, y = i; while (x >= 0 && y < s.size() && s[x] == s[y]) { dp[y + 1] = min(dp[y + 1], dp[x] + 1); x--, y++; } // odd x = y = i; while (x >= 0 && y < s.size() && s[x] == s[y]) { dp[y + 1] = min(dp[y + 1], dp[x] + 1); x--, y++; } } cout << dp.back() << endl; } }
UVA-10635 Prince and Princess
A Longest Common Subsequence (LCS) Problem.
Fairly hard problem tho, mainly because it will TLE on the 2d DP solution.
Also, there’s a same problem on leetcode, up and running for those leetcode grinder. By the way, the 2d DP approach will pass on leetcode, and it’s fairly fast on those test case. No wonder it’s mark medium on leetcode. haha.
intdfs(vector<int> &t1, vector<int> &t2, int x, int y) { if (dp[x][y] != -1) return dp[x][y]; if (x >= t1.size() || y >= t2.size()) return0; int y1 = y, x1 = x; for (; y < t2.size(); y++) if (t1[x] == t2[y]) break; if (y >= t2.size()) return0; int res = 0; for (int i = x + 1; i < t1.size(); i++) res = max(res, dfs(t1, t2, i, y + 1) + 1); return dp[x1][y1] = res; }
// top down dp method // where dp[x][y] means for (int x = 0; x < t1.size(); x++) { for (int y = 0; y < t2.size(); y++) { dp[x][y] = 0; if (y - 1 >= 0 && x - 1 >= 0) dp[x][y] = dp[x - 1][y - 1]; if (t1[x] == t2[y]) dp[x][y]++; else dp[x][y] = max(x - 1 >= 0 ? dp[x - 1][y] : 0, y - 1 >= 0 ? dp[x][y - 1] : 0); } } return dp[t1.size() - 1][t2.size() - 1]; }
intmain() { int t; cin >> t; for (int tt = 1; tt <= t; tt++) { int n, p, q, temp; cin >> n >> p >> q; vector<int> t1, t2; for (int i = 0; i <= p; i++) { cin >> temp; t1.push_back(temp); } for (int i = 0; i <= q; i++) { cin >> temp; t2.push_back(temp); } dp.assign(t1.size(), vector<int>(t2.size(), -1)); cout << "Case " << tt << ": " << lcs(t1, t2) << endl; } }
Method 2 : LCS to LIS
Actually, if you really look into LCS, it can be devide into a LIS, which has a best practice of complexity O(nlgn).
Just like this, where * and x means t1[i] == t2[j]. ref: ntnu algo
But, it just not this case, right? Since elements in our list is unique, so our thing will not alike some normal LCS graph. Rather, it’s more easy.
According to this rule, we can confidently say that same row or column will have no more than 1 value. Therefore, it reduce the complexity that we don’t have to use pairs… sorting … stuff. All we have to do is:
map t1 value to t1 index.
through t2 iteration, add (if t1 get the same value) it’s t1 index to a vector.
Since vector is already in t2’s iteration, do LIS on vector’s value.
voiddijkstra(){ dis.assign(701, INF); dis[0] = 0; pq.emplace(mp(0, 0)); while (!pq.empty()) { int x = pq.top().second; int val = pq.top().first; pq.pop(); for (auto y : edges[x]) { //cout << y.first << " "; if (dis[y.first] > dis[x] + y.second) { dis[y.first] = dis[x] + y.second; pq.push(mp(dis[y.first], y.first)); } }//cout << endl; }
}
voidconnect(int x, int y, int cost){ edges[x].emplace_back(mp(y, cost)); edges[y].emplace_back(mp(x, cost)); }
voidprint(int x){ for (auto it : edges[x]) { cout << it.first << " " << it.second << endl; } }
intmain(){ int n, k; while (cin >> n >> k) { T.assign(n + 1, 0); edges.assign(701, vector<pair<int, int>>()); for (int i = 1; i <= n; i++) cin >> T[i]; cin.ignore(); // connect linearly for (int i = 1; i <= n; i++) { string s; getline(cin, s); stringstream ss(s); int x, y; ss >> x; if (x == 0) connect(0, 100 * i, 0); while (ss >> y) { connect(100 * i + x, 100 * i + y, (y - x) * T[i]); x = y; } } // connect different -elevator for (int i = 0; i < 100; i++) for (int x = 1; x <= n; x++) for (int y = x + 1; y <= n; y++) if (!edges[x * 100 + i].empty() && !edges[y * 100 + i].empty()) connect(x * 100 + i, y * 100 + i, 60); // connect endpoint for (int x = 1; x <= n; x++) if (!edges[x * 100 + k].empty()) connect(x * 100 + k, 700, 0); //print(230); dijkstra(); if (dis[700] == INF) cout << "IMPOSSIBLE\n"; else cout << dis[700] << endl; } }
#define ll long long #define mp make_pair #define ALL(x) x.begin(), x.end()
constint mod = 1e9 + 7;
vector<vector<int>> ver; vector<int> vis;
intdfs(int x, int start = 0) { if (vis[x]) return0; if (!start) vis[x] = 1; int res = 1; for (int i = 0; i < ver[x].size(); i++) res += dfs(ver[x][i]); return res; }
voidsolve(int v) { ver.clear(); ver.resize(v + 1); int temp, t1; while (cin >> temp && temp) { while (cin >> t1 && t1) ver[temp].emplace_back(t1); } int m; cin >> m; for (int i = 0; i < m; i++) { vis.clear(); vis.resize(v + 1, 0); cin >> temp; cout << v + 1 - dfs(temp, 1); for (int j = 1; j <= v; j++) { if (vis[j] == 0) cout << " " << j; } cout << "\n"; } }
intmain(int argc, constchar *argv[]) { int v; while (cin >> v && v) solve(v); return0; }
brute force = TLE Therefore, we think that if we had traveled the vertex before, we don’t have to travel it again, since if it has been traversed, the traveler is definitely possessed greater reachable person.
voidsolve() { int m; cin >> m; memset(v, 0, m + 1); for (int i = 0; i < m; i++) { int ind; cin >> ind; cin >> v[ind]; } int res = 0, idx; memset(vis, false, m + 1); for (int i = 1; i <= m; i++) { if (!vis[i]) { memset(dfsV, false, m + 1); int temp = dfs(i); if (res < temp) { res = temp; idx = i; } } } cout << idx << endl; }
intmain(int argc, constchar *argv[]) { fast; int t; cin >> t; for (int i = 0; i < t; i++) { cout << "Case " << i + 1 << ": "; solve(); }
Year ago, I saw many blogger collects their friends blog post via Github Action auto run. Therefore, I always want to try it out.
Anyways, I build it with typescript. Also, if you have any questions or suggestions, any issues or prs are welcomed.
Step1: Generate useful Data from RSS-feed
This project is based on rss feed, so if you or your friend blog doesn’t have /feed, feed.xml, atom.xml, or any kinds of xml file contains your full blogs’ intel, you will have to generate one yourself.
