I didn’t do so well this week. I missed an obvious sorting solution for a while on question C and didn’t think of using DP for question D. Also didn’t bother to look at E but I had just learnt about and written a post about topological sort which was its solution.
A – camel Case
Given a string \(S\), print the position of the first and only capital letter within it. Nothing much to be said here:
P1
#include <iostream>
using namespace std;
int main() {
string s;
cin >> s;
for (int i = 0; i < s.size(); i++)
if (isupper(s[i])) cout << i + 1;
return 0;
}B – Trimmed Mean
A person enters a gymnastics contest, where \(5N\) judges give a score. Find the mean of the scores excluding the lowest and highest \(N\) scores. Error margin of answer is \(10^{-5}\).Also quite easy:
P2
#include <iostream>
#include <iomanip>
using namespace std;
int n, x[501];
long double ans;
int main() {
cout << fixed << setprecision(5);
cin >> n;
for (int i = 1; i <= 5 * n; i++)
cin >> x[i];
sort(x + 1, x + 5 * n + 1);
for (int i = n + 1; i <= 4 * n; i++)
ans += x[i];
ans /= n * 3;
cout << ans;
return 0;
}C – LRUD Instructions 2
A person starts on the origin of a two-dimensional plane. The person moves around following the characters of a string of length \(N\) containing L\((x -= 1)\), R\((x += 1)\), U\((y += 1)\), and D\((y -= 1)\). Determine if the person has passed over the same position twice.
Solution: create a structure pos with two integers \(x\) and \(y\) and record all the positions by going through the string. Sort the positions by their x-value and then their y-value. By iterating through the points we can compare each position to the next, determining our answer.
P3
#include <iostream>
using namespace std;
struct pos{
int x, y;
} a[200001];
bool cmp(pos X, pos Y) {
if (X.x != Y.x) return X.x < Y.x;
else return X.y < Y.y;
}
int n, x, y;
string s;
int main() {
cin >> n >> s;
for (int i = 1; i <= n; i++) {
char c = s[i - 1];
if (c == 'U') y++;
if (c == 'D') y--;
if (c == 'R') x++;
if (c == 'L') x--;
a[i].x = x, a[i].y = y;
}
sort(a, a + n + 1, cmp);
for (int i = 1; i <= n; i++)
if (a[i].x == a[i - 1].x && a[i].y == a[i - 1].y) {
cout << "Yes";
return 0;
}
cout << "No";
return 0;
}D – Flip Cards
You have \(n\) cards placed in a line. The \(i\)th card has \(A_i\) written on top and \(B_i\) on the back. How many ways are there, modulo \(998244353\), are there to flip some(possibly zero) of the cards so that no adjacent cards show the same number?
Solution: this is a DP problem. Let dp[i][j] denote the number of ways for only the first \(i\) cards such that the \(i\)th card is facing up if \(j = 0\), and down if \(j = 1\). Then, the recurrence is quite easy to construct.
P4
#include <iostream>
using namespace std;
const int M = 998244353;
int n, a[200001], b[200001], dp[200001][2];
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i] >> b[i];
dp[1][0] = dp[1][1] = 1;
for (int i = 2; i <= n; i++) {
if (a[i] != b[i - 1]) dp[i][0] = dp[i - 1][1];
if (a[i] != a[i - 1]) dp[i][0] = (dp[i][0] + dp[i - 1][0]) % M;
if (b[i] != a[i - 1]) dp[i][1] = dp[i - 1][0];
if (b[i] != b[i - 1]) dp[i][1] = (dp[i][1] + dp[i - 1][1]) % M;
}
cout << (dp[n][0] + dp[n][1]) % M;
return 0;
}E – Find Permutation
There is a permutation \((A_1, A_2, \cdots ,A_N)\)of \(1, 2, \cdots, N\). While you do not know the permutation, you know $M$ pairs of integers \((X_i, Y_i)\) such that \(A_{X_i} < A_{Y_i}\). If the permutation can be uniquely determined from these conditions, print Yes, and on the next line the permutation. If not, print No.
Solution: We run a topological sort, where the nodes are the values of \(A\), and the directed edges go from small to large. You can read my article on topological sort to get the basics. If there are multiple nodes inserted into the queue from one node, then there is no unique solution.
P5
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int n, m, x, y, deg[200001], ans[200001], k;
vector<int> graph[200001];
queue<int> q;
int main() {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> x >> y;
deg[y]++;
graph[x].push_back(y);
}
for (int i = 1; i <= n; i++)
if (!deg[i]) q.push(i);
if (q.size() > 1) {
cout << "No";
return 0;
}
while (!q.empty()) {
int cur = q.front();
q.pop();
ans[cur] = ++k;
int cnt = 0;
for (int i : graph[cur]) {
deg[i]--;
if (!deg[i]) {
cnt++;
q.push(i);
}
}
if (cnt > 1) {
cout << "No";
return 0;
}
}
cout << "Yes\n";
for (int i = 1; i <= n; i++)
cout << ans[i] << ' ';
return 0;
}
