Blog entries - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	170
2	maomao90	162
2	Um_nik	162
4	atcoder_official	160
5	djm03178	158
5	-is-this-fft-	158
7	adamant	154
7	Dominater069	154
9	awoo	153
10	luogu_official	152

Problem A - Number Theory

We can utilize the formula for the sum of a geometric progression to compute the sum of divisors raised to the power 69 efficiently.

$$$ \left(1 + p_1^{69} + p_1^{69*2} + \ldots + p_1^{69*e_1}\right) \times \left(1 + p_2^{69} + p_2^{69*2} + \ldots + p_2^{69*e_2}\right) \times \ldots \times \left(1 + p_n^{69} + p_n^{69*2} + \ldots + p_n^{69*e_n}\right) $$$

When computing the sum of divisors of a number, each divisor contributes to the total sum according to its power. For a prime factor $$$x$$$ raised to the power $$$y$$$, the divisors are of the form $$$x^0, x^1, x^2, \ldots, x^y$$$. Notice that these are in a geometric progression.

The formula for the sum of a geometric progression is:

$$$S = \frac{a \cdot (r^n - 1)}{r - 1}$$$

S: The sum of the geometric progression.
a: The first term of the progression (in this case, 1).
r: The common ratio, which is $$$x^{69}$$$.
n: The number of terms, which is y + 1.

Now, the sum of a geometric progression formula allows us to find the sum of such terms efficiently. This formula works here because each divisor contributes according to its power, and the powers themselves are in an arithmetic progression.

This simplifies to :

$$$ \prod_{i=1}^{n} \left( \frac{p_i^{69*(e_i+1)} - 1}{p_i^{69} - 1} \right) $$$

Since the input numbers and their powers can be large, we need to perform all computations modulo $$$10^9 + 7$$$ to prevent overflow.

And use Mod Inverse For Division since the mod given is prime

Code

#include "bits/stdc++.h"

using namespace std;

#define VarunDeepSaini ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define int            long long
#define double         long double
#define endl           "\n"
#define all(x)         x.begin(), x.end()
#define v              vector
#define vi             vector<int>
#define vvi            vector<vector<int>>
#define pii            pair<int, int>
#define mpci           map<char, int>
#define mpii           map<int, int>
#define pb             emplace_back
#define mp             make_pair
#define F              first
#define S              second
#define si             set<int>
#define msi            multiset<int>
#define maxn           1000005

int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}
int power(int a, int b, int m) { int ans = 1; while (b) { if (b & 1) ans = (ans * a) % m; b /= 2; a = (a * a) % m; } return ans; }
int lcm(int a, int b) { return (a * b) / gcd(a, b); }
int modInverse(int a, int m) { return power(a, m - 2, m); }
int modAdd(int a, int b, int m) { return ((a % m) + (b % m)) % m; }
int modMul(int a, int b, int m) { return ((a % m) * (b % m)) % m; }
int modSub(int a, int b, int m) { return ((a % m) - (b % m) + m) % m; }
int modDiv(int a, int b, int m) { return (modMul(a, modInverse(b, m), m) + m) % m; }
bool isPrime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }
int nCr(int n, int r) { if (r > n - r) r = n - r; int ans = 1; for (int i = 0; i < r; i++) { ans *= (n - i); ans /= (i + 1); } return ans; }
int nCrModP(int n, int r, int p) { if (r > n - r) r = n - r; int C[r + 1]; memset(C, 0, sizeof(C)); C[0] = 1; for (int i = 1; i <= n; i++) { for (int j = min(i, r); j > 0; j--) C[j] = (C[j] + C[j - 1]) % p; } return C[r]; }
int nPr(int n, int r) { int ans = 1; for (int i = 0; i < r; i++) ans *= (n - i); return ans; }
int nPrModP(int n, int r, int p) { int ans = 1; for (int i = 0; i < r; i++) ans = (ans * (n - i)) % p; return ans; }
int log(int num , int base){int ans = 0; while(num){num /= base;ans++;} return ans;}
int countSetBits(int x){int ans = 0;while(x){ans += (x&1);x >>= 1;}return ans;}

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

bool testcases = 0;

const int mod = 1e9 + 7;

