292B - Network Topology

27 Dec 2020 — Tags: graphs,implementation — URL

Given a connected graph, $G$, with $n$ nodes, you can determine it’s type by its distribution of node-degrees.

bus: $n-2$ nodes with degree $2$, and $2$ nodes with degree $1$ (the extremes).
ring: $n$ nodes of degree $2$.
star: $n - 1$ nodes with degree $1$ and $1$ node with degree $n-1$.

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>;
string solve(vi d)
{
    auto dgone = [](int dg) { return dg == 1; };
    auto dgtwo = [](int dg) { return dg == 2; };
    int n = (int)(d).size();
    sort(begin(d), end(d));
    if (all_of(begin(d), end(d), dgtwo))
        return "ring topology";
    if (all_of(begin(d) + 2, end(d), dgtwo) and
        all_of(begin(d), begin(d) + 2, dgone))
        return "bus topology";
    if (d.back() == n - 1 and all_of(begin(d), end(d) - 1, dgone))
        return "star topology";
    return "unknown topology";
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vi d(n, 0);
    while (m--)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        d[u]++, d[v]++;
    }
    cout << solve(d) << endl;
    return 0;
}

574B - Bear And Three Musketeers

26 Dec 2020 — Tags: graphs,brute_force — URL

The Editorial mentions an interesting trick to reduce complexity from $O(n^3)$ to $O(n^2 + mn)$.

Iterate pairs, $(u, v)$, and only check for a third vertex, $c$ ,if there already exists an edge between $(u, v)$. edge between the pair. In this way we are checking for each edge, $O(m)$, a third vertex $c$.

Time complexity: $O(n^2 + mn)$

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>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<vi> g(n, vi(n, 0));
    vector<int> d(n, 0);
    while (m--)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        d[u]++, d[v]++;
        g[u][v]++, g[v][u]++;
    }
    int const INF = 1e9;
    int ans = INF;
    for (int u = 0; u < n; ++u)
    {
        for (int v = u + 1; v < n; ++v)
        {
            if (g[u][v])
            {
                for (int c = v + 1; c < n; ++c)
                {
                    if (g[u][c] and g[v][c])
                        ans = min(ans, d[u] + d[v] + d[c]);
                }
            }
        }
    }
    cout << (ans == INF ? -1 : ans - 6) << endl;
    return 0;
}

330B - Road Construction

26 Dec 2020 — Tags: graph,brute_force — URL

Note that the constraint (distance between pairs is at most $2$) will only be satisfied by a star graph (all nodes connected to a center node). The problem reduces to find a center for such graph and connect all other nodes to it.

Note that there’s always an answer because of the $m < \frac{n}{2}$ constraint.

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, m;
    cin >> n >> m;
    vector<bool> is_center(n, true);
    while (m--)
    {
        int u, v;
        cin >> u >> v, u--, v--;
        is_center[u] = is_center[v] = false;
    }
    int root =
        distance(begin(is_center),
                 find_if(begin(is_center), end(is_center), [](bool flag) { return flag; }));
    cout << n - 1 << endl;
    for (int u = 0; u < n; ++u)
    {
        if (u == root)
            continue;
        cout << root + 1 << " " << u + 1 << endl;
    }
    return 0;
}

284A - Cows And Primitive Roots

26 Dec 2020 — Tags: brute_force,modulo — URL

Brute force and test all $x < p$. Check this editorial for a more mathy solution.

Time complexity: $O(p^2)$

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 solve(int p)
{
    int ans = 0;
    for (int x = 1; x < p; ++x)
    {
        bool flag = true;
        int y = x % p;
        for (int i = 1; i <= p - 2; ++i)
        {
            if (y == 1)
            {
                flag = false;
                break;
            }
            y = (y * x) % p;
        }
        if (y % p != 1)
            flag = false;
        ans += flag;
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int p;
    cin >> p;
    cout << solve(p) << endl;
    return 0;
}

742A - Arpas Hard Exam And Mehrdads Naive Cheat

25 Dec 2020 — Tags: easy — URL

Note that $1378^n \equiv 8^n \mod 10$. Furthermore, for $n >= 1$, you might notice a pattern with $n$ if you list answers for small numbers. They repeat with a period of 4, so just hardcode them.

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, ans[4] = {8, 4, 2, 6};
    cin >> n;
    if (n == 0)
        cout << 1 << endl;
    else
        cout << ans[(n - 1) % 4] << endl;
    return 0;
}

659A - Round House

25 Dec 2020 — Tags: easy,modulo — URL \[a + b \mod n\]

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, a, b;
    cin >> n >> a >> b;
    cout << (((a - 1 + b) % n) + n) % n + 1 << endl;
    return 0;
}

abc143_d - Triangles

24 Dec 2020 — Tags: sorting,binary_search — URL

