1462D - Add To Neighbour And Remove

15 Dec 2020 — Tags: brute_force — URL

Let’s say that $b$ is an array reachable from $a$ by applying the described operation such that $b_i = x$ for all $1 \leq i \leq k$, where $k \leq n$. Note that $x$ is completely defined by $k$, so call it $x_k$:

\[x_k = \frac{\sum_{i = 1}^{n} a_i}{k}\]

The problem reduces to finding the biggest $k$ possible, and that can be found by testing all possible $1 \leq k \leq n$ in descending order, and returning the first match. Testing if $x_k$ is feasible can be done in a simple $O(n)$ check.

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>;
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);
}
bool test(const vi &a, ll x)
{
    int n = (int)(a).size();
    ll cur = 0;
    for (int i = 0; i < n; ++i)
    {
        if (cur + a[i] < x)
            cur += a[i];
        else if (cur + a[i] > x)
            return false;
        else
            cur = 0;
    }
    return cur == 0;
}
int solve(const vi &a)
{
    int n = (int)(a).size();
    ll sum = accumulate(begin(a), end(a), 0LL);
    for (int i = n; i > 1; --i)
        if (sum % i == 0 and test(a, sum / i))
            return n - i;
    return n - 1;
}
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);
        cout << solve(a) << endl;
    }
    return 0;
}

1462C - Unique Number

15 Dec 2020 — Tags: greedy — URL

First note that the maximum sum of digits that can be made is $45$, we’ll assume that $x$ is less than that from now on. Note that with the previous assumption it is always possible to sum $x$.

To build our desired number $y$, our greedy strategy will then be to fit the biggest possible digits to the least significant digits of $y$. This will reduce the total amount of digits used and at the same time reserve the smaller digits for the most significant digits of $y$.

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>;
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 InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int solve(int x)
{
    if (x > 45)
        return -1;
    int ans = 0, n = 1;
    for (int d = 9; d >= 1; --d)
    {
        if (x - d >= 0)
        {
            x -= d;
            ans += n * d;
            n *= 10;
        }
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int x;
        cin >> x;
        cout << solve(x) << endl;
    }
    return 0;
}

1462B - Last Years Substring

15 Dec 2020 — Tags: implementation,strings — URL

There are three successful cases for a string $s$:

$s$ = 2020
2020 is a prefix of $s$
2020 is a suffix of $s$

To see if $s$ matches one of these cases, compute the longest common prefix between $s$ and 2020 and the longest common suffix between $s$ and 2020. If the sum of those answers is greater or equal than $4$, then it means that I can combine them together (removing the excess in the middle) and get $2020$.

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>;
bool solve(string s)
{
    int n = (int)(s).size();
    string sub = "2020";
    if (s == sub)
        return true;
    int pre = 0, suf = 0;
    while (pre < 4 and s[pre] == sub[pre])
        ++pre;
    while (suf < 4 and s[n - suf - 1] == sub[4 - suf - 1])
        ++suf;
    return pre + suf >= 4;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        string s;
        cin >> n >> s;
        cout << (solve(s) ? "YES" : "NO") << endl;
    }
    return 0;
}

1462A - Favorite Sequence

15 Dec 2020 — Tags: easy,implementation — URL

Reverse the operation.

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);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vi a(n), ans(n);
        read_n(begin(a), n);
        int i = 0, l = 0, r = n - 1;
        while (l < r)
        {
            ans[i++] = a[l++];
            ans[i++] = a[r--];
        }
        if (l == r)
            ans[i] = a[l];
        write(begin(ans), end(ans), " "), cout << endl;
    }
    return 0;
}

abc185_f - Range Xor Query

13 Dec 2020 — Tags: segment_tree,data_structures — URL