void solve()
{
    int ans = 1;
    int n; cin >> n;
    for(int i = 0 ; i  < n; i++){

        int x ,y; cin >> x >> y;
        ans *= ((power(x,(69*y+69),mod) - 1)%mod * modInverse(power(x,69,mod)-1,mod))%mod;
        ans %= mod;

    }  

    cout << ans << endl;
}

int32_t main()
{
    VarunDeepSaini 
    int t = 1;
    testcases and cin >> t;
    while(t--) solve();
}

Problem B - Maximise Mex

Problem C - Thala For A Reason

In this problem, our objective is to count the total number of ways the cricket team can win in the last over, given the total wickets left, total runs left, and total balls left. We can approach this problem using a recursive technique to enumerate all possible winning scenarios.

We can define a recursive function to explore all possible combinations of runs and wickets in the last over. At each step, we consider all possible moves a team can make, including scoring runs, getting out, or facing a dot ball. The recursive function counts the total number of ways the team can win based on the remaining runs, wickets, and balls.

Code

#include "bits/stdc++.h"

using namespace std;

#define VarunDeepSaini ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define int            long long
#define double         long double
#define endl           "\n"
#define all(x)         x.begin(), x.end()
#define v              vector
#define vi             vector<int>
#define vvi            vector<vector<int>>
#define pii            pair<int, int>
#define mpci           map<char, int>
#define mpii           map<int, int>
#define pb             emplace_back
#define mp             make_pair
#define F              first
#define S              second
#define si             set<int>
#define msi            multiset<int>
#define maxn           1000005

int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}
int power(int a, int b, int m) { int ans = 1; while (b) { if (b & 1) ans = (ans * a) % m; b /= 2; a = (a * a) % m; } return ans; }
int lcm(int a, int b) { return (a * b) / gcd(a, b); }
int modInverse(int a, int m) { return power(a, m - 2, m); }
int modAdd(int a, int b, int m) { return ((a % m) + (b % m)) % m; }
int modMul(int a, int b, int m) { return ((a % m) * (b % m)) % m; }
int modSub(int a, int b, int m) { return ((a % m) - (b % m) + m) % m; }
int modDiv(int a, int b, int m) { return (modMul(a, modInverse(b, m), m) + m) % m; }
bool isPrime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }
int nCr(int n, int r) { if (r > n - r) r = n - r; int ans = 1; for (int i = 0; i < r; i++) { ans *= (n - i); ans /= (i + 1); } return ans; }
int nCrModP(int n, int r, int p) { if (r > n - r) r = n - r; int C[r + 1]; memset(C, 0, sizeof(C)); C[0] = 1; for (int i = 1; i <= n; i++) { for (int j = min(i, r); j > 0; j--) C[j] = (C[j] + C[j - 1]) % p; } return C[r]; }
int nPr(int n, int r) { int ans = 1; for (int i = 0; i < r; i++) ans *= (n - i); return ans; }
int nPrModP(int n, int r, int p) { int ans = 1; for (int i = 0; i < r; i++) ans = (ans * (n - i)) % p; return ans; }
int log(int num , int base){int ans = 0; while(num){num /= base;ans++;} return ans;}
int countSetBits(int x){int ans = 0;while(x){ans += (x&1);x >>= 1;}return ans;}

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

bool testcases = 0;

const int mod = 1e9 + 7;

int rec(int runs, int wickets, int balls){
    
    if(runs <= 0) return 1;
    if(wickets <= 0) return 0;
    if(balls == 0) return 0;

    int ans = 0;

    ans += rec(runs - 0, wickets, balls - 1);
    ans += rec(runs - 1, wickets, balls - 1);
    ans += rec(runs - 2, wickets, balls - 1);
    ans += rec(runs - 3, wickets, balls - 1);
    ans += rec(runs - 4, wickets, balls - 1);
    ans += rec(runs - 6, wickets, balls - 1);
    ans += rec(runs, wickets - 1, balls - 1);

    return ans;
}

void solve()
{
    
    int runs , wickets; cin >> runs >> wickets;

    cout << rec(runs, wickets, 6) << endl;

}

int32_t main()
{
    VarunDeepSaini 
    int t = 1;
    testcases and cin >> t;
    while(t--) solve();
}

Problem D - Sort me please *uwu*

Code

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
 
