Competitive Programming Solutions

abc157_d - Friend Suggestions

18 Dec 2020 — Tags: dsu,graphs — URL

Let’s solve first a simpler version of the problem, where there are no blocking relations.

Let’s build a friendship graph.

Note for a given person $i$, every person in the connected component that is not a direct friend or $i$ itself is a friend candidate.

So, the answer is computed like:

\[ans[i] = | C_i | - | F_i | - 1\]

Where, $C_i$ is the connected component where $i$ lies and $F_i$ the friendships $i$ has.

In the real problem, however, the friendship component where $i$ is might have blocked people. To handle this, decrease by 1 for each blocked person that is in the same connected component. This can be efficiently done with a Disjoint Set Union structure.

Time complexity: $O((n + k) \alpha(n))$

Memory complexity: $O(n + m + n + k)$

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, k;
    cin >> n >> m >> k;
    atcoder::dsu d(n);
    vector<vi> blocked(n, vi());
    vector<vi> friends(n, vi());
    for (int i = 0; i < m; ++i)
    {
        int a, b;
        cin >> a >> b, a--, b--;
        d.merge(a, b);
        friends[a].push_back(b);
        friends[b].push_back(a);
    }
    for (int i = 0; i < k; ++i)
    {
        int c, d;
        cin >> c >> d, c--, d--;
        blocked[c].push_back(d);
        blocked[d].push_back(c);
    }
    vi ans(n, 0);
    for (int i = 0; i < n; ++i)
    {
        ans[i] = d.size(i) - (int)(friends[i]).size() - 1;
        for (auto j : blocked[i])
            ans[i] -= d.same(i, j);
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

abc157_c - Guess The Number

18 Dec 2020 — Tags: implementation,greedy — URL

Implement statement and handle edge cases. Fill every unknown space with a $0$ if it’s not the first digit ($1$ in that case).

Time complexity: $O(m + 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;
    vi s(n, -1);
    bool flag = true;
    while (m--)
    {
        int i, c;
        cin >> i >> c, i--;
        if (s[i] != -1 and s[i] != c)
            flag = false;
        if (i == 0 and c == 0 and n != 1)
            flag = false;
        s[i] = c;
    }
    if (flag)
    {
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == -1)
                s[i] = (i == 0 and n != 1);
            cout << s[i];
        }
        cout << endl;
    }
    else
    {
        cout << -1 << endl;
    }
    return 0;
}

abc157_b - Bingo

18 Dec 2020 — Tags: implementation,easy — URL

Check horizontally, vertically and in both diagonals.

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>;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    array<array<int, 3>, 3> bingo;
    for (auto &row : bingo)
        for (auto &val : row)
            cin >> val;
    int n;
    cin >> n;
    while (n--)
    {
        int bi;
        cin >> bi;
        for (auto &row : bingo)
            for (auto &val : row)
                if (val == bi)
                    val = 0;
    }
    vi ver_cnt(3, 0), hor_cnt(3, 0), diag_cnt(2, 0);
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            if (bingo[i][j] == 0)
                ver_cnt[j]++, hor_cnt[i]++;
    for (int i = 0; i < 3; ++i)
    {
        if (bingo[i][i] == 0)
            diag_cnt[0]++;
        if (bingo[i][3 - i - 1] == 0)
            diag_cnt[1]++;
    }
    bool ans = any_of(begin(ver_cnt), end(ver_cnt), [](int cnt) { return cnt == 3; }) |
               any_of(begin(hor_cnt), end(hor_cnt), [](int cnt) { return cnt == 3; }) |
               any_of(begin(diag_cnt), end(diag_cnt), [](int cnt) { return cnt == 3; });
    cout << (ans ? "Yes" : "No") << endl;
    return 0;
}

abc157_a - Duplex Printing

18 Dec 2020 — Tags: easy — URL

You need $\frac{(n + 1)}{2}$ pages.

Time complexity: $O(1)$

Memory complexity: $O(1)$

Click to show code.

 

using namespace std;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    cout << (n + 1) / 2 << endl;
    return 0;
}

1463C - Busy Robot

17 Dec 2020 — Tags: implementation — URL

Compute the position $y_i$ of the robot at time $t_i$. Then, check if for each $i$, $x_i$ lies in the range $y_i, y_{i + 1}$.

Time complexity: $O(n)$

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
int solve(vector<pll> tx)
{
    tx.emplace_back(1e13, 0);
    int ans = 0, n = (int)(tx).size();
    ll ts, xs, xe, te;
    ts = xs = xe = te = 0;
    vector<ll> y(n);
    for (int i = 0; i < n; ++i)
    {
        auto [ti, xi] = tx[i];
        y[i] = xs + (xe == xs ? 0 : (xe > xs ? 1 : -1)) * (min(ti, te) - ts);
        if (te <= ti)
        {
            ts = ti;
            xs = xe;
            te = ts + abs(xi - xs);
            xe = xi;
        }
    }
    auto inside = [](ll x, ll l, ll r) -> bool {
        if (l > r)
            swap(l, r);
        return l <= x and x <= r;
    };
    for (int i = 0; i < n - 1; ++i)
        ans += inside(tx[i].second, y[i], y[i + 1]);
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<pll> tx(n);
        for (auto &[t, x] : tx)
            cin >> t >> x;
        cout << solve(tx) << endl;
    }
    return 0;
}

