Competitive Programming Solutions

abc190_a - Very Very Primitive Game

30 Jan 2021 — Tags: easy — URL

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);
    string ans[2] = {"Aoki", "Takahashi"};
    int a, b, c;
    cin >> a >> b >> c;
    if (c == 0)
        cout << ans[a > b] << endl;
    else
        cout << ans[a >= b] << endl;
    return 0;
}

2134 - Path Queries Ii

30 Jan 2021 — Tags: data_structures,trees,hld,segment_tree — URL

Same as problem Path Queries but with maximum as the segment tree operation.

Time complexity: $O(q \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>;
using S = long long;
S op(S a, S b) { return max(a, b); }
S e() { return 0; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vi val(n);
    for (auto &x : val)
        cin >> x;
    HLD<atcoder::segtree, S, op, e> hld(n);
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        hld.add_edge(u, v);
    }
    hld();
    for (int u = 0; u < n; ++u)
        hld.set(u, val[u]);
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int u, x;
            cin >> u >> x, u--;
            hld.set(u, x);
        }
        else
        {
            int u, v;
            cin >> u >> v, u--, v--;
            cout << hld.query(u, v) << " ";
        }
    }
    cout << endl;
    return 0;
}

1138 - Path Queries

30 Jan 2021 — Tags: data_structures,hld,segment_tree — URL

Decompose the tree into heavy paths using Heavy Light Decomposition and use segment tree on each heavy path to handle queries in paths.

Time complexity: $O(q \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>;
using S = long long;
S op(S a, S b) { return a + b; }
S e() { return 0; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vi val(n);
    for (auto &x : val)
        cin >> x;
    HLD<atcoder::segtree, S, op, e> hld(n);
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        hld.add_edge(u, v);
    }
    hld();
    for (int u = 0; u < n; ++u)
        hld.set(u, val[u]);
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int u, x;
            cin >> u >> x, u--;
            hld.set(u, x);
        }
        else
        {
            int u;
            cin >> u, u--;
            cout << hld.query(0, u) << endl;
        }
    }
    return 0;
}

abc151_e - Max Min Sum

29 Jan 2021 — Tags: combinatorics,counting,contribution — URL

Assume the array $A$ is sorted.

Note that each $a_i$ will be counted as a maximum element $C(i - 1, k - 1)$ times. Conversely, it will be counted $C(n - i, k - 1)$ times as minimum.

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>;
template <int NMAX, typename mint>
struct Combinations
{
    std::vector<mint> fact, inv_fact;
    Combinations(void) { precompute(NMAX + 1); }
    void precompute(int len)
    {
        fact.resize(len), inv_fact.resize(len);
        inv_fact[0] = fact[0] = 1;
        for (int i = 1; i < len; i++)
        {
            inv_fact[i] = inv_fact[i - 1] * mint(i).inv();
            fact[i] = fact[i - 1] * i;
        }
    }
    mint C(int n, int k) const
    {
        assert(int(fact.size()) > n);
        if (k > n or k < 0)
            return 0;
        return fact[n] * inv_fact[k] * inv_fact[n - k];
    }
    mint factorial(int n)
    {
        assert(int(fact.size()) > n);
        return fact[n];
    }
    mint inverse_factorial(int n)
    {
        assert(int(fact.size()) > n);
        return inv_fact[n];
    }
    mint operator()(int n, int k) const { return C(n, k); }
};
ll solve(vector<ll> a, int k)
{
    using mint = atcoder::modint1000000007;
    int const NMAX = 1e5 + 1;
    int n = a.size();
    sort(begin(a), end(a));
    Combinations<NMAX, mint> C;
    mint ans = 0;
    for (int i = 0; i < n; ++i)
        ans += a[i] * C(i, k - 1) - a[i] * C(n - i - 1, k - 1);
    return ans.val();
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    for (auto &ai : a)
        cin >> ai;
    cout << solve(a, k) << endl;
    return 0;
}

abc151_d - Maze Master

29 Jan 2021 — Tags: bfs,graphs — URL

The problem basically asks to ask of the diameter of the graph represented by the board. We can get this number by launching a bfs from each cell to find the furthest reachable cell.

Time complexity: $O(n^4)$

Memory complexity: $O(n^2)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
using namespace std;
ll bfs(int i, int j, vector<string> &board)
{
    int h = (int)(board).size(), w = (int)(board[0]).size();
    vector<vector<bool>> visited(h, vector<bool>(w, 0));
    vector<vector<ll>> dist(h, vector<ll>(w, 1e9));
    queue<ii> frontier;
    frontier.emplace(i, j);
    visited[i][j] = true;
    dist[i][j] = 0;
    ll ans = 0;
    auto check = [&](int r, int c) {
        return board[r][c] != '#' and !visited[r][c];
    };
    auto visit = [&](int r, int c, ll d) {
        frontier.emplace(r, c);
        visited[r][c] = true;
        dist[r][c] = d;
        ans = max(ans, d);
    };
    while (not frontier.empty())
    {
        auto [r, c] = frontier.front();
        frontier.pop();
        if (check(r, c + 1))
            visit(r, c + 1, dist[r][c] + 1);
        if (check(r + 1, c))
            visit(r + 1, c, dist[r][c] + 1);
        if (check(r, c - 1))
            visit(r, c - 1, dist[r][c] + 1);
        if (check(r - 1, c))
            visit(r - 1, c, dist[r][c] + 1);
    }
    return ans;
}
ll solve(vector<string> board)
{
    int h = (int)(board).size() - 2, w = (int)(board[0]).size() - 2;
    ll ans = 0;
    for (int i = 1; i <= h; ++i)
        for (int j = 1; j <= w; ++j)
            if (board[i][j] != '#')
                ans = max(ans, bfs(i, j, board));
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int h, w;
    cin >> h >> w;
    vector<string> board(h + 2);
    board[0] = string(w + 2, '#');
    board[h + 1] = string(w + 2, '#');
    for (int i = 1; i <= h; ++i)
    {
        cin >> board[i];
        board[i] = "#" + board[i] + "#";
    }
    cout << solve(board) << endl;
    return 0;
}