#include <bits/stdc++.h>
using namespace std;
 
#ifdef TOWRIST
    #define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__);
#else
    #define debug(...);
#endif
 
template <typename T> std::ostream &operator<<(std::ostream &stream, const vector<T> &vec) {for (size_t i = 0; i < vec.size(); i++) { stream << vec[i]; if (i != vec.size() - 1) stream << ' '; }; return stream; } template <typename T> std::istream &operator>>(std::istream &stream, vector<T> &vec) {for (T &x : vec) stream >> x; return stream; } template <typename T, typename U> std::ostream &operator<<(std::ostream &stream, const pair<T, U> &pr) {stream << pr.first << ' ' << pr.second; return stream; } template <typename T, typename U> std::istream &operator>>(std::istream &stream, pair<T, U> &pr) {stream >> pr.first >> pr.second; return stream; } template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p); string to_string(const string &s) { return '"' + s + '"'; } string to_string(char c) {string s; s += c; return s; } string to_string(const char *s) { return to_string((string)s); } string to_string(bool b) { return (b ? "1" : "0"); } string to_string(vector<bool> v) {bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) {if (!first) {res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template <size_t N> string to_string(bitset<N> v) {string res = ""; for (size_t i = 0; i < N; i++) {res += static_cast<char>('0' + v[i]); } return res; } template <typename A> string to_string(A v) {bool first = true; string res = "{"; for (const auto &x : v) {if (!first) {res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cout << endl; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cout << " " << to_string(H); debug_out(T...); }
 
#define int     long long
#define all(x)  x.begin(), x.end()
#define double  long double
#define endl    '\n'
#define ff      first
#define ss      second
#define v       vector
 
using pii = pair<int, int>;
const bool multipleTestCases = false;
 
bool isSortingPossible(v<pii> &arr, map<pii, int> &mp) {
    int n = arr.size();
 
    set<int> st[n + 1];
    for(int i = 0; i < n; ++i) {
        st[arr[i].ff].insert(arr[i].ss);
    } 
 
    int prev = INT_MIN;
    v<int> temp(n);
    for(int i = 0; i < n; ++i) {
        auto [color, val] = arr[i];
 
        temp[i] = *st[color].begin();
        st[color].erase(temp[i]);
 
        mp[{color, temp[i]}] = i;
        if(temp[i] < prev) {
            return false;
        }
        prev = temp[i];
    }
 
    return true;
}
 
void solve()
{
    int n; cin >> n;
    v<pii> arr(n); // {color, value}
    for(int i = 0; i < n; ++i) {
        cin >> arr[i].ff;
    }
    for(int i = 0; i < n; ++i) {
        cin >> arr[i].ss;
    }
 
    map<pii, int> mp; // {{color, val}, idx_after_sorting}
    if(!isSortingPossible(arr, mp)) {
        cout << -1 << endl;
        return;
    }
    
    v<pii> ops;
    for(int i = 0; i < n; ++i)
    {
        int expectedIndex = mp[arr[i]];
        if(expectedIndex == i) {
            continue;
        }
 
        ops.push_back({i, expectedIndex});
        swap(arr[i], arr[expectedIndex]);
        --i;
    }
 
    cout << ops.size() << endl;
    for(auto it : ops) {
        cout << it.ff << " " << it.ss << endl;
    }
} 
 
signed main()
{
    cin.tie(nullptr)->sync_with_stdio(false);
    int t = 1;
    multipleTestCases and cin >> t;
    for (int i = 1; i <= t; i++)
    {
        // cout << "Case #" << i << ": ";
        solve();
    }
}

Problem E - Prime Queries

Problem F - Trie Me

Problem G - Minimum Sum Node

In-Out Tree DP

in[u]: This represents the total of distances from node u to all other nodes within the subtree that has u as its root.
out[u]: This signifies the total of distances from node u to all other nodes that are not part of the subtree with u as its root.

Calculation

ans[u] = in[u] + out[u]: This equation gives us the total distance from node u to all other nodes in the tree.
Calculating in[u]:

$$$in[u] = \sum_{v \in \text{children of } u} (in[v] + sub[v])$$$

(Use 'sub[v]' to denote the size of the subtree rooted at v.)

Calculating out[u]:

$$$out[u] = out[\text{par}] + (n - sub[\text{par}] + 1) + (\sum_{\text{sib}} (in[\text{sib}] + 2 \cdot sub[\text{sib}])) - (in[u] + 2 \cdot sub[u])$$$

(Use 'par' to refer to the parent of node u, 'n' for the total nodes, and 'sib' for siblings of node u.)

Interesting Observations

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;

int contribution(pii x) {
    return x.first + x.second;
}

void solve() {
    int n;
    cin >> n;
    vvi adj(n+1);
    for(int i = 0; i < n-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<pii> dp(n+1);
    function<void(int,int)> dfs1 = [&](int nd, int pr) {
        for(int i : adj[nd]) {
            if(i == pr) continue;
            dfs1(i, nd);
            dp[nd].first += contribution(dp[i]);
            dp[nd].second += dp[i].second;
        }
        dp[nd].second++;
    };
    dfs1(1, 0);

    vi up(n+1);
    function<void(int,int)> dfs2 = [&](int nd, int pr) {
        if(pr) {
            up[nd] = dp[pr].first - contribution(dp[nd]) + (dp[pr].second - dp[nd].second);
            up[nd] += up[pr] + n - dp[pr].second;
        }
        for (int i : adj[nd]) {
            if (i == pr) continue;
            dfs2(i, nd);
        }
    };
    dfs2(1, 0);

    vi ans(n);
    for(int i = 1; i <= n; i++) {
        ans[i-1] = dp[i].first + up[i];
    }
    int minn = *min_element(ans.begin(), ans.end());
    int cntmin = count(ans.begin(), ans.end(), minn);
    cout << cntmin << endl;
    for(int i = 0; i < n; i++) {
        if(ans[i] == minn) {
            cout << i+1 << ' ';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    solve();
    return 0;
}

Alternate Solution

#include "bits/stdc++.h"

using namespace std;

#define VarunDeepSaini ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define int long long
#define double long double
#define endl "\n"
#define all(x) x.begin(), x.end()
#define v vector
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define mpci map<char, int>
#define mpii map<int, int>
#define pb emplace_back
#define mp make_pair
#define F first
#define S second
#define si set<int>
#define msi multiset<int>
#define maxn 1000005

int gcd(int a, int b) { if (b == 0) return a; return gcd(b, a % b);}
int power(int a, int b, int m) { int ans = 1; while (b) { if (b & 1) ans = (ans * a) % m; b /= 2; a = (a * a) % m; } return ans; }
int lcm(int a, int b) { return (a * b) / gcd(a, b); }
int modInverse(int a, int m) { return power(a, m - 2, m); }
int modAdd(int a, int b, int m) { return ((a % m) + (b % m)) % m; }
int modMul(int a, int b, int m) { return ((a % m) * (b % m)) % m; }
int modSub(int a, int b, int m) { return ((a % m) - (b % m) + m) % m; }
int modDiv(int a, int b, int m) { return (modMul(a, modInverse(b, m), m) + m) % m; }
bool isPrime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; }
int nCr(int n, int r) { if (r > n - r) r = n - r; int ans = 1; for (int i = 0; i < r; i++) { ans *= (n - i); ans /= (i + 1); } return ans; }
int nCrModP(int n, int r, int p) { if (r > n - r) r = n - r; int C[r + 1]; memset(C, 0, sizeof(C)); C[0] = 1; for (int i = 1; i <= n; i++) { for (int j = min(i, r); j > 0; j--) C[j] = (C[j] + C[j - 1]) % p; } return C[r]; }
int nPr(int n, int r) { int ans = 1; for (int i = 0; i < r; i++) ans *= (n - i); return ans; }
int nPrModP(int n, int r, int p) { int ans = 1; for (int i = 0; i < r; i++) ans = (ans * (n - i)) % p; return ans; }
int log(int num , int base){int ans = 0; while(num){num /= base;ans++;} return ans;}
int countSetBits(int x){int ans = 0;while(x){ans += (x&1);x >>= 1;}return ans;}
//void sieve(){int isPrime[maxn];memset(isPrime, 1, sizeof(isPrime));isPrime[0] = isPrime[1] = 0;for(int i = 2; i < maxn; i++){if(isPrime[i]){primes[i] = i;for(int j = i*i; j < maxn; j += i){isPrime[j] = 0;if(primes[j] == 0) primes[j] = i;}}}}
// int primes[maxn];

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};


bool testcases = 0;

vvi g;

vector<int> Centroid(const vector<vector<int>> &g) {
        int n = g.size();
        vector<int> centroid;
        vector<int> sz(n);
        function<void (int, int)> dfs = [&](int u, int prev) {
                sz[u] = 1;
                bool is_centroid = true;
                for (auto v : g[u]) if (v != prev) {
                        dfs(v, u);
                        sz[u] += sz[v];
                        if (sz[v] > n / 2) is_centroid = false;
                }
                if (n - sz[u] > n / 2) is_centroid = false;
                if (is_centroid) centroid.push_back(u);
        };
        dfs(0, -1);
        return centroid;
}

void solve()
{
    int n; cin >> n;
    vvi g(n);

    for (int i = 0; i < n - 1; i++)
    {
        int u, v; cin >> u >> v;
        u--, v--;
        g[u].pb(v);
        g[v].pb(u);
    }

    vi centroid = Centroid(g);
    sort(all(centroid));
    cout << centroid.size() << endl;    
    cout << centroid[0] + 1 << endl;
    if (centroid.size() == 2) cout << centroid[1] + 1 << endl;

}

int32_t main()
{
    VarunDeepSaini 
    int t = 1;
    testcases and cin >> t;
    while(t--) solve();
}

Problem H - Negative Phobia

Let's consider an array arr. The prefix sum at index i, denoted as prefixSum[i], is the sum of elements from the beginning of the array up to index i.

Importantly, the sum of a subarray from index i to j can be calculated as:

$$$subarraySum[i, j] = prefixSum[j] - prefixSum[i]$$$

Our goal is to find subarrays where the subarraySum is non-negative (i.e., greater than or equal to zero). This translates to finding indices i and j such that:

$$$prefixSum[j] >= prefixSum[i]$$$

Trie for Prefix Sums: We'll use a trie to store the prefix sums encountered so far. Each node in the trie can represent a part of the prefix sum.
Iteration and Query:

For each element in arr, calculate the current prefix sum (pss).
Query the trie to count how many prefix sums stored in the trie are smaller than pss. These form valid subarrays.
Insert the current pss into the trie.

Code (Trie)

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define v vector
#define vi v<int>
#define pb push_back
template<typename T>istream& operator>>(istream& is, v<T>& v){for(auto& x : v)is >> x;return is;}

class trie
{
public:
    v<trie *> child;
    int cnt=0;
    trie()
    {
        child.resize(2,NULL);
    }
};
trie *root=new trie();
int great(int x) // -1e14 <= x <= 1e14
{
    trie *cur = root;
    // cnt no of elements greater than x
    int k = x+1e14;
    int ans = 0;
    for(int i=63;i>=0;i--)
    {
        int b = (k>>i)&1;
        if(b==0 && cur->child[b^1])
            ans += cur->child[b^1]->cnt; 
        if(!cur->child[b])
            break;
        cur = cur->child[b];
    }
    return ans;
}
void insert(int x) // -1e14 <= x <= 1e14
{
    trie *cur = root;
    x+=1e14; // offset to make it positive 
    for (int i = 63; i >= 0; i--)
    {
        int b = (x >> i) & 1;
        if (!cur->child[b])
            cur->child[b] = new trie();
        cur = cur->child[b];
        cur->cnt++;
    }
}
int f(vi& arr) 
{
    int n = arr.size(); 
    int pss= 0;
    int ans = 0;
    insert(0);
    for(int i=0;i<n;i++)
    {
        pss += arr[i];
        ans += great(pss);
        insert(pss);
    }
    return ans;    
}
void solve()
{
    int n; cin >> n;
    root = new trie();
    vi a(n); cin >> a;
    int res = n*(n+1)/2;    // no of all subarrays
    int ans = f(a);         // cnt no of subarrays with sum less than 0
    cout << res - ans << endl;
}
signed main()
{
    IOS
    int t=1;
    cin >> t;
    while(t--)
    {
        solve();
    }
}

Alternate Solution (Ordered Set)

Full text and comments »

sojabhai's blog

Hello Codeforces!

0xPPL AlgoBee II