1463B - Find The Array

17 Dec 2020 — Tags: math,observation — URL

Idea: for each $a_i$, let $b_i$ be the biggest power of $2$ less than or equal to $a_i$.

So, if $b_i = 2^k$, then $2^k \leq a_i \leq 2^{k + 1}$. This tells us that the difference between $a_i$ and $b_i$ is at most $b_i$ (remember that the length of the range $2^k, 2^{k + 1}$ is $2^k$).

Equivalently, $\frac{a_i}{2} \leq b_i \leq a_i$, which tells us that:

\[a_i - b_i \leq \frac{a_i}{2}\]

Therefore, by picking $b_i$’s with the following strategy, the sum of differences will be at most $\frac{S}{2}$, begin $S$ the total sum of $a_i$’s.

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 <typename InputIt,
          typename T = typename std::iterator_traits<InputIt>::value_type>
void write(InputIt first, InputIt last, const char *delim = "\n")
{
    copy(first, last, std::ostream_iterator<T>(std::cout, delim));
}
int prevpow2(int n)
{
    int ans = 1;
    while (ans <= n)
        ans <<= 1;
    return (ans >>= 1);
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi b(n, 0);
        for (auto &bi : b)
        {
            int ai;
            cin >> ai;
            bi = prevpow2(ai);
        }
        write(begin(b), end(b), " "), cout << endl;
    }
    return 0;
}

1463A - Dungeon

17 Dec 2020 — Tags: math,easy — URL

Note that the total health of enemies has to be a multiple of 9 (6 + 3), if you want to pass the dungeon beautifully.

In such case, the total amount of enhance shots done will be $x = \frac{s}{9}$, where $s$ denotes the total health of enemies.

Note that the actual amount of enhanced shots possible is bounded by the minimum health of all monsters (every enhanced shot forces us to reduce all monster’s health by 1). So, if $x \leq \min(a, b, c)$, there’s always a way to reduce the excess health with normal shots (given our previous assumption that $s$ is a multiple of $9$).

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 solve(int a, int b, int c)
{
    int total = a + b + c;
    if (total % 9)
        return false;
    int shots = total / 9;
    return min({a, b, c}) >= shots;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        cout << (solve(a, b, c) ? "YES" : "NO") << endl;
    }
    return 0;
}

1462F - The Tresure Of The Segments

15 Dec 2020 — Tags: sorting,brute_force — URL

For each range $(l, r)$ present in the array, see how many ranges wouldn’t be covered and keep the one that yields the minimum answer.

To compute $ans_{l, r}$, note that we only need to know $ans_l$ and $ans_r$:

