abc176_b - Multiple Of 9

12 Dec 2020 — Tags: easy — URL

Check if the sum of digits is multiple of $9$.

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;
    cin >> n;
    ll sum =
        accumulate(begin(n), end(n), 0LL, [](ll acc, char c) { return acc + (c - '0'); });
    cout << (sum % 9 == 0 ? "Yes" : "No") << endl;
    return 0;
}

abc176_a - Takoyaki

12 Dec 2020 — Tags: easy — URL

The answer is: $t \times ceil(\frac{n}{x})$

Time complexity: $O(1)$

Memory complexity: $O(1)$

Click to show code.

using namespace std;
int ceil(int a, int b) { return (a + b - 1) / b; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, x, t;
    cin >> n >> x >> t;
    cout << t * ceil(n, x) << endl;
    return 0;
}

abc184_d - Increment Of Coins

11 Dec 2020 — Tags: dp,expected_value,probability — URL

I’m kinda :brick: at Probability, so here’s the Editorial.

Time complexity: $O(n^3)$

Memory complexity: $O(n^3)$

Click to show code.

using namespace std;
int const NMAX = 100 + 1;
double dp[NMAX][NMAX][NMAX];
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int a, b, c;
    cin >> a >> b >> c;
    for (int x = 99; x >= 0; --x)
    {
        for (int y = 99; y >= 0; --y)
        {
            for (int z = 99; z >= 0; --z)
            {
                double d = x + y + z;
                dp[x][y][z] = x / d * (dp[x + 1][y][z] + 1) +
                              y / d * (dp[x][y + 1][z] + 1) +
                              z / d * (dp[x][y][z + 1] + 1);
            }
        }
    }
    cout << setprecision(12) << fixed << dp[a][b][c] << endl;
    return 0;
}

abc177_d - Friends

11 Dec 2020 — Tags: dsu,data_structures — URL

Note that the the transitive and symmmetric properties of friendship described on the problem statement imply that we’ll have fully connected hubs of people that are mutually friends.

The only way to divide the people in groups where no two people are friends would be to place all the members of a friendship group in different answer groups.

Note that the upper bound on groups created would be equal to the size of the biggest friendship hub. Use a Disjoint Set Structure to maintain such hubs efficiently.

Time complexity: $O(m \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 UnionFind
{
    int n;
    vi parent, sz;
    UnionFind(int n) : n(n)
    {
        parent.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; ++i)
            make_set(i);
    }
    void make_set(int v)
    {
        parent[v] = v;
        sz[v] = 1;
    }
    int find_set(int v)
    {
        if (v == parent[v])
            return v;
        return (parent[v] = find_set(parent[v]));
    }
    void union_sets(int a, int b)
    {
        a = find_set(a);
        b = find_set(b);
        if (a != b)
        {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }
    int biggest_component(void)
    {
        int ans = 0;
        for (int i = 0; i < n; ++i)
            if (i == find_set(i))
                ans = max(ans, sz[i]);
        return ans;
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    UnionFind dsu(n);
    while (m--)
    {
        int a, b;
        cin >> a >> b, a--, b--;
        dsu.union_sets(a, b);
    }
    cout << dsu.biggest_component() << endl;
    return 0;
}

abc177_c - Sum Of Product Of Pairs

11 Dec 2020 — Tags: math — URL

By doing some algebra on the expression you will note that the contribution of $a_i$ is:

\[a_i \times \sum_{j = i + 1}^{n} 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>;
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 main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    ll const MOD = 1e9 + 7;
    int n;
    cin >> n;
    vi a(n);
    read_n(begin(a), n);
    ll sfxsum = 0, ans = 0;
    for (int i = n - 1; i >= 0; --i)
    {
        ans += a[i] * sfxsum;
        sfxsum += a[i];
        ans %= MOD, sfxsum %= MOD;
    }
    cout << ans << endl;
    return 0;
}

abc177_b - Substring

11 Dec 2020 — Tags: brute_force — URL

Try all possible positions for string $T$ and keep the minimum number of differences for all of them.

Time complexity: $O(n^2)$

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 s, t;
    cin >> s >> t;
    int n = (int)(s).size(), m = (int)(t).size(), ans = m;
    for (int i = 0; i <= n - m; ++i)
    {
        int cur = m;
        for (int j = 0; j < m; ++j)
            if (t[j] == s[i + j])
                cur--;
        ans = min(ans, cur);
    }
    cout << ans << endl;
    return 0;
}

abc177_a - Dont Be Late

11 Dec 2020 — Tags: easy — URL

To arrive in time, this has to be true: $T >= \frac{D}{S}$

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 d, t, s;
    cin >> d >> t >> s;
    cout << (((d + s - 1) / s <= t) ? "Yes" : "No") << endl;
    return 0;
}

abc145_d - Knight

11 Dec 2020 — Tags: counting,math — URL

This blog helped me understand the Editorial.

Time complexity: $O(n + m)$

Memory complexity: $O(n + m)$

