arc108_a - Sum And Product

  • Write both equations in terms of one variable, N or M: $N^2 - NS + P = 0$.
  • The problem reduces to finding a positive root of that expression.
  • This problem could be solved by doing a binary search, but it would result in integer overflow.
  • Note, however, that $\max(N, M) <= \sqrt{max(S, P)}$.
  • Since that value doesn’t exceed $10^6$, we can linear search the answer.

Time complexity: $O( \sqrt{ \max(S, P)})$

Memory complexity: $O(1)$

Click to show code.


using namespace std;
using ll = long long;
using predicate = function<bool(ll)>;
bool solve(ll S, ll P)
{
    for (ll N = 1, MAX = 1e6; N <= MAX; ++N)
        if (N * (S - N) == P)
            return true;
    return false;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    ll S, P;
    cin >> S >> P;
    cout << (solve(S, P) ? "Yes" : "No") << endl;
    return 0;
}


abc142_d - Disjoint Set Of Common Divisors

First note that all the common divisors of $A$ and $B$ are the factors of $gcd(A, B)$.

The key observation is that the optimal answer is the set of all prime factors of $gcd(A, B)$ and 1. It is trivial to see that such a set is indeed mutually coprime.

The intuition behind this is that if we were to add a composite factor to our answer set, then it would always be a better choice to add its prime factors.

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

Memory complexity: $O(\sqrt{n})$

Click to show code.


using namespace std;
using ll = long long;
using vi = vector<int>;
vi prime_factors(ll n)
{
    vi factors;
    for (ll i = 2; i * i <= n; ++i)
    {
        while (n % i == 0)
        {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1)
        factors.push_back(n);
    return factors;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    ll A, B;
    cin >> A >> B;
    ll g = gcd(A, B);
    auto factors = prime_factors(g);
    cout << 1 + distance(begin(factors), unique(begin(factors), end(factors))) << endl;
    return 0;
}


1034A - Enlarge Gcd

  • Note that any other common factor between the chosen subset of numbers will result in a greater gcd than the global gcd.
  • So, the problem reduces to finding the most frequent common factor.

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

Memory complexity: $O(a_{max})$

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));
}
using namespace std;
using ll = long long;
using vi = vector<int>;
int const PMAX = 1.5e7 + 11;
int const NMAX = 3e5 + 11;
int n, a[NMAX];
bitset<PMAX> is_prime;
vi primes;
vi factors(PMAX, 0);
void update_factors(int x, int &ans)
{
    for (int const &pf : primes)
    {
        if (pf * pf > x)
            break;
        if (x % pf == 0)
        {
            factors[pf]++;
            ans = max(ans, factors[pf]);
        }
        while (x % pf == 0)
            x = x / pf;
    }
    if (x != 1)
    {
        factors[x]++;
        ans = max(ans, factors[x]);
    }
}
void sieve(int const sieve_size)
{
    is_prime.set();
    is_prime[0] = is_prime[1] = 0;
    for (int i = 2; i * i <= sieve_size; i++)
    {
        if (is_prime[i])
        {
            for (int j = i * i; j <= sieve_size; j += i)
                is_prime[j] = 0;
            primes.push_back(i);
        }
    }
}
int solve(void)
{
    int n_gcn = a[0], ans = 0;
    for (int i = 1; i < n; ++i)
        n_gcn = gcd<int, int>(n_gcn, a[i]);
    for (int i = 0; i < n; ++i)
        update_factors(a[i] / n_gcn, ans);
    return ans == 0 ? -1 : n - ans;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    sieve(PMAX - 1);
    cin >> n;
    for (int i = 0; i < n; ++i)
        cin >> a[i];
    cout << solve() << endl;
    return 0;
}


102694E - Filthy Rich Trees

  • Flattening tree with ETT.
  • Build Segment Tree that stores the multiplication of subtrees as log addition.

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 <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));
}
template <typename T>
struct SegmentTree
{
    using vi = vector<int>;
    int n;
    vector<T> t;
    SegmentTree(vi &a) : n(a.size())
    {
        t.resize(4 * n);
        build(a, 1, 0, n - 1);
    }
    void build(vi &a, int v, int tl, int tr)
    {
        if (tl == tr)
            t[v] = 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 0;
        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 Tree
{
    using vi = vector<int>;
    int n;
    vector<vi> g;
    Tree(int n) : n(n) { g.resize(n); }
    void add_edge(int u, int v)
    {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    void dfs(int u,
             int p,
             function<void(int, int)> init,
             function<void(int, int)> din,
             function<void(int, int)> dout) const
    {
        init(u, p);
        for (auto v : g[u])
        {
            if (v == p)
                continue;
            din(u, v);
            dfs(v, u, init, din, dout);
            dout(u, v);
        }
    }
    pair<vi, vi> flatten(void) const
    {
        int timer = 0;
        vi sz(n, 1), vtime(n, 0);
        auto init = [&vtime, &timer](int u, int p) {
            (void)p;
            vtime[u] = timer++;
        };
        auto din = [](int u, int v) { (void)u, (void)v; };
        auto dout = [&sz](int u, int v) { sz[u] += sz[v]; };
        dfs(0, -1, init, din, dout);
        return {vtime, sz};
    }
};
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int n, q;
    cin >> n;
    Tree tree(n);
    for (int i = 0; i < n - 1; ++i)
    {
        int u, v;
        cin >> u >> v, --u, --v;
        tree.add_edge(u, v);
    }
    auto [vtime, sz] = tree.flatten();
    vi a(n, log(1));
    SegmentTree<double> st(a);
    cin >> q;
    while (q--)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int u, new_val;
            cin >> u >> new_val, u--;
            st.update(1, 0, n - 1, vtime[u], log(new_val));
        }
        else
        {
            int u, v;
            cin >> u >> v, u--, v--;
            double ans = st.query(1, 0, n - 1, vtime[u], vtime[u] + sz[u] - 1) -
                         st.query(1, 0, n - 1, vtime[v], vtime[v] + sz[v] - 1);
            ans = max(log(1e-9), min(ans, log(1e9)));
            cout << fixed << setprecision(12) << exp(ans) << endl;
        }
    }
    return 0;
}