\[ans_l = \text{#right endings that are less than } l\] \[ans_r = \text{#left endings that are greater than } r\]

We can solve those queries in $O(\log{n})$ each with two arrays:

  1. $sorted_l$: Array sorted by left borders.
  2. $sorted_r$: Array sorted by right borders.

For example, for a given range $l, r$ to compute $ans_l$ we only need to binary search (on $sorted_r$) the first range whose $r$ is less than $l$. The answer is the number of elements that precede it. Pretty much the same thing for $ans_r$.

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 <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
int solve(vector<ii> &a)
{
    int n = (int)(a).size();
    vi lb(n), rb(n);
    for (int i = 0; i < n; ++i)
        lb[i] = a[i].first, rb[i] = a[i].second;
    sort(begin(lb), end(lb)), sort(begin(rb), end(rb));
    int ans = 1e9 + 7;
    for (auto [l, r] : a)
    {
        int ansl = distance(begin(rb), lower_bound(begin(rb), end(rb), l)),
            ansr = distance(upper_bound(begin(lb), end(lb), r), end(lb));
        ans = min(ans, ansl + ansr);
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<ii> a(n);
        for (auto &[l, r] : a)
            cin >> l >> r;
        cout << solve(a) << endl;
    }
    return 0;
}

1462E2 - Close Tuples

15 Dec 2020 — Tags: sorting,combinatorics,binary_search — URL

Assume a $a$ is sorted non-decreasingly.

To count all the sequences ($a_{i_1}, a_{i_2}, …, a_{i_m}$, assume $a_{i_j} \leq a_{i_{j + 1}}$) that satisfy the given condition:

  1. Fix the maximum value, $a_{i_m}$.
  2. Find the minimum $a_{i_1}$ such that the condition ($a_{i_m} - a_{i_1} \leq k$) holds.
  3. Compute the number of ways to pick $m-1$ elements from $i_m - i_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>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename T1, typename T2>
T1 binpow(T1 base, T2 exp)
{
    T1 ans = 1;
    while (exp > 0)
    {
        if (exp & 1)
            ans *= base;
        base *= base;
        exp >>= 1;
    }
    return ans;
}
template <int M>
class ModInt
{
    using ll = long long;
    using mint = ModInt<M>;
    ll x;
  public:
    static const int MOD = M;
    inline static std::vector<mint> inv{};
    ModInt(ll x) : x(x) {}
    ModInt() : x(0) {}
    ModInt(mint const &y) : x(y.v()) {}
    explicit operator ll() const { return v(); }
    ll v(void) const { return (this->x + M) % M; }
    mint & operator=(mint const &y)
    {
        this->x = y.v();
        return *this;
    }
    mint &operator=(ll const &y) { return this->operator=(mint(y)); }
    mint &operator+=(mint const &y) { return this->operator=(operator+(y)); }
    mint &operator-=(mint const &y) { return this->operator=(operator-(y)); }
    mint &operator*=(mint const &y) { return this->operator=(operator*(y)); }
    mint operator+(mint const &y) const { return (v() + y.v()) % M; }
    mint operator+(ll const &y) const { return this->operator+(mint(y)); }
    mint operator-(mint const &y) const { return (v() - y.v()) % M; }
    mint operator-(ll const &y) const { return this->operator-(mint(y)); }
    mint operator*(mint const &y) const { return (v() * y.v()) % M; }
    mint operator*(ll const &y) const { return this->operator*(mint(y)); }
    mint operator/(mint const &y) const { return this->operator*(y.inverse()); }
    static void precompute_inverses(int len)
    {
        (void)0;
        int len0 = inv.size();
        inv.resize(std::max(int(inv.size()), len), 0);
        if (len0 == 0)
            inv[1] = 1, len0 = 2;
        for (int i = len0; i < len; ++i)
            inv[i] = MOD - ll(inv[MOD % i] * (MOD / i));
    }
    mint inverse(void) const { return binpow(*this, MOD - 2); }
    static mint inverse(ll x)
    {
        (void)0;
        if (x < ll(inv.size()))
            return inv[x];
        return binpow(mint(x), MOD - 2);
    }
};
template <int MOD>
std::vector<ModInt<MOD>> factorials(int len)
{
    (void)0;
    std::vector<ModInt<MOD>> ans(len);
    ans[0] = 1;
    for (int i = 1; i < len; i++)
        ans[i] = ans[i - 1] * i;
    return ans;
}
template <int MOD>
std::vector<ModInt<MOD>> inverse_factorials(int len)
{
    using mint = ModInt<MOD>;
    (void)0;
    mint::precompute_inverses(len);
    std::vector<mint> inv_fact(len);
    inv_fact[0] = 1;
    for (int i = 1; i < len; i++)
        inv_fact[i] = inv_fact[i - 1] * mint::inverse(i);
    return inv_fact;
}
template <int NMAX, int MOD>
struct Combinations
{
    using mint = ModInt<MOD>;
    std::vector<mint> fact, inv_fact;
    Combinations(void)
    {
        fact = factorials<MOD>(NMAX + 1);
        inv_fact = inverse_factorials<MOD>(NMAX + 1);
    }
    mint C(int n, int k) const
    {
        (void)0;
        if (k > n or k < 0)
            return 0;
        return fact[n] * inv_fact[k] * inv_fact[n - k];
    }
    mint factorial(int n)
    {
        (void)0;
        return fact[n];
    }
    mint inverse_factorial(int n)
    {
        (void)0;
        return inv_fact[n];
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int const MOD = 1e9 + 7;
    int const NMAX = 2e5 + 11;
    using mint = ModInt<MOD>;
    Combinations<NMAX, MOD> comb;
    int t;
    cin >> t;
    while (t--)
    {
        int n, m, k;
        cin >> n >> m >> k;
        vi a(n);
        read_n(begin(a), n);
        sort(begin(a), end(a));
        mint ans = 0;
        for (int i = 0; i < n; ++i)
        {
            int j = distance(begin(a), lower_bound(begin(a), end(a), a[i] - k));
            ans += comb.C(i - j, m - 1);
        }
        cout << ll(ans) << endl;
    }
    return 0;
}

1462E1 - Close Tuples

15 Dec 2020 — Tags: sorting,combinatorics,binary_search — URL

See post for E2, this is just a special case of it.

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 <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
ll C2(ll n)
{
    if (n < 2)
        return 0;
    return (n * (n - 1)) / 2;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi a(n);
        read_n(begin(a), n);
        sort(begin(a), end(a));
        ll ans = 0;
        for (int i = 0; i < n; ++i)
        {
            int j = distance(begin(a), lower_bound(begin(a), end(a), a[i] - 2));
            ans += C2(i - j);
        }
        cout << ans << endl;
    }
    return 0;
}