Problem A : Tarun and the Cannon Range
Author : Casual_W
Problem B : Aditya's Apple Tree
Author : Casual_W
Problem C : Dewansh and the MEX Game
Author : Godbot
Problem D : Jai, Tarun, and the Parentheses Game
Author : Godbot
Problem E : Dewansh and the Growing Digits
Author : Godbot <spoiler summary="Hint" Digits are independent to each other and order does not matter
Define dp[i][j] length of digit i if i do j operations on it Transitions : dp[i][j] = dp[i+1][j-1] when 0<=i<=8 = dp[0][j-1] + dp[1][j-1] when i==9 because when i==9 and u do one more operation then it will be 10 so ad the contribution of those
Precompute this otherwise TC will be m*t which will TLE After precomputing dp[i][j] just multiply it with the number of its occcurences in the given number n
include<bits/stdc++.h>
using namespace std;
define MOD 1000000007
define MOD1 998244353
define pb push_back
typedef long long ll; typedef unsigned long long ull; typedef long double lld; ll mod_add(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a + b) % m) + m) % m;} ll mod_mul(ll a, ll b, ll m) {a = a % m; b = b % m; return (((a * b) % m) + m) % m;} const int nMax = 2 * 1e5 + 10;
ll dp[10][nMax]; void solve() { int t; cin >> t; for (int i = 0; i <= 9; i++) { dp[i][0] = 1; } for (int i = 1; i < nMax; i++) { for (int j = 0; j <= 8; j++) { dp[j][i] = dp[j + 1][i — 1]; } dp[9][i] = mod_add(dp[0][i — 1], dp[1][i — 1], MOD); } while (t--) { int n, m; cin >> n >> m; vector occ(10, 0); while (n > 0) { occ[n % 10]++; n /= 10; } ll ans = 0; for (int i = 0; i < 10; i++) { ll x = dp[i][m]; ll y = occ[i]; ans = mod_add(mod_mul(x, y, MOD), ans, MOD); } cout << ans << endl; } }
int main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); solve(); }
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(), v.end()
#define loop(i, n) for (int i = 0; i < n; i++)
typedef vector<int> vi;
#define vin(a) for (int i = 0; i < (a).size(); i++) cin >> a[i];
#define sz(x) ((int)(x).size())
signed main() {
ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
int t=1;
// cin >> t;
while (t--) {
int n; cin >> n;
vi a(n);
vin(a);
sort(all(a),greater<int>());
int ans=0;
for(int i=0;i<n;i+=2) ans+=(a[i]-a[i+1]);
cout<<ans<<endl;
}
return 0;
}
Problem G : Aditya and the Magic Powder
Author : Godbot
Is the function $$$f(M) = \text{"Can we bake } M \text{ cookies?"}$$$ monotonic?
Binary Search
To bake $$$M$$$ cookies, the $$$i$$$-th ingredient requires a total of $$$M \cdot a_i$$$ grams.Aditya already possesses $$$b_i$$$ grams of the $$$i$$$-th ingredient. Therefore, the deficit (extra amount needed) for ingredient $$$i$$$ is:
Monotonicity:If we can bake $$$x$$$ cookies, we can also bake $$$x - 1$$$ cookies. The predicate function $$$f(x) = \text{"Can bake } x \text{ cookies?"}$$$ forms a monotonic pattern: $$$\text{TTTT}\dots\text{FFFF}\dots$$$. We simply binary search for the rightmost $$$\text{True}$$$ to get the maximum possible cookies.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(), v.end()
#define loop(i, n) for (int i = 0; i < n; i++)
typedef vector<int> vi;
#define vin(a) for (int i = 0; i < (a).size(); i++) cin >> a[i];
#define pb push_back
#define sz(a) (int)a.size()
bool good(vi& a, vi& b, int mid, int k) {
int n = sz(a);
int dec = 0;
loop(i, n) {
int req = a[i] * mid;
if (req > b[i]) {
dec += (req — b[i]);
}
if (dec > k) return 0;
}
return 1;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
int t=1;
// cin >> t;
while (t--) {
int n,k; cin >> n >> k;
vi a(n),b(n);
vin(a);vin(b);
// Binary search -> ttttfff.. <- pattern
int l=0,r=2e9;
int ans=0;
while(l<=r){
int m = l+(r-l)/2;
if(good(a,b,m,k)) ans=max(ans,m),l=m+1;
else r=m-1;
}
cout<<ans<<endl;
}
return 0;
}
Problem H : Tarun and the rolling circle
Author : Its_Tarun
In 1 step, we can move the center by any distance $$$x \in (0, 2r]$$$ by choosing an appropriate rotation angle $$$\theta = 2 \arcsin\left(\frac{x}{2r}\right)$$$.Therefore, if $$$d \% 2r \neq 0$$$, we take $$$\lfloor \frac{d}{2r} \rfloor$$$ steps of length $$$2r$$$ plus 1 smaller step of length $$$d \bmod 2r$$$, totaling $$$\lceil \frac{d}{2r} \rceil$$$ steps.
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define loop(i, n) for (int i = 0; i < n; i++)
#define print_vec(a) for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
#define endl '\n'
signed main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int r, x, y, xf, yf;
cin >> r >> x >> y >> xf >> yf;
int dx = xf - x;
int dy = yf - y;
int d2 = dx*dx + dy*dy;
double d = sqrtl(d2);
int ans = ceil(d/(2.0*r));
cout << ans << "\n";
return 0;
}
Problem I : Dewansh and the Secret Numbers
Author : JAS1123
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void solve() {
vector<long long> x(4);
for (int i = 0; i < 4; ++i) {
cin >> x[i];
}
sort(x.begin(), x.end());
// S = x[3] = a + b + c
long long a = x[3] - x[2];
long long b = x[3] - x[1];
long long c = x[3] - x[0];
cout << a << " " << b << " " << c << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
solve();
return 0;
}
Problem J : Jai's Permutation
Author : JAS1123
We construct the array starting with $$$P_1 = 1$$$. Each subsequent term $$$P_i$$$ ($$$1 \lt i \le N$$$) is formed by alternatingly applying step sizes (jumps) of $$$N$$$ and $$$N+2$$$:
$$$P_i = \vert{}N - P_{i-1}\vert{}$$$ if $$$i$$$ is odd,
$$$P_i = \vert{}(N + 2) - P_{i-1}\vert{}$$$ if $$$i$$$ is even.
Modulo $$$(N+1)$$$, notice that:
$$$N \equiv -1 \pmod{N+1}$$$
$$$N+2 \equiv +1 \pmod{N+1}$$$
2. Jump Sum Analysis ($$$L$$$):
For a contiguous block of length $$$k$$$, the jump sum $$$L_k$$$ alternates between terms of $$$N$$$ and $$$N+2$$$. The possible jump sums $$$L$$$ take two forms:
$$$\text{Type 1 (starts with } N \text{)}: N + (N+2) + N + (N+2) + \dots$$$
$$$\text{Type 2 (starts with } N+2 \text{)}: (N+2) + N + (N+2) + N + \dots$$$
For example, when $$$k = 3$$$:
$$$\text{Type 1: } N + (N+2) + N = 3N + 2$$$
$$$\text{Type 2: } (N+2) + N + (N+2) = 3N + 4$$$
Let L be the above value
3. Parity & Impossibility Proof:
Let's analyze $$$L$$$ and $$$N+1$$$ based on the parity of $$$N$$$:
It will be different in both the cases either n = even or odd which implies L%(N+1) can never be equals to zero
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define loop(i, n) for (int i = 0; i < n; i++)
#define print_vec(a) for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
#define endl '\n'
signed main() {
int t=1;
// cin >> t;
while (t--) {
int n; cin >> n;
int s = (n*(n+1))/2;
if(s%(n+1)){
vi ans(n);
ans[0] = 1;
for(int i=1;i<n;i++){
if(i&1) ans[i] = abs(n-ans[i-1]);
else ans[i] = abs(n+2-ans[i-1]);
}
print_vec(ans);
cout<<endl;
}else cout<<-1<<endl;
}
return 0;
}