101498J - Spilt The String

  • Note that we only care about the position of the whitespaces, since we can’t break words.
  • We can iterate all whitespaces (they will define the end of the first line with width $w$) and test if positions $2w, 3w, …$ also contain whitespaces.
  • By harmonic series approximation, each test call runs in O(logn)

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>;
bool test(int width, string &line)
{
    int n = (int)(line).size(), i = width - 1;
    for (int d = 1; i < n; i = width * d - 1, ++d)
    {
        if (line[i] != ' ')
            return false;
    }
    return i == n;
}
bool solve(string line)
{
    for (int i = 0, n = (int)(line).size(); i < n; ++i)
    {
        if (line[i] == ' ')
        {
            if (test(i + 1, line))
                return true;
        }
    }
    return false;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    cin.ignore();
    while (t--)
    {
        string line;
        getline(cin, line);
        cout << (solve(line) ? "YES" : "NO") << endl;
    }
    return 0;
}


101498I - Rock Piles

[Maybe this is flawed, but it got AC. Nevertheless, here’s my reasoning.]

  • Let’s define:
    1. Even state: 2 piles have an even amount of rocks.
    2. Odd state: not even state.
  • If a player is on an even state, the second player can always force him to be on even states.
  • So, since the end state has trivially an even state, then whoever starts on an uneven state can force the second player to lose by keeping him on even states.

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 t;
    cin >> t;
    string ans[2] = {"hasan", "abdullah"};
    while (t--)
    {
        ll n, m;
        cin >> n >> m;
        cout << ans[n % 2 == 0 and m % 2 == 0] << endl;
    }
    return 0;
}


101498H - Palindrome Number

  • Note that there are 2 ways in which no solutions exist:
    1. n > 1 and s == 1, where placing 1 on both ends would exceed s.
    2. otherwise, when s exceeds placing 9 on all places.
  • The first case can be handled by a if guard.
  • Note that the most significant digits have greater effect in maximizing the palindrome.
  • The strategy would then be to greedily maximize from i=0 to n/2.

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>;
string solve(int n, int s)
{
    if (n > 1 and s == 1)
        return "-1";
    string ans(n, '0');
    for (int i = 0, mid = n / 2; i < mid; ++i)
    {
        for (int d = 9; d >= 0; --d)
        {
            if (s - 2 * d >= 0)
            {
                ans[i] = ans[n - 1 - i] = d + '0';
                s -= 2 * d;
                break;
            }
        }
    }
    if (n % 2 == 1)
    {
        for (int d = 9; d >= 0; --d)
        {
            if (s - d >= 0)
            {
                ans[n / 2] = d + '0';
                s -= d;
                break;
            }
        }
    }
    return s == 0 ? ans : "-1";
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        int n, s;
        cin >> n >> s;
        cout << solve(n, s) << endl;
    }
    return 0;
}


101498E - Car Factory

  • The answer is $k$ + the time the last car is waiting.

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 t;
    cin >> t;
    while (t--)
    {
        ll n, k;
        cin >> n >> k;
        cout << (n - 1) + k << endl;
    }
    return 0;
}


101498D - Counting Paths

  • A path in a binary tree can be described by a sequence of l’s and r’s.
  • We need to count such $a$-sized sequences such that they change $b$ times.
  • Without loss of generality, such string is of the form: $LRLRLR…LR$, where $L$ and $R$ are blocks of ‘l’s and ‘r’s respectively, with a total of $b+1$ blocks and sum of block sizes equal to $a$.
  • This probem can be thought as finding all the solutions to the equation: \(x_1 + x_2 + ... + x_{b + 1} = a\)
  • Where $x_i >= 1$.
  • This is the stars and bars problem, to which a direct formula is known.

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 <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 = 1e5 + 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)
        return 1;
    return ll(fact[n] * inv_fact[n - k] * inv_fact[k]);
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    precompute_fact();
    while (t--)
    {
        ll a, b;
        cin >> a >> b;
        cout << (2 * C(a - 1, b)) % MOD << endl;
    }
    return 0;
}


101498C - Lunch Break

  • Get index of minimum element.

Time complexity: $O(1)$

Memory complexity: $O(1)$

Click to show code.


using namespace std;
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    string ans[3] = {"First", "Second", "Third"};
    int roads[3];
    while (t--)
    {
        cin >> roads[0] >> roads[1] >> roads[2];
        cout << ans[distance(roads, min_element(roads, roads + 3))] << endl;
    }
    return 0;
}