# Divide by Zero 2018

## 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]));
}
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]);
}
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);
}
``````