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

// there are 4(n-1) squares on the boundary as it is 4*n - 4 (overcounted squares)
// there are (n-2)*(n-2) squares on the interior as we exclude the boundaries so the side length is n-2

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';
}

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 node 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';
}

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);
}