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 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();
}
