Competitive Programming Solutions

1475E - Advertising Agency

25 Jan 2021 — Tags: counting,sorting — URL

Comment

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>;
using mint = atcoder::modint1000000007;
ll C(int n, int k)
{
    mint up = 1, down = 1;
    for (int i = 0; i < k; ++i)
    {
        up *= n - i;
        down *= k - i;
    }
    return (up / down).val();
}
ll solve(vi a, int k)
{
    map<int, int, greater<int>> freq;
    for (auto ai : a)
        freq[ai]++;
    for (auto [x, cnt] : freq)
    {
        if (cnt < k)
            k -= cnt;
        else
            return C(cnt, k);
    }
    return 1;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;
        cin >> n >> k;
        vi a(n);
        for (auto &ai : a)
            cin >> ai;
        cout << solve(a, k) << endl;
    }
    return 0;
}

1475D - Cleaning The Phone

25 Jan 2021 — Tags: binary_search,sortings — URL

Comment

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 solve(vi a, vi b, int m)
{
    int n = (int)(a).size();
    vector<ll> acc[2];
    acc[0] = {0}, acc[1] = {0};
    for (int i = 0; i < n; ++i)
        acc[b[i] - 1].push_back(a[i]);
    for (int i = 0; i < 2; ++i)
    {
        auto start = begin(acc[i]) + 1;
        sort(start, end(acc[i]), greater<int>());
        partial_sum(start, end(acc[i]), start);
    }
    ll const INF = 1e15;
    ll ans = INF;
    int n1 = acc[0].size();
    for (int i = 0; i < n1; ++i)
    {
        auto it = lower_bound(begin(acc[1]), end(acc[1]), max(0LL, m - acc[0][i]));
        if (it != acc[1].end())
        {
            int j = distance(begin(acc[1]), it);
            ans = min(ans, i + 2LL * j);
        }
    }
    return ans == INF ? -1 : ans;
}
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), b(n);
        for (auto &ai : a)
            cin >> ai;
        for (auto &bi : b)
            cin >> bi;
        cout << solve(a, b, m) << endl;
    }
    return 0;
}

abc189_d - Logical Expression

23 Jan 2021 — Tags: dp — URL

Let’s define the following dps:

$dp_1(i)$ : Number of ways for the expression $x_0,…x_i$ to be true with the given logical operators up to the $i$th.

$dp_0(i)$ : Number of ways for the expression $x_0,…x_i$ to be false with the given logical operators up to the $i$th.

In $dp_1$:

For the case where the $i$th logical operator, $op$, $x_{i-1} op x_i$, is an AND, we need the expression $x_0,…x_{i-1}$ to yield true.

For the case where the $i$th logical operator, $op$, $x_{i-1} op x_i$, is an OR, the expression $x_0,…x_{i-1}$ can yield true (in which case $x_i$ can be either true or false) or false (in which case $x_i$ must be true).

One can similarly define $dp_0$.

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>;
using vll = vector<ll>;
ll solve(vi a)
{
    int n = (int)(a).size();
    vector<vll> dp(n + 1, vll(2, 0));
    dp[0][0] = dp[0][1] = 1;
    for (int i = 1; i <= n; ++i)
    {
        if (a[i - 1])
        {
            dp[i][1] = dp[i - 1][1];
            dp[i][0] = 2 * dp[i - 1][0] + dp[i - 1][1];
        }
        else
        {
            dp[i][1] = dp[i - 1][0] + 2 * dp[i - 1][1];
            dp[i][0] = dp[i - 1][0];
        }
    }
    return dp[n][1];
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &ai : a)
    {
        string s;
        cin >> s;
        ai = s == "AND";
    }
    cout << solve(a) << endl;
    return 0;
}

abc189_c - Mandaring Orange

23 Jan 2021 — Tags: greedy,segment_tree,binary_search,brute_force — URL

For each element $a_i$, find indexes $l$ and $r$, such that $l \leq i \leq r$ and $\min{a_l,…,a_i,…,a_r} = a_i$. The answer for such particular index would then be $a_i \times (r - l + 1)$.

There are several ways to do this, check Editorial for more info.

In my approach, I used a segment tree to handle minimum range queries and then used binary search on it to find both indexes. Check AtCoder’s SegmentTree’s docs and this problem for an idea of how min_left and max_right work.

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>;
using S = int;
int op(int a, int b) { return min(a, b); }
int e() { return 1e9; }
ll solve(vi a)
{
    int n = (int)(a).size();
    ll ans = 0;
    using RMQ = atcoder::segtree<S, op, e>;
    RMQ st(a);
    for (int i = 0; i < n; ++i)
    {
        int ai = a[i];
        auto f = [ai](S b) { return ai <= b; };
        int l = st.min_left(i, f);
        int r = st.max_right(i, f);
        ans = max(ans, a[i] * ll(r - l));
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi a(n);
    for (auto &ai : a)
        cin >> ai;
    cout << solve(a) << endl;
    return 0;
}

abc189_b - Alcoholic

23 Jan 2021 — Tags: implementation — URL

Linearly test if the $i$th liquor gets Takahashi drunk. To avoid precision errors, multiply $x$ by $100$ instead of dividing each percentage by $100$.

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 solve(vi v, vi p, ll x)
{
    int n = (int)(v).size();
    ll cur = 0;
    x *= 100;
    for (int i = 0; i < n; ++i)
    {
        cur += v[i] * p[i];
        if (cur > x)
            return i + 1;
    }
    return -1;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, x;
    cin >> n >> x;
    vi v(n), p(n);
    for (int i = 0; i < n; ++i)
        cin >> v[i] >> p[i];
    cout << solve(v, p, x);
    return 0;
}

abc189_a - Slot

23 Jan 2021 — Tags: easy,implementation — URL

Check if three values are equal.

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 s;
    cin >> s;
    cout << (s[0] == s[1] and s[1] == s[2] ? "Won" : "Lost") << endl;
    return 0;
}