If we have the length of the sticks, $l$, sorted non-decreasingly, we can count all possible triangles by listing two sides $a$, and $b$ and finding the position, $c$, where the length starts to become degenerate.

Remember that $a + b > c$ and $a \leq b \leq c$.

This can be done with binary search or two-pointers.

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>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi l(n);
    for (auto &li : l)
        cin >> li;
    sort(begin(l), end(l));
    int ans = 0;
    for (int i = 0; i < n - 2; ++i)
    {
        for (int j = i + 1; j < n - 1; ++j)
        {
            auto it = lower_bound(begin(l) + j + 1, end(l), l[i] + l[j]);
            int k = distance(begin(l), it);
            if (k - 1 > j)
                ans += k - j - 1;
        }
    }
    cout << ans << endl;
    return 0;
}

575 - Skew Binary

24 Dec 2020 — Tags: implementation — URL

Same as converting from binary to decimal but with $2^{k + 1} - 1$ as factor.

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);
    string n;
    while (cin >> n and n != "0")
    {
        int m = (int)(n).size(), x = 0;
        reverse(begin(n), end(n));
        for (int i = 0; i < m; ++i)
            x += ((1LL << (i + 1)) - 1) * (n[i] - '0');
        cout << x << endl;
    }
    return 0;
}

LITE - Light Switching

23 Dec 2020 — Tags: data_structures,segment_tree,lazy — URL

Choose your favorite range-update, range-query data structure. I’ll be using AtCoder’s Lazy Segment Tree for this.

Let’s store for each segtree node the amount of elements is covering in its respective range, $n$ and the amount of lights set “on”, $setcnt$.

A range-update (switching lights), $(l, r)$, would be equal to turning off all set lights and vice versa, or $setcnt = n - setcnt$.

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>;
struct S
{
    int n, set_cnt;
};
S op(S a, S b) { return {a.n + b.n, a.set_cnt + b.set_cnt}; }
S e() { return {0, 0}; }
using F = bool;
S mapping(F f, S x) { return (f ? S{x.n, x.n - x.set_cnt} : x); }
F composition(F f, F g) { return f ^ g; }
F id() { return 0; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vector<S> a(n);
    for (auto &ai : a)
        ai = S{1, 0};
    using namespace atcoder;
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    while (m--)
    {
        int type, l, r;
        cin >> type >> l >> r, l--, r--;
        if (type == 0)
            seg.apply(l, r + 1, true);
        else
        {
            auto x = seg.prod(l, r + 1);
            cout << x.set_cnt << endl;
        }
    }
    return 0;
}

GSS5 - Can You Answer These Queries V

22 Dec 2020 — Tags: data_structures,segment_tree — URL

Assume [x1, y1] and [x2, y2] are non-overlapping ranges. The answer will be the maximum suffix of [x1, y1], plus the total sum of range ]y1, x2[, plus the maximum prefix of [x2, y2]. Computing maximum subarrays on ranges is a well known technique described in CP-Algorithms.

Handling overlapping ranges, requires a bit of casework:

Best suffix of [x1, y1] + best prefix of ]y1, y2]
Best suffix of [x1, x2[ + best prefix of [x2, y2]
Best subarray in [x2, y1]

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>;
int const INF = 1e7;
struct Node
{
    int pre, suf, tot, best;
    Node(int x = 0) : pre(x), suf(x), tot(x), best(x) {}
};
Node merge(Node a, Node b)
{
    Node ans;
    ans.pre = max(a.pre, a.tot + b.pre);
    ans.suf = max(b.suf, b.tot + a.suf);
    ans.tot = a.tot + b.tot;
    ans.best = max({a.best, b.best, a.suf + b.pre});
    return ans;
}
Node e()
{
    Node ans(-INF);
    ans.tot = 0;
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, q;
        cin >> n;
        vector<Node> a(n);
        for (auto &ai : a)
        {
            int x;
            cin >> x;
            ai = Node(x);
        }
        atcoder::segtree<Node, merge, e> st(a);
        cin >> q;
        while (q--)
        {
            int x1, y1, x2, y2, ans;
            cin >> x1 >> y1 >> x2 >> y2, x1--, y1--, x2--, y2--;
            if (y1 < x2)
                ans = st.prod(x1, y1 + 1).suf + st.prod(y1 + 1, x2).tot +
                      st.prod(x2, y2 + 1).pre;
            else
                ans = max(
                    {st.prod(x2, y1 + 1).best,
                     st.prod(x1, x2).suf + st.prod(x2, y2 + 1).pre,
                     st.prod(x2, y1 + 1).suf + st.prod(y1 + 1, y2 + 1).pre});
            cout << ans << endl;
        }
    }
    return 0;
}

Competitive Programming Solutions