Competitive Programming Solutions

1461B - Find The Spruce

11 Dec 2020 — Tags: dp,brute_force — URL

Note that you can know what is the largest spruce that can be constructed with root $(r, c)$, by merging the spruces at $(r + 1, c - 1)$, $(r + 1, c)$ and $(r + 1,c + 1)$ and cutting the excess. With this idea in mind, define the following dp state:

\[dp(r, c) = 1 + min(dp(r + 1, c - 1), dp(r + 1, c), dp(r + 1, c + 1))\]

if $(r, c) == ‘*’$.

Time complexity: $O(n^2)$

Memory complexity: $O(n^2)$

Click to show code.

 

using namespace std;
using ll = long long;
int const NMAX = 500 + 11;
int n, m, board[NMAX][NMAX];
ll solve(void)
{
    ll ans = 0;
    for (int r = n; r >= 1; --r)
    {
        for (int c = m; c >= 1; --c)
        {
            if (board[r][c])
            {
                board[r][c] = 1 + min({board[r + 1][c - 1],
                                       board[r + 1][c],
                                       board[r + 1][c + 1]});
                ans += board[r][c];
            }
        }
    }
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        memset(board, 0, sizeof board);
        for (int r = 1; r <= n; ++r)
        {
            for (int c = 1; c <= m; ++c)
            {
                char ch;
                cin >> ch;
                board[r][c] = (ch == '*');
            }
        }
        cout << solve() << endl;
    }
    return 0;
}

1461A - String Generation

11 Dec 2020 — Tags: easy,constructive,greedy — URL

Stacking “abc” together, will have the following property: No character will have neighbors that are equal to each other or to itself.

All palindromes need at least its center to be this way, so constructing one is impossible.

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>;
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, k;
        cin >> n >> k;
        string ch = "abc";
        for (int i = 0; i < n; ++i)
            cout << ch[i % 3];
        cout << endl;
    }
    return 0;
}

arc102_a - Triangular Relationship

10 Dec 2020 — Tags: counting — URL

The key insight is to think about the remainders of $a, b, c$ when divided by $k$.

Trivially, picking $a, b, c$’s with remainder $0$ will yield multiples of $k$ when added. However, when $k$ is even, we may also count numbers with remainder $k / 2$.

Note that no other numbers will contribute to the answer.

Time complexity: $O(n)$

Memory complexity: $O(1)$

Click to show code.

 

using namespace std;
using ll = long long;
ll solve(int n, int k)
{
    auto ways = [](ll n) -> ll { return n * n * n; };
    ll mid = 0, zero = 0;
    for (int i = 1; i <= n; ++i)
    {
        mid += (k % 2 == 0 and i % k == (k / 2));
        zero += (i % k == 0);
    }
    return ways(zero) + ways(mid);
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    cout << solve(n, k) << endl;
    return 0;
}

abc163_d - Sum Of Large Numbers

10 Dec 2020 — Tags: math,counting — URL

I’m kinda lazy to explain this problem, so here’s the editorial

Anyhow, the key points are:

  • Fix the quantity of numbers to sample, $i$, $k \leq i \leq n + 1$.
  • Note that we can produce any number in between the minimum and maximum sum of $i$ numbers.
  • For each desired $i$ compute the size of the range described above.
  • Note that those ranges do not overlap.

Time complexity: $O(n)$

Memory complexity: $O(1)$

Click to show code.

 

