Competitive Programming Solutions

101889E - Enigma

28 Nov 2020 — Tags: None

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 const NMAX = 1e3 + 11;
int const XMAX = 1e3 + 11;
int n, x;
string s;
bool dp[NMAX][XMAX], vis[NMAX][XMAX];
char ans[NMAX];
bool possible(int i, int rem)
{
    if (i == n)
        return rem == 0;
    auto &cur = dp[i][rem];
    if (vis[i][rem])
        return cur;
    vis[i][rem] = true;
    if (s[i] == '?')
    {
        for (int d = (i == 0); d <= 9; ++d)
        {
            ans[i] = d + '0';
            if (possible(i + 1, (10 * rem + d) % x))
                return cur = true;
            ans[i] = 0;
        }
    }
    else
    {
        int d = s[i] - '0';
        ans[i] = d + '0';
        if (possible(i + 1, (10 * rem + d) % x))
            return cur = true;
        ans[i] = 0;
    }
    return cur = false;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    while (cin >> s >> x)
    {
        n = (int)s.size();
        memset(dp, 0, sizeof dp);
        memset(vis, 0, sizeof vis);
        memset(ans, 0, sizeof ans);
        if (possible(0, 0))
            write(ans, ans + n, ""), cout << endl;
        else
            cout << "*" << endl;
    }
    return 0;
}

148A - Insomnia Cure

27 Nov 2020 — Tags: number_theory,factorization,brute_force — URL

Count all numbers [1, d] that are at least divisible by k, l, m or n.

Time complexity: $O(d)$

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);
    vi factors(4);
    for (auto &fi : factors)
        cin >> fi;
    int d, ans = 0;
    cin >> d;
    for (int i = 1; i <= d; ++i)
    {
        for (auto fi : factors)
        {
            if (i % fi == 0)
            {
                ans++;
                break;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

1342C - Yet Another Counting Problem

27 Nov 2020 — Tags: math,lcm — URL
  • We first observe that the after every $lcm(a, b)$, the pattern of moduli repeats itself.
  • This suggest the idea of precomputing the result for the first block of numbers ( (of size $lcm(a,b)$). We’ll refer to this array as block or pre.
  • Querying for a [0, r] range seems reasonably simple: We count how many full blocks fit in our range + the part of the block that was cut by $r$.
  • We can solve the problem’s query [l, r] by splitting it into two of our queries. [0, r] - [0, l - 1].

Time complexity: $O(ab + q)$

Memory complexity: $O(ab)$

Click to show code.

 

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
int const AMAX = 200 + 5;
ll period, pre[AMAX * AMAX];
inline ll cnt(ll r) { return pre[period - 1] * (r / period) + pre[r % period]; }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int a, b, q;
        cin >> a >> b >> q;
        period = lcm(a, b);
        pre[0] = 0;
        for (int x = 1; x <= period; ++x)
            pre[x] = pre[x - 1] + (((x % a) % b) != ((x % b) % a));
        while (q--)
        {
            ll l, r;
            cin >> l >> r;
            cout << cnt(r) - cnt(l - 1) << " ";
        }
        cout << endl;
    }
    return 0;
}

1175A - From Hero To Zero

27 Nov 2020 — Tags: number_theory,euclidean_algorithm — URL

Intuition tells us that it is always better to divide by $k$ whenever possible. Following this reasoning, the procedure is as follows:

For a number $n = d_1 * k + r_1$, subtract $r_1$ and perform one division. Our new number will be $d_1$. Proceed until 0.

One way to think about the problem is to convert the number $n$ to base-$k$. The problem would then be to wipe out all numbers to get a sequence of zeros, by subtracting $1$ or shifting left one position if the last position is $0$.

I think it becomes more evident why the aforementioned strategy is optimal.

Time complexity: $O( \log{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>;
ll solve(ll n, ll k)
{
    if (n == 0)
        return 0;
    ll r = n % k, d = n / k;
    return r + (d == 0 ? 0 : 1 + solve(d, k));
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        ll n, k;
        cin >> n >> k;
        cout << solve(n, k) << endl;
    }
    return 0;
}

516 - Prime Land

26 Nov 2020 — Tags: number_theory,factorization — URL
  • Reconstruct number.
  • Prime factorize number - 1.

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

Memory complexity: $O(n)$

Click to show code.

 

using namespace std;
using ll = long long;
const int PMAX = 1e5 + 11;
bitset<PMAX> is_prime;
vector<int> primes;
int binpow(int base, int exp)
{
    int ans = 1;
    while (exp > 0)
    {
        if (exp & 1)
            ans *= base;
        base *= base;
        exp >>= 1;
    }
    return ans;
}
map<int, int> prime_factors(ll n)
{
    map<int, int> factors;
    ll i = 0, pf = primes[i];
    while (pf * pf <= n)
    {
        while (n % pf == 0)
        {
            factors[pf]++;
            n = n / pf;
        }
        pf = primes[++i];
    }
    if (n != 1)
        factors[n]++;
    return factors;
}
void sieve(void)
{
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    for (ll i = 2; i < PMAX; i++)
        if (is_prime[i])
        {
            for (ll j = i * i; j < PMAX; j += i)
                is_prime[j] = 0;
            primes.push_back(i);
        }
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    string line;
    sieve();
    while (getline(cin, line) and line[0] != '0')
    {
        stringstream ss(line);
        int n = 1, p, e;
        while (ss >> p >> e)
            n *= binpow(p, e);
        auto factors = prime_factors(n - 1);
        for (auto it = factors.rbegin(); it != factors.rend(); ++it)
        {
            cout << it->first << " " << it->second;
            if (next(it) != factors.rend())
                cout << " ";
        }
        cout << endl;
    }
    return 0;
}

arc107_a - Simple Math

24 Nov 2020 — Tags: math — URL

We only need to manipulate the summation a bit to represent it in closed forms. For example:

\[\sum_{i = 1}^{C} = \frac{C * (C + 1)}{2}\]

Since we’are dealing with modular arithmetic, we’ll need to compute the inverse of 2. The final formula is:

\[\frac{A * (A + 1)}{2} \times \frac{B * (B + 1)}{2} \times \frac{C * (C + 1)}{2}\]

Time complexity: $O(log(MOD))$

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 <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 = 998244353;
using NM = NumMod<MOD, ll>;
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); }
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    ll a, b, c;
    cin >> a >> b >> c;
    NM ans = NM(a * (a + 1)) / 2 * NM(b * (b + 1)) / 2 * NM(c * (c + 1)) / 2;
    cout << ll(ans) << endl;
    return 0;
}