Click to show code.

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <int M, typename T = long long>
class NumMod
{
    static_assert(std::is_integral<T>::value, "Integral required.");
    using NM = NumMod<M, T>;
    T x;
  public:
    static const int MOD = M;
    NumMod(T x) : x(x) {}
    NumMod() : x(0) {}
    NumMod(NM const &y) : x(y.v()) {}
    explicit operator T() const { return x; }
    T v(void) const { return (this->x + M) % M; }
    NM & operator=(NM const &y)
    {
        this->x = y.v();
        return *this;
    }
    NM &operator=(T const &y) { return this->operator=(NM(y)); }
    NM &operator+=(NM const &y) { return this->operator=(operator+(y)); }
    NM &operator-=(NM const &y) { return this->operator=(operator-(y)); }
    NM &operator*=(NM const &y) { return this->operator=(operator*(y)); }
    NM operator+(NM const &y) const { return (v() + y.v()) % M; }
    NM operator+(T const &y) const { return this->operator+(NM(y)); }
    NM operator-(NM const &y) const { return (v() - y.v()) % M; }
    NM operator-(T const &y) const { return this->operator-(NM(y)); }
    NM operator*(NM const &y) const { return (v() * y.v()) % M; }
    NM operator*(T const &y) const { return this->operator*(NM(y)); }
    NM operator/(NM const &y) const { return this->operator*(inverse(y)); }
};
ll const MOD = 1e9 + 7;
int const NMAX = 1e6 + 11;
using NM = NumMod<MOD, ll>;
NM fact[NMAX], inv[NMAX], inv_fact[NMAX];
void precompute_fact(void)
{
    inv[1] = fact[0] = inv_fact[0] = 1;
    for (int i = 1; i < NMAX; ++i)
    {
        if (i > 1)
            inv[i] = MOD - ll(inv[MOD % i] * (MOD / i));
        fact[i] = fact[i - 1] * i;
        inv_fact[i] = inv_fact[i - 1] * inv[i];
    }
}
template <typename T>
T binpow(T a, ll b)
{
    T ans = 1;
    while (b > 0)
    {
        if (b & 1)
            ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}
NM inverse(NM const &y) { return binpow(y, y.MOD - 2); }
ll C(int n, int k)
{
    if (k > n or k < 0)
        return 0;
    return ll(fact[n] * inv_fact[n - k] * inv_fact[k]);
}
int solve(int x, int y)
{
    if ((x + y) % 3 != 0)
        return 0;
    precompute_fact();
    int n = (2 * x - y) / 3, m = (2 * y - x) / 3;
    return C(n + m, n);
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int x, y;
    cin >> x >> y;
    cout << solve(x, y) << endl;
    return 0;
}

1461D - Divide And Summarize

11 Dec 2020 — Tags: sorting,divide_and_conquer — URL

Note that for a given array $A$, you can produce all possible subarray sums by performing splits recursively until it’s no longer possible.

Also, note that the order of the elements does not matter, because splitting and getting the sum of a subarray are order invariant.

Algorithm:

Sort array.
Precompute prefix sums of sorted array (to be able to do range sums).
Perform splitting recursively, and for each [l, r], add its sum to the answer set and find the new middle by binary searching the midpoint.
For each query, binary search on the answer set.

Note that the recurrence tree has on average at most $O(\log{a_{max}})$ height, because the maximum difference between two elements is $10^9$ and that halves on each split. Credits to Senhor nitor for the complexity analysis.

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

Memory complexity: $O(n)$

Click to show code.

using namespace std;
using ll = long long;
int const NMAX = 1e5 + 11;
ll n, a[NMAX], pa[NMAX];
set<ll> answers;
ll sum(int l, int r) { return pa[r] - (l == 0 ? 0 : pa[l - 1]); }
void solve(int l, int r)
{
    if (r < l or l < 0 or r >= n)
        return;
    int mx = a[r], mn = a[l], md = (mx + mn) / 2;
    int mdix = distance(a, upper_bound(a + l, a + r + 1, md));
    answers.insert(sum(l, r));
    if (mdix - 1 != r)
        solve(l, mdix - 1);
    if (mdix != l)
        solve(mdix, r);
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        answers.clear();
        int q;
        cin >> n >> q;
        for (int i = 0; i < n; ++i)
            cin >> a[i];
        sort(a, a + n);
        partial_sum(a, a + n, pa);
        solve(0, n - 1);
        while (q--)
        {
            ll s;
            cin >> s;
            cout << (answers.find(s) != end(answers) ? "Yes" : "No") << endl;
        }
    }
    return 0;
}

1461C - Random Events

11 Dec 2020 — Tags: observation,probability — URL

Key observation: we only care about the last position that is unsorted.

The reasoning behind this is that the numbers that go after that are already sorted and the numbers that come before will always have more or equal probability of getting sorted.

So, for such number $a_{last}$, the probability of staying unsorted is:

\[(1 - p_{i_0}) (1 - p_{i_0}) ... (1 - p_{i_k})\]

for all $i_j$’s such that $last \leq r_{i_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>;
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 main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        vi a(n);
        read_n(begin(a), n);
        int last = n;
        while (last >= 1 and a[last - 1] == last)
            --last;
        double P_unsorted = (last == 0 ? 0.0 : 1.0);
        while (m--)
        {
            int r;
            double p;
            cin >> r >> p;
            if (r >= last)
                P_unsorted *= (double(1) - p);
        }
        cout << setprecision(12) << fixed << double(1) - P_unsorted << endl;
    }
    return 0;
}

Older Newer

Competitive Programming Solutions