abc151_c - Welcome To Atcoder

29 Jan 2021 — Tags: implementation — URL

Implementation.

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>;
ii solve(vector<ii> sub_status, int n)
{
    vi problem(n, 0);
    ll penalty = 0;
    for (auto [p, s] : sub_status)
    {
        if (s == -1 and problem[p] <= 0)
        {
            problem[p] += s;
        }
        else if (s == +1)
        {
            if (problem[p] < 0)
                penalty += -problem[p];
            problem[p] = 1;
        }
    }
    ll score = count_if(begin(problem), end(problem), [](int x) { return x > 0; });
    return {score, penalty};
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<ii> sub_status(m);
    for (int i = 0; i < m; ++i)
    {
        string si;
        cin >> sub_status[i].first >> si, sub_status[i].first--;
        sub_status[i].second = si == "AC" ? +1 : -1;
    }
    auto [score, penalty] = solve(sub_status, n);
    cout << score << " " << penalty << endl;
    return 0;
}

abc151_b - Achieve The Goal

29 Jan 2021 — Tags: math,easy — URL

Let $x$ be the score needed to achieve a total of $M$ points.

$x = M * N - \sum_{1}^{n - 1} a_i$

If $x <= k$ then it’s achievable, otherwise it’s not.

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>;
ll ceil(ll a, ll b) { return (a + b - 1) / b; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, k, m;
    cin >> n >> k >> m;
    vi a(n - 1);
    for (auto &ai : a)
        cin >> ai;
    ll sum = accumulate(begin(a), end(a), 0LL);
    ll x = max(m * n - sum, 0LL);
    x = x > k ? -1 : x;
    cout << x << endl;
    return 0;
}

abc151_a - Next Alphabet

29 Jan 2021 — Tags: easy — URL

$C + 1$

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);
    char c;
    cin >> c;
    cout << char(c + 1) << endl;
    return 0;
}

1476D - Journey

29 Jan 2021 — Tags: dsu,graphs — URL

As the problem states, each country has two states (original roads and reversed roads). Let’s picture this with a bipartite graph, where each city has two corresponding nodes. For a given city $u$, let’s call its corresponding node on the original roads $id0(u)$ and $id1(1)$ on the reversed roads.

The ith road in this graph will connect $id0(i - 1)$ and $id1(i)$ if it’s a R road and $id0(i)$ and $id1(i - 1)$ otherwise.

Note that such edges can be considered undirected, since each time one edge is taken all of them should be reversed.

Using this, note that the answer of a given city $u$ is the size of the connected component that $id0(u)$ lies on.

We can use a dfs or a disjoint set union to compute this efficiently.

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>;
vi solve(string s)
{
    int n = s.size();
    auto id0 = [](int u) { return 2 * u; };
    auto id1 = [](int u) { return 2 * u + 1; };
    atcoder::dsu dsu(2 * (n + 1));
    for (int i = 1; i <= n; ++i)
    {
        if (s[i - 1] == 'L')
            dsu.merge(id0(i), id1(i - 1));
        else
            dsu.merge(id0(i - 1), id1(i));
    }
    vi ans(n + 1);
    for (int i = 0; i <= n; ++i)
        ans[i] = dsu.size(2 * i);
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        string s;
        cin >> n >> s;
        auto ans = solve(s);
        for (auto x : ans)
            cout << x << " ";
        cout << endl;
    }
    return 0;
}

1476C - Longest Simple Cycle

29 Jan 2021 — Tags: greedy — URL

We’ll denote a cycle’s length as the number of nodes it traverses.

Observations:

  1. when $a_i = b_i$, the $i-1$ chain necesarily divides the graph into two parts. The longest cycle cannot go through $i-1$.

We’ll scan from left to right and compute the maximum length cycle that ends at position $i$.

We’ll also keep the length of the longest non-closed cycle up to $i$, call it $open_i$.

Using this two informations, we can check for the following for each $i$:

  1. The answer is $open_{i - 1}$ + the length of the $i$th chain, $c_i$, closing the cycle.
  2. $open_i$ will be the maximum between the length of the current chain, $c_i$, and $c_{i - 1} + 2$.

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>;
ll solve(vector<ll> a, vector<ll> b, vector<ll> c)
{
    int n = c.size();
    vector<ll> w(n);
    for (int i = 0; i < n - 1; ++i)
        w[i] = abs(a[i + 1] - b[i + 1]) + 1;
    w[n - 1] = c[n - 1];
    ll ans = 0, cur = w[0];
    for (int i = 1; i < n; ++i)
    {
        ans = max(ans, cur + c[i]);
        cur = w[i] == 1 ? 1 : max(w[i], cur + c[i] - w[i] + 2);
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<ll> a(n), b(n), c(n);
        for (auto &ci : c)
            cin >> ci;
        for (auto &ai : a)
            cin >> ai;
        for (auto &bi : b)
            cin >> bi;
        cout << solve(a, b, c) << endl;
    }
    return 0;
}