Posts

Kick Start 2019 Round B Building Palindromes (5pts, 12pts) 判断给定区间内的子字符串是否是回文串。 Solution: Prefix Sum 判断字符串是否是回文串只需要判断字符串里个数为奇数的字符的数量是否小于等于1，但如果每次都遍历一遍给定的区间肯定会超时，所以我们需要对给定的原始字符串进行预处理，计算出每一个位置的前缀和（从下标为0到下标为i - 1的位置的字符的总数）。这样在查询的时候就只有O(1)的时间复杂度了。 时间复杂度：O(N) 空间复杂度：O(N) // C++ #include <iostream> #include <cmath> #include <cstdio> #include <math.h> #include <limits> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; int main() { int total_test_case_number; cin >> total_test_case_number; for (int case_number = 1; case_number <= total_test_case_number; ++case_number) { int N, Q, m, n, total = 0; cin >> N >> Q; string words; cin >> words; vector<vector<int>> odds(N + 1, vector<int>(26)); for (int i = 1; i <= N; ++i) { for (int j = 0; j < 26; ++j) odds[i][j] = odds[i - 1][j]; ++odds[i][words[i - 1] - 'A']; } for (int q = 0; q < Q; ++q) { cin >> m >> n; int odd = 0; for (int j = 0; j < 26; ++j) odd += ((odds[n][j] - odds[m - 1][j]) % 2 != 0); total += odd <= 1; } printf("Case #%d: %d\n", case_number, total); } return 0; } Energy Stones (17pts, 24pts) 在所有物品消耗完之前吃掉，使得能够获得的energy最多，类似于背包问题。 ...

Code Jam 2019 Round 1A Pylons (8pts, 23pts) 在m*n的网格里移动，每次移动后的位置不能与之前的位置在同一行/列/对角线上。 Solution: BackTracking 类似于八皇后问题，不过每次的限制条件只和上一个位置有关，可以用回溯解决。 时间复杂度：O(m^2 * n^2) 空间复杂度：O(m * n) // C++ #include <iostream> #include <cmath> #include <cstdio> #include <math.h> #include <limits> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; int m, n; bool BackTracking(int t, int i, int j, vector<vector<bool>> &visited, vector<vector<int>> &res) { visited[i][j] = true; res[t] = {i, j}; if (t + 1 == m * n) return true; for (int x = 0; x < m; ++x) { for (int y = 0; y < n; ++y) { int r = (x + i) % m, c = (y + j) % n; if (!visited[r][c] && r != i && c != j && r + c != i + j && r - c != i - j && BackTracking(t + 1, r, c, visited, res)) return true; } } visited[i][j] = false; return false; } int main() { int total_test_case_number; cin >> total_test_case_number; for (int case_number = 1; case_number <= total_test_case_number; ++case_number) { bool rev = false; cin >> m >> n; if (m > n) { rev = true; swap(n, m); } vector<vector<bool>> visited(m, vector<bool>(n, false)); vector<vector<int>> res(m * n, vector<int>()); printf("Case #%d: ", case_number); if (BackTracking(0, 0, 0, visited, res)) { printf("POSSIBLE\n"); for (int i = 0; i < m * n; ++i) if (!rev) printf("%d %d\n", res[i][0] + 1, res[i][1] + 1); else printf("%d %d\n", res[i][1] + 1, res[i][0] + 1); } else printf("IMPOSSIBLE\n"); } return 0; } Alien Rhyme (10pts, 27pts) 找到后缀相同的一对单词，后缀的长度可以自己定义，其他单词的后缀不能与这一对相同，使得这样的单词对最多。 ...

Code Jam 2019 Qualification Round Foregone Solution (6pts, 10pts, 1pts) 将一个带有数字4的数拆分为两个不带数字4的数。 Solution: Construction 输入的数一定带有数字4，对于每一位上的数字4，我们可以将其拆分为2+2（或1+3）的两个数。输入数据最大是10的100次方，所以我们可以将其作为字符串处理。 时间复杂度：O(n) 空间复杂度：O(1) // C++ #include <iostream> #include <cmath> #include <math.h> #include <limits> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <string> #include <map> #include <set> #include <unordered_map> #include <unordered_set> using namespace std; int main() { int T; cin >> T; for (int t = 1; t <= T; ++t) { string N; cin >> N; string a, b; for (auto c:N) { a += c == '4' ? '2' : c; b += c == '4' ? '2' : '0'; } while (a[0] == '0') a.erase(a.begin()); while (b[0] == '0') b.erase(b.begin()); cout << "Case #" << t << ": " << a << " " << b << endl; } } You Can Go Your Own Way (5pts, 9pts, 10pts) 在n*n的矩阵里从(0,0)走到(n-1,n-1)，只能向右或向下走。矩阵里有一条已有的路径，不能与该路径有重合。最常规的做法是DFS/BFS，时间复杂度为O(n^2)。 ...

Kick Start 2019 Round A Training (7pts, 13pts) 一共有N个人，从中选P个人，计算这P个人中 skill rating 的最大值与其他人的 skill rating 的差值之和。 $$ \sum_{i}^{j} max(rating) - rating[i] $$ Solution: Sort + Prefix Sum 先对数组排序，然后在长度为N的有序数组中遍历长为P的所有连续子数组，计算子数组中的最大值与其他值的差值之和。 $$ \sum_{i}^{j - 1} rating[j] - rating[i] $$ 如果直接遍历长为P的子数组会浪费很多时间，可以将上面的公式简化为如下。 $$ \sum_{i}^{j - 1} rating[j] - rating[i] = rating[j] * (j - 1 - i) - \sum_{i}^{j - 1} rating[i] $$ 为了避免重复计算 $$ \sum_{i}^{j - 1} rating[i] $$，可以用一个长为N+1的数组将原始数组的前缀和保存下来，这样每次直接计算 prefix[j] - prefix[i] 就能得到 $$ \sum_{i}^{j - 1} rating[i] $$ 了，时间复杂度是O(N)。 ...

Methods to Prevent Overfitting in Deep Learning Overfitting Overfitting refers to that when a model fits the training data well but cannot predict the test data correctly, we may say that the model lacks the ability of generalization. It is important to figure out how it happens, and how we can prevent overfitting from the very beginning. Detect Overfitting The simplest way to detect overfitting is to split the dataset into two parts: the training set for training the model, and the test set for testing the accuracy of the model on a dataset that it has never seen before. Of course, we will also partition part of the training set to be the validation set for fine-tuning hyper-parameters. Note that it is necessary to shuffle all the data before splitting. ...