abc181_e - Transformable Teacher

31 Jan 2021 — Tags: sorting,brute_force,implementation — URL

Let’s sort the students by their heights. Without the teacher the optimal answer would be the sum of differences on the sorted array.

For each $m$ heights for the teacher, we need to find where should be placed to provide an optimal solution for that given height. Out of all, we’ll pick the best.

We can build two arrays that that maintain the difference sum for the prefix up to $i$ and the suffix until $i$. To find the optimal placement of the teacher given height $j$, we shall binary search the place where it should be placed in order to keep the array sorted. Given that new position, we can use our prefix and suffix array to answer get the answer.

Time complexity: $O(n \log{n})$

Memory complexity: $O(n)$

Click to show code.

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll solve(vi h, vi w)
{
    int n = h.size();
    sort(begin(h), end(h), greater<int>());
    vector<ll> rans(n), lans(n);
    rans[n - 1] = h[n - 1], lans[0] = h[0];
    for (int i = n - 2; i >= 0; --i)
        rans[i] = h[i] - rans[i + 1];
    for (int i = 1; i < n; ++i)
        lans[i] = lans[i - 1] + h[i] * (i % 2 == 0 ? +1 : -1);
    ll ans = 1e15;
    for (auto wi : w)
    {
        auto it = lower_bound(begin(h), end(h), wi, greater<int>());
        ll cur;
        if (it == h.end())
            cur = lans[n - 1] - wi;
        else if (it == h.begin())
            cur = wi - rans[0];
        else
        {
            int i = distance(begin(h), it);
            if (i % 2 == 0)
                cur = lans[i - 1] + wi - rans[i];
            else
                cur = lans[i - 1] - wi + rans[i];
        }
        ans = min(ans, cur);
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vi h(n), w(m);
    for (auto &hi : h)
        cin >> hi;
    for (auto &wi : w)
        cin >> wi;
    cout << solve(h, w) << endl;
    return 0;
}

abc181_d - Hachi

31 Jan 2021 — Tags: math,brute_force — URL

It’s a known rule that numbers whose last three digits are divisible by 8, are also divisible by 8. We can therefore split the problem into two cases:

$x >= 100$: Do as said above
$x < 100$: Brute_force all multiples of 8 and reverse multiples of 8, $<100$.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
bool solve(string s)
{
    if (s.size() <= 2)
    {
        int x = stoi(s);
        reverse(begin(s), end(s));
        int y = stoi(s);
        if (x % 8 == 0 or y % 8 == 0)
            return true;
    }
    vector<int> cnt(10, 0);
    for (auto c : s)
        cnt[c - '0']++;
    for (int x = 104; x < 1000; x += 8)
    {
        auto d = cnt;
        for (char x : to_string(x))
            d[x - '0']--;
        if (all_of(begin(d), end(d), [](int x) { return x >= 0; }))
            return true;
    }
    return false;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    string s;
    cin >> s;
    cout << (solve(s) ? "Yes" : "No") << endl;
    return 0;
}

abc181_c - Collinearity

31 Jan 2021 — Tags: math,brute_force — URL

Given three points, we can check if they lie on the same line by testing if their slope is the same. We shall do some algebra first to work with integers and avoid precision errors.

Using this fact, we can try all triplets of points to see if they fulfill this condition.

Time complexity: $O(n^3)$

Memory complexity: $O(n)$

Click to show code.

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
bool solve(vector<ii> points)
{
    int n = points.size();
    sort(begin(points), end(points));
    for (int i = 0; i < n - 2; ++i)
    {
        auto [x1, y1] = points[i];
        for (int j = i + 1; j < n - 1; ++j)
        {
            auto [x2, y2] = points[j];
            for (int k = j + 1; k < n; ++k)
            {
                auto [x3, y3] = points[k];
                if ((x2 - x1) * (y3 - y2) == (x3 - x2) * (y2 - y1))
                    return true;
            }
        }
    }
    return false;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<ii> points(n);
    for (auto &[x, y] : points)
        cin >> x >> y;
    cout << (solve(points) ? "Yes" : "No") << endl;
    return 0;
}

abc181_b - Trapezoid Sum

31 Jan 2021 — Tags: math,easy — URL

Each operation $a, b$, is equivalent to increasing the answer by $sq(b) - sq(a)$, where $sq(n)$ is the sum of the first $n$ natural numbers.

Time complexity: $O(n)$

Memory complexity: $O(1)$

Click to show code.

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll sq(ll n) { return (n * (n + 1)) / 2; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        ans += sq(b) - sq(a - 1);
    }
    cout << ans << endl;
    return 0;
}

abc181_a - Heavy_Rotation

31 Jan 2021 — Tags: easy — URL

If $n$ days pass, Takahashi will wear black if $n$ is odd and white otherwise.

Time complexity: $O(1)$

Memory complexity: $O(1)$