BRCKTS - Brackets

24 Nov 2020 — Tags: data_structures,segment_tree — URL
  • Build a segment tree where nodes represent the unmatched left and right parenthesis.
  • Merging nodes $L$ and $R$, would mean matching the unmatched right parenthesis of $R$ with the unmatched left parenthesis of $L$.
  • Checking if the string is unbalanced would be the same as checking if the root segment tree node has 0 left and right unmatched parenthesis;

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>;
template <typename T, typename Container>
struct SegmentTree
{
    int n;
    vector<T> t;
    SegmentTree(Container &a) : n(a.size())
    {
        t.resize(4 * n);
        build(a, 1, 0, n - 1);
    }
    void build(Container &a, int v, int tl, int tr)
    {
        if (tl == tr)
            t[v] = T(a[tl]);
        else
        {
            int tm = (tl + tr) / 2;
            build(a, v * 2, tl, tm);
            build(a, v * 2 + 1, tm + 1, tr);
            t[v] = merge(t[v * 2], t[v * 2 + 1]);
        }
    }
    inline T merge(T a, T b) { return a + b; }
    T query(int v, int tl, int tr, int l, int r)
    {
        if (l > r)
            return T();
        if (l == tl and r == tr)
            return t[v];
        int tm = (tl + tr) / 2;
        return merge(query(v * 2, tl, tm, l, min(r, tm)),
                     query(v * 2 + 1, tm + 1, tr, max(l, tm + 1), r));
    }
    void update(int v, int tl, int tr, int pos, T new_val)
    {
        if (tl == tr)
            t[v] = new_val;
        else
        {
            int tm = (tl + tr) / 2;
            if (pos <= tm)
                update(v * 2, tl, tm, pos, new_val);
            else
                update(v * 2 + 1, tm + 1, tr, pos, new_val);
            t[v] = merge(t[v * 2], t[v * 2 + 1]);
        }
    }
};
struct Node
{
    int umleft, umright;
    Node() { umleft = umright = -1; }
    Node(int umleft, int umright) : umleft(umleft), umright(umright) {}
    explicit Node(char c) : umleft(c == '('), umright(c == ')') {}
    bool operator==(Node const &other) const
    {
        return umleft == other.umleft and umright == other.umright;
    }
    Node operator+(Node const &right_node) const
    {
        if (this->operator==(Node()))
            return right_node;
        if (right_node == Node())
            return *this;
        int matches = min(umleft, right_node.umright);
        return {right_node.umleft + umleft - matches,
                right_node.umright + umright - matches};
    }
    bool balanced(void) const { return umleft == 0 and umright == 0; }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t = 10;
    while (t--)
    {
        int n, m;
        string brackets;
        cin >> n >> brackets >> m;
        SegmentTree<Node, string> st(brackets);
        cout << "Test " << 10 - t << ":\n";
        while (m--)
        {
            int k;
            cin >> k;
            if (k == 0)
            {
                cout << (st.query(1, 0, n - 1, 0, n - 1).balanced() ? "YES"
                                                                    : "NO")
                     << '\n';
            }
            else
            {
                k--;
                brackets[k] = (brackets[k] == '(' ? ')' : '(');
                st.update(1, 0, n - 1, k, Node(brackets[k]));
            }
        }
    }
    return 0;
}

