Problem A - Number Theory$$$ \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) $$$ $$$S = \frac{a \cdot (r^n - 1)}{r - 1}$$$ $$$ \prod_{i=1}^{n} \left( \frac{p_i^{69*(e_i+1)} - 1}{p_i^{69} - 1} \right) $$$
We can utilize the formula for the sum of a geometric progression to compute the sum of divisors raised to the power 69 efficiently.
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: 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 :
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
We know that our answer can only lie in the range [0,n]. The position of the numbers actually does not matter, as the number should just be in the array, irrespective of its index. Also, we do not need the duplicates. So, we can make a set of the entire array.
Now, the basic intuition is that, given 'k', it is guaranteed that we can place first k non-negative elements in the array. We just need to check how many elements are there in the array which is less than or equal to k. For each element that is present which is less than or equal to k, we can have 1 element which is greater than k.
So, we can loop through all the elements of the set, ignore the negative elements, and add to k if there is any number less than or equal to k.
At last, we can return min(k, n) as the answer.
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long int
void solve() {
// taking the inputs
int n, k;
cin >> n >> k;
vector<int> a(n);
for(int i=0; i<n; i++){
cin >> a[i];
}
// to handle duplicates and getting the values in sorted order
set<int> s(a.begin(),a.end());
// iterating through all the values
for(auto i:s)
{
// handling negative values
if(i<0) continue;
// increement k if any element is less than or equal to k
if(i<=k)k++;
}
// max possible answer can be n
cout << min(k,n) << endl;
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int t; cin>>t;
while(t--){
solve();
}
return 0;
}
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
Code
Problem F - Trie Me
We're sorry for the inconvenience we didnt know that this problem's solution was available in a cf blog
Link to the blog : https://mirror.codeforces.com/blog/entry/68953
Problem G - Minimum Sum Node$$$in[u] = \sum_{v \in \text{children of } u} (in[v] + sub[v])$$$ $$$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])$$$
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]:
(Use 'sub[v]' to denote the size of the subtree rooted at v.)
- Calculating out[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
The total number of answers will never be more than 2.
Also the answer will always be the centroid of the tree
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
pssinto 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)
...