Click to show code.

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    cout << (n % 2 ? "Black" : "White") << endl;
    return 0;
}

qtree - Query On Tree

30 Jan 2021 — Tags: None

Click to show code.

using namespace std;
using ll = long long;
using iii = tuple<int, int, int>;
using vi = vector<int>;
const int NMAX = 1e4 + 11;
int n, parent[NMAX], depth[NMAX], heavy[NMAX], head[NMAX], pos[NMAX], hldcnt;
int cost[NMAX];
vi g[NMAX];
iii edges[NMAX];
struct segtree
{
    int n;
    int t[4 * NMAX];
    segtree() {}
    segtree(int n) : n(n) {}
    void build(int a[]) { build_util(a, 1, 0, n - 1); }
    void build_util(int a[], int v, int tl, int tr)
    {
        if (tl == tr)
            t[v] = cost[tl];
        else
        {
            int tm = (tl + tr) >> 1;
            build_util(a, (v << 1), tl, tm);
            build_util(a, (v << 1) + 1, tm + 1, tr);
            t[v] = ((t[v << 1]) > (t[(v << 1) + 1]) ? (t[v << 1]) : (t[(v << 1) + 1]));
        }
    }
    int query(int ql, int qr) { return query_util(1, 0, n - 1, ql, qr); }
    int query_util(int v, int tl, int tr, int ql, int qr)
    {
        if (ql > qr)
            return 0;
        if (ql == tl and qr == tr)
            return t[v];
        int tm = (tl + tr) >> 1;
        int rl = query_util((v << 1), tl, tm, ql, min(tm, qr));
        int rr = query_util((v << 1) + 1, tm + 1, tr, max(tm + 1, ql), qr);
        return ((rl) > (rr) ? (rl) : (rr));
    }
    void update(int pos, int new_val)
    {
        update_util(1, 0, n - 1, pos, new_val);
    }
    void update_util(int v, int tl, int tr, int pos, int new_val)
    {
        if (tl > pos or tr < pos)
            return;
        if (tl == tr and tl == pos)
            t[v] = new_val;
        else
        {
            int tm = (tl + tr) >> 1;
            update_util(v << 1, tl, tm, pos, new_val);
            update_util((v << 1) + 1, tm + 1, tr, pos, new_val);
            t[v] = ((t[v << 1]) > (t[(v << 1) + 1]) ? (t[v << 1]) : (t[(v << 1) + 1]));
        }
    }
} st;
int dfs(int u)
{
    int usz = 1, mvz = 0, vsz;
    for (auto v : g[u])
    {
        if (v != parent[u])
        {
            parent[v] = u;
            depth[v] = depth[u] + 1;
            vsz = dfs(v);
            usz += vsz;
            if (vsz > mvz)
            {
                mvz = vsz;
                heavy[u] = v;
            }
        }
    }
    return usz;
}
void decompose(int u, int h)
{
    head[u] = h;
    pos[u] = hldcnt++;
    if (heavy[u] != -1)
        decompose(heavy[u], h);
    for (auto v : g[u])
    {
        if (parent[u] != v and heavy[u] != v)
            decompose(v, v);
    }
}
void update(int i, int new_value)
{
    auto uvc = edges[i];
    int u = get<0>(uvc);
    int v = get<1>(uvc);
    if (depth[u] > depth[v])
        swap(u, v);
    st.update(pos[v], new_value);
}
int query(int u, int v)
{
    int ans = 0;
    while (head[u] != head[v])
    {
        if (depth[head[u]] > depth[head[v]])
            swap(u, v);
        ans = ((ans) > (st.query(pos[head[v]], pos[v])) ? (ans) : (st.query(pos[head[v]], pos[v])));
        v = parent[head[v]];
    }
    if (depth[u] > depth[v])
        swap(u, v);
    return ((ans) > (st.query(pos[u] + 1, pos[v])) ? (ans) : (st.query(pos[u] + 1, pos[v])));
}
void reset(void)
{
    hldcnt = 0;
    memset(heavy, -1, sizeof(*heavy) * n);
    for (int i = 0; i < n; ++i)
        g[i].clear();
}
int main(void)
{
    char s[10];
    int t, u, v, c, ei, nv;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        st = segtree(n);
        reset();
        for (int i = 0; i < n - 1; ++i)
        {
            scanf("%d %d %d", &u, &v, &c);
            edges[i] = make_tuple(u - 1, v - 1, c);
            g[u - 1].push_back(v - 1);
            g[v - 1].push_back(u - 1);
        }
        dfs(0);
        decompose(0, 0);
        for (int i = 0; i < n - 1; ++i)
        {
            auto uvc = edges[i];
            u = get<0>(uvc);
            v = get<1>(uvc);
            c = get<2>(uvc);
            if (depth[u] > depth[v])
                swap(u, v);
            cost[pos[v]] = c;
        }
        st.build(cost);
        while (scanf("%s", s) and s[0] != 'D')
        {
            if (s[0] == 'Q')
            {
                scanf("%d %d", &u, &v);
                printf("%d\n", query(u - 1, v - 1));
            }
            else
            {
                scanf("%d %d", &ei, &nv);
                update(ei - 1, nv);
            }
        }
    }
    return 0;
}