using namespace std;
using ll = long long;
int const MOD = 1e9 + 7;
ll sq(ll n) { return (n * (n + 1)) / 2; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    ll ans = 0;
    for (int i = k; i <= n + 1; ++i)
    {
        ans += sq(n) - sq(n - i) - sq(i - 1) + 1;
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

nikkei2019_2_qual_b - Counting Of Trees

09 Dec 2020 — Tags: counting,constructive,dp — URL

Note that no tree can be made if our given array doesn’t fullfill the following properties:

  1. The distance of node $1$ to itself ($d_1$) is not $0$.
  2. There are exists a node $i \neq 1$ that has distance $d_i = 0$.
  3. There exists a distance $d_{missing} \leq d_i$ for some $d_i$, such that $d_{missing} \notin D$.

From now on we’ll assume otherwise.

The idea is to construct the answer by adding layers of nodes with the same distance to the root. We’ll compute the solution for a certain distance $i$ by counting all the ways in which we can place the nodes at distance $i$ on the nodes at distance $i-1$. For each current node we would have $cnt_{i-1}$ options, so in total there would be $cnt_{i-1}^{cnt_i}$ ways to construct one more layer of the tree.

A simple dp works:

\[dp(i) = dp(i - 1) \times cnt_{i - 1}^{cnt_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>;
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 const MOD = 998244353;
ll solve(vector<int> d)
{
    int n = (int)(d).size(), m = 0;
    vector<int> cnt(n, 0);
    vector<ll> dp(n, 0);
    for (auto di : d)
        cnt[di]++, m = max(m, di);
    if (d[0] != 0 or cnt[0] > 1)
        return 0;
    dp[0] = 1;
    for (int i = 1; i <= m; ++i)
    {
        if (cnt[i] == 0)
            return 0;
        dp[i] = dp[i - 1];
        for (int j = 0; j < cnt[i]; ++j)
            dp[i] = (dp[i] * cnt[i - 1]) % MOD;
    }
    return dp[m];
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n;
    cin >> n;
    vector<int> d(n);
    read_n(begin(d), n);
    cout << solve(d) << endl;
    return 0;
}

arc076_a - Reconciled

09 Dec 2020 — Tags: math,sorting — URL

Note that if $|n - m| > 1$ there’s no way to avoid getting two animals of the same type beside each other.

Without loss of generality, assume $n \geq m$. Let’s break it into cases:

  1. $ n = m + 1 $: Our arrangements will have the form: $DMDM…MDMD$. We can count all possible arrangements of dogs $D$ and monkeys $M$ and multiply those counts together. Since animals are distinguishable, such quantities are $n!$ and $m!$.
  2. $n = m$: Our arrangements will have the form: $DMD…MDM$ or $MDMD…MD$. Similar arguments, but multiply by $2$ to account for both types of arrangements.

Since $n$ is small enough, let’s just precompute all.

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 const MOD = 1e9 + 7;
int solve(int n, int m)
{
    if (n < m)
        swap(n, m);
    if (n - m > 1)
        return 0;
    vector<ll> fact(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i)
        fact[i] = (i * fact[i - 1]) % MOD;
    return ((n == m ? 2 : 1) * (fact[n] * fact[m]) % MOD) % MOD;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    cout << solve(n, m) << endl;
    return 0;
}

abc089_c - March

09 Dec 2020 — Tags: counting — URL

Mantain count of strings that start with one of “MARCH” letters. Count all possible triplets.

Time complexity: $O(1)$

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);
    const string march = "MARCH";
    array<ll, 5> cnt;
    fill(begin(cnt), end(cnt), 0);
    int n;
    cin >> n;
    while (n--)
    {
        string s;
        cin >> s;
        if (auto it = find(begin(march), end(march), s[0]); it != end(march))
            cnt[distance(begin(march), it)]++;
    }
    ll ans = 0;
    for (int i = 0; i < 3; ++i)
        for (int j = i + 1; j < 4; ++j)
            for (int k = j + 1; k < 5; ++k)
                ans += cnt[i] * cnt[j] * cnt[k];
    cout << ans << endl;
    return 0;
}

abc184_b - Quizzes

08 Dec 2020 — Tags: easy,implementation — URL

Iterate through all Takahashi’s answers in order and update $x$ as the problem says.

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 n, x;
    cin >> n >> x;
    while (n--)
    {
        char cur;
        cin >> cur;
        if (cur == 'o')
            x += 1;
        else
            x = max(0, x - 1);
    }
    cout << x << endl;
    return 0;
}

abc184_a - Determinant

08 Dec 2020 — Tags: easy — URL

$a \times d - b \times c$.

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 main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    cout << a * d - b * c << endl;
    return 0;
}

abc148_c - Super Ryuma

08 Dec 2020 — Tags: binary_search,math — URL

See Editorial for a much better $O(1)$ solution.

To ease our analysis, let’s paint the board with two colors, black and white, in the same way as a chess board.

Note that if both pieces are on a cell with the same color, then the maximum number of moves is 2 (two diagonals). Otherwise it is 3.

Compute the two points $p_3$ and $p_4$ that are closest to $p_2$ if I take the respective diagonals from $p_1$ (using Binary Search). Let’s say that $p_3$ is the closest one to $p_2$.

If $p_3$ is at more distance than $3$, and both points are at the same color, then we will only need another diagonal move, otherwise we’ll need a move to change colors and another diagonal move to reach $p_2$.

There are some cases to handle left, but that’s the gist.

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

Memory complexity: $O(1)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using predicate = function<bool(ll)>;
inline ll manhattan(ii p1, ii p2)
{
    return abs(p1.first - p2.first) + abs(p1.second - p2.second);
}
ll bs(ll l, ll r, predicate p)
{
    while (l < r)
    {
        ll m = l + (r - l) / 2;
        if (p(m))
            r = m;
        else
            l = m + 1;
    }
    return l;
}
bool argmin(function<ll(ll)> f, ll x) { return f(x + 1) - f(x) >= 0; }
ii diag1(ii p, ll x) { return ii{p.first + x, p.second + x}; }
ii diag2(ii p, ll x) { return ii{p.first + x, p.second - x}; }
int solve(ii p1, ii p2)
{
    if (p1 == p2)
        return 0;
    else if (manhattan(p1, p2) <= 3)
        return 1;
    else
    {
        auto f1 = [p1, p2](ll x) { return manhattan(p2, diag1(p1, x)); };
        auto f2 = [p1, p2](ll x) { return manhattan(p2, diag2(p1, x)); };
        ll x1 = bs(-1e9, 1e9, bind(argmin, f1, placeholders::_1));
        ll x2 = bs(-1e9, 1e9, bind(argmin, f2, placeholders::_1));
        ii p3 = f1(x1) <= f2(x2) ? diag1(p1, x1) : diag2(p1, x2);
        if (p3 == p2)
            return 1;
        else if (manhattan(p1, p2) <= 6 or manhattan(p2, p3) <= 3)
            return 2;
        else
            return 2 +
                   !((p3.first + p3.second) % 2 == (p2.first + p2.second) % 2);
    }
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    ii p1, p2;
    cin >> p1.first >> p1.second;
    cin >> p2.first >> p2.second;
    cout << solve(p1, p2) << endl;
    return 0;
}