242E - Xor On Segment

22 Dec 2020 — Tags: data_structures,lazy,segment_tree,bitmask — URL

Let the ith Segment Tree maintain information on the ith bit of all numbers in the array $A$.

The sum query would be the same as counting the set bits for all bits and then adding them together (with it’s corresponding $2^i$ factor).

The update query would be the same as swapping all numbers on the ith bit if such bit is set on $x$.

I’m trying AtCoder’s Lazy Segment Tree.

Let’s define the structure’s parameters.

S: A pair of integers, n and cnt_set (the number of elements in that range and the number of set bits ($1$s) in that range.
op: Standard pair addition
e : $(0, 0)$
F : The set of functions $F$ is uniquely determined by a boolean value. $F= (f_0, f_1)$.
mapping: $f_1(S) \to S$ means applying xor to all the bits denoted by node $S$. This is equal to n - cnt_set. Note that $f_0$ doesn’t change anything.
composition: $f_j(f_i(S)) = (i \oplus j) \oplus S $
id: $f_0$

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

Memory complexity: $O(n \log{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, cnt_set;
};
using F = bool;
S op(S l, S r) { return {l.n + r.n, l.cnt_set + r.cnt_set}; }
S e() { return {0, 0}; }
S mapping(F l, S r) { return (l ? S{r.n, r.n - r.cnt_set} : r); }
F composition(F l, F r) { return l ^ r; }
F id() { return 0; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n;
    array<vector<S>, 20> a;
    for_each(begin(a), end(a), [n](auto &v) { v.resize(n); });
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        for (int j = 0; j < 20; ++j)
            a[j][i] = {1, (x >> j) & 1};
    }
    using lazy_segtree =
        atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>;
    array<lazy_segtree, 20> st;
    for (int i = 0; i < 20; ++i)
        st[i] = lazy_segtree(a[i]);
    cin >> m;
    while (m--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int l, r;
            cin >> l >> r, l--, r--;
            ll ans = 0;
            for (int i = 0; i < 20; ++i)
            {
                auto cur = st[i].prod(l, r + 1);
                ans += (1LL << i) * cur.cnt_set;
            }
            cout << ans << endl;
        }
        else
        {
            int l, r, x;
            cin >> l >> r >> x, l--, r--;
            for (int i = 0; i < 20; ++i)
                st[i].apply(l, r + 1, (x >> i) & 1LL);
        }
    }
    return 0;
}

BGSHOOT - Shoot And Kill

21 Dec 2020 — Tags: data_structures,segment_tree,coordinate_compression — URL

Essentially the problem asks you to find the maximum number of intersections of ranges [x, y] in a given range [l, r].

Since the ranges are too big, we have to do coordinate compression to be able to fit all of them in an array.

So, ideally we’ll have a frequency array $freq$, where $freq_i$ denotes the number of ranges that pass through that point. To compute this efficiently, we may use a difference array to construct the frequency array in $O(n)$.

Having done this, we may use a segment tree built on top of the resulting frequency array, to efficiently query for maximum on a range [l, r].

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

Memory complexity: $O(n)$

Click to show code.

using namespace std;
using namespace atcoder;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename T>
map<T, int> compress(vector<T> values)
{
    map<T, int> mp;
    int cnt = 0;
    for (auto v : values)
        mp[v];
    for (auto &[k, v] : mp)
        v = cnt++;
    return mp;
}
int e(void) { return 0; }
int f(int a, int b) { return max(a, b); }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, q;
    cin >> n;
    vector<ii> xy(n);
    vector<int> values;
    for (auto &[x, y] : xy)
    {
        cin >> x >> y, x--, y--;
        values.push_back(x), values.push_back(y);
    }
    cin >> q;
    vector<ii> lr(q);
    for (auto &[l, r] : lr)
    {
        cin >> l >> r, l--, r--;
        values.push_back(l), values.push_back(r);
    }
    auto c = compress(values);
    int m = (int)(c).size();
    vector<int> freq(m + 2, 0);
    for (auto [x, y] : xy)
        freq[c[x]] += 1, freq[c[y] + 1] -= 1;
    int cnt = 0;
    for (auto &x : freq)
        cnt += x, x = cnt;
    segtree<int, f, e> st(freq);
    for (auto [l, r] : lr)
        cout << st.prod(c[l], c[r] + 1) << endl;
    return 0;
}

1465B - Fair Numbers

20 Dec 2020 — Tags: brute_force,observation — URL

Note that the minimum fair integer $x$ such that $n \leq x$ is at most $lcm(1, 2, …, 9)$ steps away ($2520$). This is the period of fair numbers that contain all single non-zero digits, therefore, the maximum period.

Brute force approach:

Test if number is fair, if not increment it and try again until it is.

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>;
bool fair(ll n)
{
    ll x = n;
    while (x != 0)
    {
        int d = x % 10;
        if (d and n % d)
            return false;
        x /= 10;
    }
    return true;
}
ll solve(ll n)
{
    while (not fair(n))
        ++n;
    return n;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        ll n;
        cin >> n;
        cout << solve(n) << endl;
    }
    return 0;
}

abc186_e - Throne

19 Dec 2020 — Tags: number_theory,modulo,crt — URL

Let the throne lie at position $0$ and Takahashi at position $S$. We want to find:

\[s + xk \equiv 0 \mod n\]