abc190_f - Shift And Inversions

30 Jan 2021 — Tags: constructive,inversions,fenwick_tree,dp — URL

Let’s denote $a_i$ to the $i$th element in the original array (0-indexed).

Think about how does the inversion count for a given shift $k - 1$ to $k$.

The element $a_{k - 1}$ will become the last element. All other elements will be at its left, so that means that it will gain an inversion count of the quantity of such elements greater than it.
All other elements in step $k - 1$ where at the right of such element, so they will lose all inversions they had with $a_{k - 1}$.

This leads us to formulate the following dp:

\[dp(k) = dp(k - 1) + |\{a_j > a_{k - 1}\}| - |\{a_j < a_{k - 1}\}|\]

Since $a$ is a permutation of $0… n - 1$:

$ {a_j > a_{k - 1}} = n - 1 - a_{k - 1}$
$ {a_j < a_{k - 1}} = a_{k - 1}$

Which would result into: $dp(k) = dp(k - 1) + n - 1 - 2 a_{k - 1}$

Finally, we can compute $dp(0)$ in $O(n \log{n})$ using the standard fenwick tree approach to count inversions.

Time complexity: $O(n \log{n} + n)$

Memory complexity: $O(a_{max} + n)$

Click to show code.

using namespace std;
using namespace atcoder;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
ll count_inversions(const vector<ll> &a)
{
    ll amax = *max_element(begin(a), end(a)) + 1, ans = 0;
    fenwick_tree<ll> fw(amax);
    for (auto ai : a)
    {
        ans += fw.sum(ai + 1, amax);
        fw.add(ai, 1);
    }
    return ans;
}
vector<ll> solve(const vector<ll> &a)
{
    int n = a.size();
    vector<ll> ans(n);
    ans[0] = count_inversions(a);
    for (int k = 1; k < n; ++k)
        ans[k] = ans[k - 1] + n - 1 - 2 * a[k - 1];
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<ll> a(n);
    for (auto &ai : a)
        cin >> ai;
    auto ans = solve(a);
    for (auto x : ans)
        cout << x << endl;
    return 0;
}

abc190_d - Staircase Sequences

30 Jan 2021 — Tags: math,number_theory — URL

Editorial

Time complexity: $O(\sqrt{n})$

Memory complexity: $O(1)$

Click to show code.

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    ll n;
    cin >> n;
    n *= 2;
    int ans = 0;
    for (ll k = 1, sqn = sqrt(n); k <= sqn; ++k)
        if (n % k == 0 and (n / k - k + 1) % 2 == 0)
            ans += 2;
    cout << ans << endl;
    return 0;
}

abc190_c - Bowls And Dishes

30 Jan 2021 — Tags: bitmasks,brute_force — URL

Let’s iterate over all possible configurations of dishes and pick the one which fulfills the most conditions.

Since $k \leq 16$ we can do this by defining a bitmask where:

$b(i, j)$ : if $j = 0$, $c_i$ is taken, if $j = 0$, then $d_i$ is taken.

Time complexity: $O(2^k (n + m))$

Memory complexity: $O(n + m)$

Click to show code.

using namespace std;
using ll = long long;
using ii = array<int, 2>;
using vi = vector<int>;
ll solve(vector<ii> conditions, vector<ii> options, int n)
{
    int k = options.size();
    vector<int> balls(n);
    ll ans = 0;
    for (int mask = 0; mask < (1 << k); ++mask)
    {
        fill(begin(balls), end(balls), 0);
        for (int i = 0; i < k; ++i)
        {
            int j = (mask >> i) & 1;
            balls[options[i][j]]++;
        }
        ll cur = 0;
        for (auto [u, v] : conditions)
            cur += balls[u] && balls[v];
        ans = max(ans, cur);
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<ii> conditions(m);
    for (auto &[u, v] : conditions)
        cin >> u >> v, u--, v--;
    int k;
    cin >> k;
    vector<ii> options(k);
    for (auto &[u, v] : options)
        cin >> u >> v, u--, v--;
    cout << solve(conditions, options, n) << endl;
    return 0;
}

abc190_b - Magic 3

30 Jan 2021 — Tags: implementation — URL

For each monster test if it will yield damage.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, s, d;
    cin >> n >> s >> d;
    ll ans = 0;
    for (int i = 0; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        if (x < s and y > d)
            ans += y;
    }
    cout << (ans > 0 ? "Yes" : "No") << endl;
    return 0;
}

Older Newer

Competitive Programming Solutions