236B - Easy Number Challenge

24 Nov 2020 — Tags: number_theory,divisors,brute_force — URL
  • Precompute the divisor function up to $a \times b \times c$.
  • A way to interpret this is the following: For each possible number, we’ll increment the divisor count of all its multiples.
  • Brute-force the solution.

Time complexity: $O(abc * \log{abc})$

Memory complexity: $O(abc)$

Click to show code.

 

using namespace std;
using ll = long long;
using vi = vector<int>;
vi precompute_divisors(int n)
{
    vi d(n + 1, 0);
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i)
            d[j]++;
    return d;
}
int solve(int a, int b, int c)
{
    int const MOD = 1 << 30;
    ll ans = 0;
    auto d = precompute_divisors(a * b * c);
    for (int i = 1; i <= a; ++i)
        for (int j = 1; j <= b; ++j)
            for (int k = 1; k <= c; ++k)
                ans = (ans + d[i * j * k]) % MOD;
    return ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int a, b, c;
    cin >> a >> b >> c;
    cout << solve(a, b, c) << endl;
    return 0;
}

10490 - Mr Azad And His Son

24 Nov 2020 — Tags: number_theory,primes — URL
  • Testing primality up to the square root does the trick.

Implementation details:

  • Make sure you precompute the square root, instead of constantly squaring x. That did all the difference for me (from 3s TLE to 0ms AC).

Time complexity: $O(\sqrt{2^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>;
bool is_prime(int n)
{
    if (n < 2)
        return false;
    for (int x = 2, sq = sqrt(n); x <= sq; ++x)
        if (n % x == 0)
            return false;
    return true;
}
int main(void)
{
    int n;
    while (scanf("%d", &n) == 1 && n)
    {
        if (not is_prime(n))
            printf(
                "Given number is NOT prime! NO perfect number is available.\n");
        else if (is_prime((1LL << n) - 1))
            printf("Perfect: %lld!\n", (1LL << (n - 1)) * ((1LL << n) - 1));
        else
            printf("Given number is prime. But, NO perfect number is "
                   "available.\n");
    }
    return 0;
}

10368 - Euclids Game

24 Nov 2020 — Tags: number_theory,gcd — URL

For simplicity, let’s assume $b \leq a$.

  • At any state the player has the option to take $[1, a / b]$ from $a$.
  • Note that there’s always a turning point, when $a$ becomes less than $b$.
  • Let’s call the current state $s_i$ and the next turning point state, $s_n(i)$.
  • We have two cases:
    1. $s_n(i)$ is a losing state $\to$ We take $a/b$ from $a$ to force the next player to lose.
    2. $s_n(i)$ is a winning state. If $a / b \geq 2$, we take $a / b - 1$ and force the next player to take $b$, which leaves us in the winning state.

Time complexity: $O( \log{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>;
bool solve(int a, int b)
{
    if (b == 0)
        return false;
    return !solve(b, a % b) || (a / b >= 2);
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int a, b;
    while (cin >> a >> b, a and b)
    {
        if (b > a)
            swap(a, b);
        cout << (solve(a, b) ? "Stan" : "Ollie") << " wins" << endl;
    }
    return 0;
}