Furthermore, to simplify the problem, let $y = s + xk$, the position where Takahashi first meets the Throne (if we were to count distance rather than displacement). Assume that such a value exists.

We can say a couple of things about $y$.

$y$ will be at the Throne’s position (after some number of laps around the circle), or: $y \equiv 0 \mod n$
$y$ is reachable by some number of $k$-displacements: $y - s \equiv 0 \mod k$

If we arrange 2. to be $y \equiv s \mod k$ then we have two modular congruencies that we can solve using the chinese remainder theorem.

Having solved the modular equations, the only thing left to do is to solve for $x$ in the aforementioned equivalence: $y=s+xk$.

Time complexity: $O(\log{lcm(s, k)})$

Memory complexity: $O(n)$

Click to show code.

using namespace std;
using ll = long long;
ll solve(ll n, ll s, ll k)
{
    auto [y, z] = atcoder::crt({0, s}, {n, k});
    if (z == 0)
        return -1;
    if (y < s)
        y += z;
    return (y - s) / k;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        ll n, s, k;
        cin >> n >> s >> k;
        cout << solve(n, s, k) << endl;
    }
    return 0;
}

abc186_d - Sum Of Difference

19 Dec 2020 — Tags: math,sorting — URL

Two observations:

$ x - y = y - x $.
Each $a_i$ is paired with all other elements $a_j$, $i!=j$.

This allows us to reorder the elements, both in position and in the operand.

Sort the array non-decreasingly. In this way we won’t have to worry about possible negative values:

\[\sum_{i=n}^{1} (i \times a_i - \sum_{j = 1}^{i - 1} a_j)\]

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;
    cin >> n;
    vector<ll> a(n), pa(n);
    read_n(begin(a), n);
    sort(begin(a), end(a));
    partial_sum(begin(a), end(a), begin(pa));
    ll ans = 0;
    for (int i = n - 1; i >= 1; --i)
        ans += i * a[i] - pa[i - 1];
    cout << ans << endl;
    return 0;
}

abc186_c - Unluck 7

19 Dec 2020 — Tags: brute_force,math — URL

Try all numbers from [1, n] and check if they contain $7$ in their octal or decimal representation.

Time complexity: $O(n \log{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>;
bool bad(int n, int base)
{
    while (n)
    {
        if ((n % base) == 7)
            return true;
        n /= base;
    }
    return false;
}
int solve(int n)
{
    int ans = n;
    for (int i = n; i > 0; --i)
        if (bad(i, 10) or bad(i, 8))
            ans--;
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}

abc186_b - Blocks On Grid

19 Dec 2020 — Tags: easy,implementation — URL

To make all blocks the same height, make them the same height. as the smallest block.

Time complexity: $O(hw)$

Memory complexity: $O(hw)$

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 h, w;
    cin >> h >> w;
    ll minv = 1e9, sum = 0;
    for (int r = 0; r < h; ++r)
    {
        for (int c = 0; c < w; ++c)
        {
            ll arc;
            cin >> arc;
            minv = min(minv, arc);
            sum += arc;
        }
    }
    cout << sum - (h * w * minv) << endl;
    return 0;
}

abc186_a - Brick

19 Dec 2020 — Tags: easy — URL \[floor(\frac{n}{w})\]

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, w;
    cin >> n >> w;
    cout << n / w << endl;
    return 0;
}

abc185_e - Sequence Matching

18 Dec 2020 — Tags: dp — URL

Lol, it was edit distance. Editorial

Time complexity: $O(n^2)$

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 solve(vi a, vi b)
{
    int const INF = 1e8;
    int n = (int)(a).size(), m = (int)(b).size();
    vector<vi> dp(n + 1, vi(m + 1, INF));
    for (int i = 0; i <= n; ++i)
        dp[i][0] = i;
    for (int j = 0; j <= m; ++j)
        dp[0][j] = j;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            auto &ans = dp[i][j];
            ans = min(ans, dp[i - 1][j] + 1);
            ans = min(ans, dp[i][j - 1] + 1);
            ans = min(ans, dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]));
        }
    }
    return dp[n][m];
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vi a(n), b(m);
    read_n(begin(a), n);
    read_n(begin(b), m);
    cout << solve(a, b) << endl;
    return 0;
}

abc157_e - Simple String Queries

18 Dec 2020 — Tags: segment_tree,data_structures — URL

Build a segment tree where nodes store a frequency array of the characters in their respective range.

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 Node
{
    array<int, 26> cnt;
    Node() { fill(begin(cnt), end(cnt), 0); }
    Node(int i) : Node() { cnt[i]++; }
};
Node op(Node a, Node b)
{
    Node ans;
    for (int i = 0; i < 26; ++i)
        ans.cnt[i] = a.cnt[i] + b.cnt[i];
    return ans;
}
Node e() { return Node(); }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, q;
    cin >> n;
    vector<Node> a(n);
    for (auto &x : a)
    {
        char ch;
        cin >> ch;
        x.cnt[ch - 'a']++;
    }
    atcoder::segtree<Node, op, e> st(a);
    cin >> q;
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int i;
            char ch;
            cin >> i >> ch, i--;
            st.set(i, Node(ch - 'a'));
        }
        else
        {
            int l, r;
            cin >> l >> r, l--;
            auto freq = st.prod(l, r).cnt;
            cout << count_if(begin(freq), end(freq), [](int x) { return x != 0; }) << endl;
        }
    }
    return 0;
}

Competitive Programming Solutions