Segment Tree with xor as operation.

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>;
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 <class T>
struct SegmentTree
{
    using BinaryOperator = std::function<T(T, T)>;
    T id;
    BinaryOperator op;
    int n;
    std::vector<T> t;
    template <class InputIterator>
    explicit SegmentTree(InputIterator first,
                         InputIterator last,
                         T id,
                         BinaryOperator op)
        : id(id), op(op), n(distance(first, last))
    {
        t.resize(4 * n);
        build(first, last, 1, 0, n - 1);
    }
    template <class InputIterator>
    void build(InputIterator first, InputIterator last, int v, int tl, int tr)
    {
        if (tl == tr)
            t[v] = T(*(first + tl));
        else
        {
            int tm = (tl + tr) / 2;
            build(first, last, v << 1, tl, tm);
            build(first, last, (v << 1) + 1, tm + 1, tr);
            t[v] = op(t[v << 1], t[(v << 1) + 1]);
        }
    }
    T query(int l, int r) const { return query(1, 0, n - 1, l, r); }
    T query(int v, int tl, int tr, int l, int r) const
    {
        if (l > r)
            return id;
        if (l == tl and r == tr)
            return t[v];
        int tm = (tl + tr) >> 1;
        return op(query(v << 1, tl, tm, l, std::min(r, tm)),
                  query((v << 1) + 1, tm + 1, tr, std::max(l, tm + 1), r));
    }
    void update(int pos, T val) { return update(1, 0, n - 1, pos, val); }
    void update(int v, int tl, int tr, int pos, T val)
    {
        if (tl == tr)
            t[v] = val;
        else
        {
            int tm = (tl + tr) >> 1;
            if (pos <= tm)
                update(v << 1, tl, tm, pos, val);
            else
                update((v << 1) + 1, tm + 1, tr, pos, val);
            t[v] = op(t[v << 1], t[(v << 1) + 1]);
        }
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    vi a(n);
    read_n(begin(a), n);
    SegmentTree<int> st(begin(a), end(a), 0, bit_xor<int>());
    while (q--)
    {
        int t, x, y;
        cin >> t >> x >> y;
        if (t == 1)
        {
            x--;
            int new_val = st.query(x, x) ^ y;
            st.update(x, new_val);
        }
        else
        {
            x--, y--;
            cout << st.query(x, y) << endl;
        }
    }
    return 0;
}

abc185_d - Stamp

13 Dec 2020 — Tags: implementation,greedy — URL

Assume that array $A$ is sorted.

Compute in $O(n)$ the length of all the white stripes (consecutive blocks of white squares). Note that the optimal answer is taking a stamp with size equals to the minimum length of such stripes (if bigger, then it wouldn’t fit). The answer would then be:

\[ans = \sum_{s \in S} ceil(s, k)\]

Where $S$ is the set of stripe lengths and $k$ the minimum element of such set.

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);
}
inline ll ceil(ll a, ll b) { return (a + b - 1) / b; }
ll solve(vector<ll> a)
{
    sort(begin(a), end(a));
    ll prev = 0;
    vector<ll> stripes;
    for (auto ai : a)
    {
        if (ai - prev - 1 > 0)
            stripes.push_back(ai - prev - 1);
        prev = ai;
    }
    if (stripes.empty())
        return 0;
    ll k = *min_element(begin(stripes), end(stripes)), ans = 0;
    for (auto st : stripes)
        ans += ceil(st, k);
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    if (m != 0)
    {
        vector<ll> a(m + 1);
        read_n(begin(a), m);
        a[m] = n + 1;
        cout << solve(a) << endl;
    }
    else
        cout << 1 << endl;
    return 0;
}

abc185_c - Duodecim Ferra

13 Dec 2020 — Tags: combinatorics,dp — URL

Compute the number of ways to cut a log of width $l$, $C(l - 1, 11)$.

Time complexity: $O(l^2)$

Memory complexity: $O(l^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 l;
    cin >> l;
    vector<vector<ll>> C(l + 1, vector<ll>(l + 1, 0));
    C[0][0] = 1;
    for (int n = 1; n <= l; ++n)
    {
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; ++k)
            C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
    }
    cout << C[l - 1][11] << endl;
    return 0;
}

abc185_b - Smartphone Addiction

13 Dec 2020 — Tags: implementation — URL

Simulate the battery through time.

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>;
bool solve(ll n, ll t, vector<ii> events)
{
    ll ct = 0, battery = n;
    events.emplace_back(t, t);
    for (auto [a, b] : events)
    {
        battery = max(0LL, battery - (a - ct));
        if (battery == 0)
            return false;
        battery = min(n, battery + b - a);
        ct = b;
    }
    return true;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m, t;
    cin >> n >> m >> t;
    vector<ii> events(m);
    for (auto &[a, b] : events)
        cin >> a >> b;
    cout << (solve(n, t, events) ? "Yes" : "No") << endl;
    return 0;
}

abc185_a - Abc Preparation

13 Dec 2020 — Tags: easy — URL

The answer is the minimum of $a_1$, $a_2$, $a_3$ and $a_4$.

Time complexity: $O(1)$

Memory complexity: $O(1)$

Click to show code.

using namespace std;
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);
    array<int, 4> a;
    read_n(begin(a), 4);
    cout << *min_element(begin(a), end(a)) << endl;
    return 0;
}

abc176_c - Step

12 Dec 2020 — Tags: implementation,greedy — URL

Define new array $B$ such that it’s elements are defined the following way:

Base case $i = 1$: $b_1 = a_1$

For $1 < i \leq n$:

\[b_i = max(b_{i - 1}, a_i)\]

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);
}
ll solve(vector<ll> a)
{
    ll ans = 0, prev = a[0];
    for (auto &ai : a)
    {
        if (ai < prev)
        {
            ans += (prev - ai);
            ai = prev;
        }
        prev = ai;
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<ll> a(n);
    read_n(begin(a), n);
    cout << solve(a) << endl;
    return 0;
}

Older Newer

Competitive Programming Solutions