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:
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))
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();
}
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])
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
Explanation coming soon.........
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)
DFS through the tree, keeping track of time. Keep track of the tree with max time and then size as tiebreaker.
#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);
}
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.
#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';
}
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
#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';
}
That wasn't too bad...
Hard
This one was fun. We claim that the solution is the same as the previous one pretending that {}[] is the same as (), multiplied by 3 to the power of the # of ?s.
Proof:
First, we can prove that each symbol in A will map to a symbol in B. This is because symbols in A cannot match to other symbols in A, because there are an odd # of symbols in between.
Let us further suppose that there are no ?s. Then, there is a bijection from sequences containing only () restricted by A to sequences containing ()[]{} that are restricted by A because you can change the character (and its matching character in B) back to the original.
For example:
A = ({])}
simplified A = (()))
possible sequence = (((()())))
constrained by original A ({{[]()}})
Each ? means that we have 3x the possibilty for that character ([{ so we multiply by 3^# of ?s.
This is just Michael's code for P8 but modified by me.
// thx michael orz
#include "bits/stdc++.h"
using namespace std;
const ll mod = 1e9 + 7;
ll add(ll a, ll b) { return (a + b) % mod; }
ll dp[4001][4001];
ll binpow(ll x,ll p){
ll r=1,sq=x;
while(p){
if(p&1)r=r*sq%mod;
sq=sq*sq%mod;p>>=1;
}
return r;
}
ll main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
ll n;
string s;
cin >> n >> s;
if (s[0] == ')') {
cout << 0 << '\n';
return 0;
}
memset(dp, 0, sizeof dp);
dp[0][0] = 1;
for (ll i = 0; i < n * 2; i++) {
for (ll 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] == ')'||s[i / 2] == '}'||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] == '('||s[i / 2] == '['||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);
}
}
}
ll wild=0;
for (auto x:s)if(x=='?')wild++;
cout << 1ll*dp[2 * n][0]*binpow(3,wild)%mod << '\n';
}
My favorite problem :) Honestly easier than P9.
Different bounds for rows and columns motivate going through by rows (we assume rows have the smaller of the two dimensions) Note that (by a brute force) there are only 60 valid possibilities for a row. Thus, we can represent bitmasks as numbers between 1-60.
We use bitmask dp: dp[row][mask][mask2] represents the max # of haybales you can get if you are at row i, the current row's haybales are mask2, and the previous row's haybales are mask. Then dp[row][mask][mask2] = max(dp[row-1][pmask][mask] + 1) over all compatible pmasks (compatible meaning that their bits are distinct).
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <vector>
using namespace std;
#define pcnt __builtin_popcount
#define cnt(x) pcnt(tom(x))
int tom(int x) {
switch(x) {
case 0: return 0;case 1: return 1;case 2: return 2;case 3: return 4;case 4: return 8;case 5: return 9;case 6: return 16;case 7: return 17;case 8: return 18;case 9: return 32;case 10: return 33;case 11: return 34;case 12: return 36;case 13: return 64;case 14: return 65;case 15: return 66;case 16: return 68;case 17: return 72;case 18: return 73;case 19: return 128;case 20: return 129;case 21: return 130;case 22: return 132;case 23: return 136;case 24: return 137;case 25: return 144;case 26: return 145;case 27: return 146;case 28: return 256;case 29: return 257;case 30: return 258;case 31: return 260;case 32: return 264;case 33: return 265;case 34: return 272;case 35: return 273;case 36: return 274;case 37: return 288;case 38: return 289;case 39: return 290;case 40: return 292;case 41: return 512;case 42: return 513;case 43: return 514;case 44: return 516;case 45: return 520;case 46: return 521;case 47: return 528;case 48: return 529;case 49: return 530;case 50: return 544;case 51: return 545;case 52: return 546;case 53: return 548;case 54: return 576;case 55: return 577;case 56: return 578;case 57: return 580;case 58: return 584;case 59: return 585;
}
return 99;
}
int compat(int m1,int m2,int m3) {
return pcnt(m1|m2|m3)==pcnt(m1)+pcnt(m2)+pcnt(m3);
}
int main()
{
int n, m; scanf("%d%d",&n,&m);
vector<int>mp(n);
for (int i=0;i<n;i++)for(int j=0;j<m;j++){char x;scanf(" %c",&x);
if(x=='D')mp[i]|=1<<j;
}
for(int i=0;i<n;i++)mp[i]=~mp[i];
if(n == 1) {
int mx=0;
for (int j=0; j<60; j++) {
if(tom(j) & mp[0]) continue;
mx=max(mx,cnt(j));
}
printf("%d\n",mx);
return 0;
}
vector<vector<vector<int>>> dp(n,vector<vector<int>>(60,vector<int>(60)));
for (int j=0; j<60; j++) {
for (int k=0;k<60;k++) {
if(tom(j)&mp[0])continue;
if(tom(k)&mp[1])continue;
if(!compat(0,tom(j),tom(k)))continue;
dp[1][j][k] = cnt(j)+cnt(k);
}
}
for (int i=2; i<n; i++) {
for (int j=0; j<60; j++) {
for (int k=0;k<60;k++) {
if(dp[i-1][j][k]==0)continue;
// printf("dp[%d][%d][%d] = %d\n",i-1,j,k,dp[i-1][j][k]);
for (int x=0;x<60;x++) {
if(tom(x)&mp[i])continue;
if(!compat(tom(j),tom(k),tom(x)))continue;
dp[i][k][x] = max(dp[i][k][x],dp[i-1][j][k] + cnt(x));
// printf("\t=> dp[%d][%d][%d] = %d\n",i,k,x,dp[i-1][j][k]+cnt(x));
}
}
}
}
int mx=0;
for (int j=0;j<60;j++)for(int k=0;k<60;k++)mx=max(mx,dp[n-1][j][k]);
printf("%d\n",mx);
}
