As the official editorial is promised to come out later, I will write an unofficial editorial for now. Some of the solutions are from my teammate tcmmichaelb139 orz.
Easy
These problems are quite trivial, so I will only provide solutions:
P1
n=int(input())
arr=[]
for i in range(n):arr.append(input().strip().replace('x',''))
for i in range(n):
cnt=arr[i].count('y')
arr[i]=arr[i].replace('y','')
arr[i]+=cnt*'y'
arr=sorted(arr,key=lambda x:(-len(x),x))
print('\n'.join(arr))
P2
Michael's solution:
#include "bits/stdc++.h"
using namespace std;
string pi = "31415926535897932384626433832... (truncated copy-paste from internet)";
void solve() {
string s;
cin >> s;
for (int i = 0; i < s.length(); i++)
if (s[i] != pi[i]) {
cout << i << '\n';
return;
}
cout << s.length() << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) solve();
}
P3
n=int(input())
b=int(input())
x=int(input())
y=int(input())
s=4*(n-1)*y+(n-2)*(n-2)*x
print(["Walter will like this lab","Sorry Mr. Fring, no can do"][s>b])
P4
Michael did this one, but it looks like pain...
#include "bits/stdc++.h"
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
string s;
cin >> s;
int a = 0, b = 0;
char cur = s[0];
int len = 1;
for (int i = 1; i < s.length(); i++) {
if (cur != s[i]) {
if (len >= 3) {
if (cur == '<')
a -= 20 + (len - 3) * 5;
else if (cur == '>')
a += 20 + (len - 3) * 5;
else if (cur == 'v')
b -= 20 + (len - 3) * 5;
else if (cur == '^')
b += 20 + (len - 3) * 5;
} else {
if (cur == '<')
a -= 2 * len;
else if (cur == '>')
a += 2 * len;
else if (cur == 'v')
b -= 2 * len;
else if (cur == '^')
b += 2 * len;
}
len = 1;
cur = s[i];
} else {
len++;
}
}
if (len >= 3) {
if (cur == '<')
a -= 20 + (len - 3) * 5;
else if (cur == '>')
a += 20 + (len - 3) * 5;
else if (cur == 'v')
b -= 20 + (len - 3) * 5;
else if (cur == '^')
b += 20 + (len - 3) * 5;
} else {
if (cur == '<')
a -= 2 * len;
else if (cur == '>')
a += 2 * len;
else if (cur == 'v')
b -= 2 * len;
else if (cur == '^')
b += 2 * len;
}
cout << "(" << a << "," << b << ")" << '\n';
}
That's it for the easy problems, they were all pretty straightforward.
Medium
P5
Explanation coming soon.........
Code
n=int(input())
a=[0]+[int(x)for x in input().split()]
b=0
for i in range(1,n+1):
b+=max(a[i]-a[i-1],0)
print(b)
P6
DFS through the tree, keeping track of time. Keep track of the tree with max time and then size as tiebreaker.
Code
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <vector>
#include <algorithm>
using namespace std;
int lastlay=-1;
int lastnode=-1;
vector<vector<int>> adj(1000);
void dfs(int v,int p,int lay){
if(lay>lastlay)lastlay=lay,lastnode=v;
else if(lay==lastlay&&v>lastnode)lastnode=v;
for (auto&x:adj[v])if(x!=p)dfs(x,v,lay+1);
}
int main()
{
int r, n; scanf("%d %d", &r, &n);
r--;
for (int i=0;i<n;i++){int u,v;scanf("%d %d",&u,&v);
u--;v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
for (auto&v:adj)sort(v.begin(),v.end());
dfs(r,r,0);
printf("%d\n",lastnode+1);
}
P7
Michael did this one, so my explanation might not be great. Just brute force while keeping track of visited letters in O(3^26) time. Since the testcases are random, the average time is a lot less, so brute force works.
Code
#include "bits/stdc++.h"
using namespace std;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
int n, m;
vector<string> v;
int ans = 0;
void dfs(int x, int y, vector<int> vis, int done) {
ans = max(ans, done);
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if (vis[v[nx][ny] - 'A']) continue;
vector<int> vis2 = vis;
vis2[v[nx][ny] - 'A'] = true;
dfs(nx, ny, vis2, done + 1);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
v.push_back(s);
}
vector<int> vis(27, false);
vis[v[0][0] - 'A'] = true;
dfs(0, 0, vis, 1);
cout << ans << '\n';
}
P8
Use dp: dp[i][j] represents # of ways to create a parenthesis sequence up to index i with j extra left parenthesis (
If you are on a (: Add dp[i][j] to dp[i+1][j+1]
If you are on a ): Add dp[i][j] to dp[i+1][j-1] if j>0
If you are on a B's turn or a ?: Do both
Code
#include "bits/stdc++.h"
using namespace std;
const int MOD = 1e9 + 7;
int add(int a, int b) { return (a + b) % MOD; }
int dp[4001][4001];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
string s;
cin >> n >> s;
if (s[0] == ')') {
cout << 0 << '\n';
return 0;
}
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for (int i = 0; i < n * 2; i++) {
for (int j = 0; j < n * 2; j++) {
if (i & 1) {
if (j > 0)
dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
} else {
if (s[i / 2] == ')') {
if (j > 0)
dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
} else if (s[i / 2] == '(')
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
else if (s[i / 2] == '?') {
if (j > 0)
dp[i + 1][j - 1] = add(dp[i + 1][j - 1], dp[i][j]);
dp[i + 1][j + 1] = add(dp[i + 1][j + 1], dp[i][j]);
} else
assert(false);
}
}
}
cout << dp[2 * n][0] << '\n';
}
