2024 Summer Camp Coding Practice Record for Graduate Recommendations
Leetcode problem-solving can be a tad monotonous, so I plan to tackle one real problem set for a day (smile). I won't be tackling particularly difficult problems or extensive simulations to ensure a fast problem-solving pace.
I will follow a specific order in solving problems.
2023 Graduate Recommendation (5/14)
All Included
A: All Included
Total Time Limit: 1000ms Memory Limit: 65536kB Description You have designed a new encryption technique that encodes information by cleverly inserting random strings between the characters of the original message. Due to patent issues, we will not discuss how to generate and insert strings into the original information in detail. However, to verify your method, it is necessary to write a program to check if all the original information is included in the final string.
Given two strings s and t, you need to determine if s is a "subsequence" of t. That is, if you remove some characters from t, the remaining characters will concatenate to form s.
Input The input consists of multiple test cases. Each test case is a pair of specific strings s and t, composed of alphanumeric ASCII characters and separated by a space. The length of s and t does not exceed 100000.
Output For each test case, if s is a "subsequence" of t, print "Yes"; otherwise, print "No".
Warm-up problem. Use the two-pointer technique to scan once.
#include <iostream>
#include <string>
using namespace std;
int n;
bool isSub(string str, string sub) {
int i = 0, l = 0;
while (i < sub.size() && l < str.size()) {
if (str[l] == sub[i]) i++, l++;
else l++;
}
return i == sub.size();
}
int main() {
string substr, str;
while (cin >> substr >> str) {
cout << (isSub(str, substr) ? "Yes" : "No" ) << endl;
}
}
Closest Fraction
B: Closest Fraction Total Time Limit: 1000ms Memory Limit: 65536kB Description
What is the largest reduced fraction less than A/B for which the denominator does not exceed N?
Input
Three positive integers N, A, and B, separated by a single space. .
Output
Two positive integers, which are the numerator and the denominator of the desired fraction, separated by a single space.
Scan from 1 to N, and choose the numerator and denominator using this method. Since , is acceptable.
Pay special attention to using multiplication to prevent division precision issues. The maximum value of 1000*1000 won't overflow an int.
#include <iostream>
using namespace std;
int n, a, b;
int main() {
cin >> n >> a >> b;
// The denominator must be less than or equal to n and less than a / b
int mxi = -1, mxj = -1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
// j/i
if (j*b < a *i) {
if (mxi == -1 || mxj == -1 || j * mxi > mxj * i) mxj = j, mxi = i;
}
}
}
cout << mxj << " " << mxi << endl;
}
Stepping Squares
Stepping Squares
Total Time Limit: 1000ms Memory Limit: 65536kB Description
You are given a grid of squares. The grid's boundaries extend infinitely in all directions. We make the following assumptions: a. You can move only one step from the current square to an adjacent square; b. The square you step on collapses and cannot be stepped on again; c. You can only move north, east, and west;
The task: calculate how many different ways you can step on n squares given the above rules.
Input The number of steps n (n ≤ 20).
Output The number of different ways calculated.
One look and it's DP or DFS. Here it uses DFS and backtracking, which runs at most 20 * 3 times. An array of size 41 * 21 was used, starting from 20. This array is used to check if a position has been visited.
#include <iostream>
using namespace std;
int mat[42][21];
int res;
int n;
int dx[3] = {0, 1, 0};
int dy[3] = {-1, 0, 1};
void dfs(int x, int y, int u) {
if (u == n) {
res ++;
return;
}
for (int i = 0; i < 3; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (mat[xx][yy]) continue;
mat[xx][yy] = 1;
dfs(xx, yy, u + 1);
mat[xx][yy] = 0;
}
}
int main() {
cin >> n;
mat[20][0] = 1;
dfs(20, 0, 0);
cout << res;
}
Nuclear Power Plant
D: Nuclear Power Plant
Total Time Limit: 5000ms Single Test Point Time Limit: 1000ms Memory Limit: 131072kB Description A nuclear power plant has N pits containing nuclear material, arranged in a straight line. If nuclear material is placed in M consecutive pits, an explosion will occur, so some pits might be left empty.
Task: For given N and M, find the total number of ways to place nuclear material without causing an explosion.
Input A single line with two positive integers N and M (1 < N < 50, ).
Output A single positive integer S, representing the total number of ways.
For , the most difficult problem. Initially, it used a DFS with two states: placing or not placing at each position, ending up with complexity, which is infeasible. However, it might still score a few points on a real test.
Instead, choose DP. Initially, a 2D DP was written, but the transition equation was unclear.
represents the number of valid ways up to position i, with j representing two states: placing at position i or not. For cases where i < m, simply add the ways; for i == m, subtract one invalid way of placing all m positions; for i > m, the invalid cases are clear: place nuclear materials in i-m+1 to i, leaving a free i-m position such that positions before i-m-1 can be placed in any manner. The number of invalid ways is 1 * f[i-m-1].
Also, take care of int overflow. Assuming no M constraint, there are 2^n possible ways. Since the constraint does not significantly reduce the number of ways, using long long is safest.
/* O(2^n) */
void dfs(int x, int u, int p) {
// u current total placed
// x current position
// p current consecutive placed
if (p >= m) return;
if (x == n) {
res ++;
return;
}
dfs(x + 1, u, 0); // do not place here
dfs(x + 1, u + 1, p + 1); // place here
return;
}
long long f[55];
int main() {
cin >> n >> m;
// f[i][0/1] represents placing or not placing at position i (valid ways)
// f[n][0] + f[n][1]
// f[i][0] = f[i-1][0] + f[i-1][1]
// f[i][1] = f[i-1][0] + f[i-1][1] - invalid ways
// For i == m, simply subtract one way of placing all.
// For i > m, we subtract ways placing in positions i-m+1 to i, leaving i-m with i-m-1 positions without constraints—handled by multiplication principle.
f[0][0] = 1;
for (int i = 1; i < m; i++) f[i][1] = f[i][0] = f[i-1][0] + f[i-1][1];
for (int i = m; i <= n;) {
f[i][0] = f[i-1][0] + f[i-1][1];
f[i][1] = f[i-1][0] + f[i-1][1] - 1;
break;
}
for (int i = m + 1; i <= n; i++) {
f[i][0] = f[i-1][0] + f[i-1][1];
f[i][1] = f[i-1][0] + f[i-1][1] - f[i-1-m][1] - f[i-1-m][0];
}
cout << f[n][0] + f[n][1];
}
Afterwards, it becomes clear that merging into a one-dimensional solution is more optimal.
long long f[55];
int main() {
cin >> n >> m;
// Convert to a one-dimensional problem
// f[i][1] + f[i][0] = 2*(f[i-1][0] + f[i-1][1]) - invalid ways
f[0] = 1;
for (int i = 1; i <= n; i++) {
f[i] = 2 * f[i-1];
if (i == m) f[i] -= 1;
if (i > m) f[i] -= f[i-1-m];
}
cout << f[n];
}
Highways
G: Highways Total Time Limit: 1000ms Memory Limit: 65536kB Description The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. As a result, traffic is difficult in Flatopia. The Flatopian government is planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system.
Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns and follows straight lines, usable in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town.
The government wants to minimize the length of the longest highway to be built, guaranteeing that every town is reachable from every other town.
Input The first line of input is an integer T, representing the number of test cases. For each test case, the first line is an integer N (), representing the number of towns. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (an integer within [1, 65536]) between village i and village j. An empty line follows each test case.
Output For each test case, output an integer, representing the length of the longest road to be built such that all towns are connected, and this value is minimized.
Summarize the problem: find the minimum spanning tree such that the weight of its longest edge is minimized. This is effectively a minimum spanning tree problem with a greedy nature, which can be proven.
The understanding translates to a shortest-path minimum spanning tree problem. Use Prim or Kruskal algorithm.
Note: When reading input, change its self-weight to infinity (0x3f3f3f3f).
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int n;
void prim(vector<vector<int>>& mat) {
vector<int> dist(mat.size(), 0x3f3f3f3f);
vector<bool> st(mat.size(), false);
dist[1] = 0;
int res = INT_MIN;
for (int i = 1; i < mat.size(); i++) {
int v = -1;
for (int j = 1; j < mat.size(); j++) if (!st[j] && (v == -1 || dist[j] < dist[v] )) v = j;
st[v] = true;
res = max(res, dist[v]);
for (int j = 1; j < mat.size(); j++) {
if (!st[j] && dist[j] > mat[v][j]) dist[j] = mat[v][j];
}
}
cout << res << endl;
}
int main() {
scanf("%d", &n);
while (n--) {
string tmp;
getline(cin, tmp);
int m;
scanf("%d", &m);
vector<vector<int>> mat(m + 1, vector<int>(m + 1));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= m; j ++) {
scanf("%d", &mat[i][j]);
if (i == j) mat[i][j] = 0x3f3f3f3f;
}
}
prim(mat);
}
}