abc182_c - To 3

23 Jan 2021 — Tags: implementation,math — URL

Observations:

  1. For a number to be divisible by $3$ the sum of its digits must be divisible by $3$.
  2. Removing two digits with the same remainder $r$ is equivalent to removing remainder $3 - r$ from the overall digit sum.

Say that a number $x$ has a digit sum equal to $s$ and $s$ has remainder $r$ when divided by $3$. Let’s handle some of the cases.

If $r$ is zero, then we’re done.

If there’s a digit with remainder $r$ in $x$, we remove it and we’re done.

If there are two digits remainder $3 - r$, we remove then and we’re done.

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 solve(vi a)
{
    int n = (int)(a).size();
    vi rem(3, 0);
    for (auto ai : a)
        rem[ai % 3]++;
    int sum = accumulate(begin(a), end(a), 0);
    if (sum % 3 == 0)
        return 0;
    if (n > 1 and rem[sum % 3])
        return 1;
    if (n > 2 and rem[3 - (sum % 3)] >= 2)
        return 2;
    return -1;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    string n;
    cin >> n;
    vi a(n.size());
    transform(begin(n), end(n), begin(a), [](char c) { return c - '0'; });
    cout << solve(a) << endl;
    return 0;
}

abc182_b - Almost Gcd

23 Jan 2021 — Tags: brute_force,number_theory,implementation — URL

Count number of elements divisible by $k$ for each $2 \geq k \geq a_{max}$.

Time complexity: $O(a_{max} \times 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 solve(vi a)
{
    int amax = *max_element(begin(a), end(a));
    ii ans = {0, 0};
    for (int k = 2; k <= amax; ++k)
    {
        int cur = count_if(begin(a), end(a), [k](int ai) { return ai % k == 0; });
        ans = max(ans, {cur, k});
    }
    return ans.second;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vi a(n);
    for (auto &ai : a)
        cin >> ai;
    cout << solve(a) << endl;
    return 0;
}

abc182_a - Twiblr

23 Jan 2021 — Tags: easy — URL

$2a + 100 - b$

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 a, b;
    cin >> a >> b;
    cout << 2 * a + 100 - b << endl;
    return 0;
}

842D - Vitya And Strange Lesson

22 Jan 2021 — Tags: trie,string — URL

Editorial.

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 T>
struct Trie
{
    int n, nmax;
    vector<vector<int>> t;
    vector<T> val;
    Trie(int N, int alphasz) : n(0), t(N, vector<int>(alphasz, 0)), val(N, T())
    {
    }
    void update(const vector<int> &a, function<void(T &)> f)
    {
        int cur = 0;
        for (int i = 0; i < (int)a.size(); ++i)
        {
            if (!t[cur][a[i]])
                t[cur][a[i]] = ++n;
            cur = t[cur][a[i]];
            f(val[cur]);
        }
    }
    void traverse(const vector<int> &a, function<void(T &, int)> f)
    {
        int cur = 0;
        for (int i = 0; i < (int)a.size(); ++i)
        {
            if (!t[cur][a[i]])
                return;
            f(val[t[cur][a[i]]], i);
            cur = t[cur][a[i]];
        }
    }
};
template <size_t N>
vector<int> bitvec(int x)
{
    vi a(N);
    for (int i = (int)N - 1; i >= 0; --i)
        a[i] = (x >> i) & 1;
    return a;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    int const MAXLEN = 20, ALPHA_SZ = 2;
    Trie<int> trie(1 << MAXLEN, ALPHA_SZ);
    auto f1 = [](int &a) { a++; };
    vector<bool> vis(3e5 + 11, false);
    for (int i = 0; i < n; ++i)
    {
        int ai;
        cin >> ai;
        if (!vis[ai])
        {
            auto a = bitvec<MAXLEN>(ai);
            reverse(begin(a), end(a));
            trie.update(a, f1);
            vis[ai] = true;
        }
    }
    int x = 0;
    while (m--)
    {
        int xi, ans = 0;
        cin >> xi;
        x ^= xi;
        auto a = bitvec<MAXLEN>(x);
        reverse(begin(a), end(a));
        auto f2 = [MAXLEN, &a, &ans](int &val, int i) {
            int j = MAXLEN - i - 1;
            if (val == (1 << j))
            {
                ans |= 1 << j;
                a[i] = 1 - a[i];
            }
        };
        trie.traverse(a, f2);
        cout << ans << endl;
    }
    return 0;
}