Divide by Zero 2018 LeeRinji

Check the string

#include <bits/stdc++.h>
using namespace std;
char s[8195];
int c[3];
int main()
{
	scanf("%s", s);
	for (int i = 0; s[i]; ++i)
	{
		++c[s[i] - 'a'];
		if (i && s[i] < s[i - 1])
			return printf("NO"), 0;
	}
	printf(c[0] && c[1] && (c[2] == c[0] || c[2] == c[1]) ? "YES" : "NO");
}

Minimize the error

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<ll> q;
ll n, k, t, a[1023];
int main()
{
	scanf("%lld%lld%lld", &n, &k, &t);
	k += t;
	for (ll i = 0; i < n; ++i)
		scanf("%lld", &a[i]);
	for (ll i = 0; i < n; ++i)
	{
		scanf("%lld", &t);
		q.push(abs(a[i] - t));
	}
	while (k--)
	{
		t = q.top();
		q.pop();
		q.push(t ? t - 1 : t + 1);
	}
	for (t = 0; !q.empty(); q.pop())
		t += q.top() * q.top();
	printf("%lld", t);
}

Subsequence Counting

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> v;
ll x, d;
int main()
{
	scanf("%lld%lld", &x, &d);
	for (ll a = 1; x; a += d)
		for (ll i = 1; i <= x; i <<= 1)
			v.push_back(a), x -= i;
	printf("%d\n", v.size());
	for (auto i : v)
		printf("%lld ", i);
}

Alternating Tree

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5 + 7;
struct Mod
{
	const ll M;
	Mod(ll M) : M(M) {}
	ll add(ll a, ll b) const { return ((a + b) % M + M) % M; }
	ll mul(ll a, ll b) const { return a * b % M; }
} M(1e9 + 7);
vector<ll> e[N];
ll n, ans, v[N], f[N][2], g[N][2];
void dfs(ll u, ll fa = N)
{
	for (auto to : e[u])
		if (to != fa)
		{
			dfs(to, u);
			f[u][0] = M.add(f[u][0] + f[to][1], -M.mul(g[to][1], v[u]));
			f[u][1] = M.add(f[u][1] + f[to][0], M.mul(g[to][0], v[u]));
			g[u][0] = M.add(g[u][0], g[to][1]);
			g[u][1] = M.add(g[u][1], g[to][0]);
		}
	for (auto to : e[u])
		if (to != fa)
		{
			if (g[to][0])
				ans = M.add(ans, M.mul(g[u][1] - g[to][0], f[to][0] * 2 + g[to][0] * v[u]));
			if (g[to][1])
				ans = M.add(ans, M.mul(g[u][0] - g[to][1], f[to][1] * 2 - g[to][1] * v[u]));
		}
	ans = M.add(ans, f[u][1] * 2 + v[u]);
	f[u][1] = M.add(f[u][1], v[u]);
	g[u][1] = M.add(g[u][1], 1);
}
int main()
{
	scanf("%lld", &n);
	for (ll i = 1; i <= n; ++i)
		scanf("%lld", &v[i]);
	for (ll i = 1, x, y; i < n; ++i)
	{
		scanf("%lld%lld", &x, &y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1);
	printf("%lld", ans);
}