Welcome to the Editorial of [IPC-1 (2025-26)](https://mirror.codeforces.com/contestInvitation/3565b9f462a1f3a169fadc04e3740536d3b0a313).↵
↵
[A. Balance-Array](https://mirror.codeforces.com/gym/633555/problem/A)↵
------------------↵
Author:[user:justplaygame,2025-09-13]↵
↵
<spoiler summary="Problem Tags">↵
Math, Implementation↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
First check if the sum of the array is divisible by its size.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
If not, think about removing one element and what happens to the sum and the size.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
The element you remove must have the right remainder when divided by (n−1).↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
We are given an array of size n with total sum S. If S is divisible by n, the array is already balanced and the answer is "YES". Otherwise, we can try deleting one element ai. After deletion, the new sum becomes S — ai and the new size becomes n — 1. For the new array to be balanced, (S — a[i]) must be divisible by (n — 1), which is the same as saying that ai must have the same remainder as S when divided by (n — 1). Thus, it is enough to check if there exists at least one element such that a[i] % (n — 1) == S % (n — 1). A special case is when n = 1, where the answer is always "YES" since deleting the single element leaves an empty array, which is considered balanced. The solution only requires scanning the array once, giving a time complexity of O(n) per test case.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) {↵
int n;↵
cin >> n;↵
vector<long long> a(n);↵
long long S = 0;↵
↵
// Read the array and calculate total sum S↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
S += a[i];↵
}↵
↵
// Special case: if array has only 1 element,↵
// we can always remove it -> empty array is balanced↵
if (n == 1) {↵
cout << "YES\n";↵
continue;↵
}↵
↵
// Case 1: Already balanced (S % n == 0)↵
if (S % n == 0) {↵
cout << "YES\n";↵
continue;↵
}↵
↵
// Case 2: Try deleting one element↵
bool ok = false;↵
for (int i = 0; i < n; i++) {↵
// After removing a[i], check if new array is balanced↵
// Condition: (S - a[i]) % (n - 1) == 0↵
if ((S - a[i]) % (n - 1) == 0) {↵
ok = true;↵
break;↵
}↵
}↵
↵
cout << (ok ? "YES\n" : "NO\n");↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[B. Fruit Dish](https://mirror.codeforces.com/gym/633555/problem/B)↵
------------------↵
Author:[user:Krish_M,2025-09-13]↵
↵
<spoiler summary="Problem Tags">↵
Sorting + greedy↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
We always want to choose the cheapest item available.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Think of data structure used to maintain the cheapest item.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Use Minheap↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Push all the elements into a minheap while also storing their index. Then pop out the cheapest fruit and we buy it (decrease the remaining budget). Then we push the updated price of the fruit back into the heap. The updated price = price of fruit + index.↵
↵
We repeat the above process till the cheapest fruit that we get is costlier than the remaining budget.↵
↵
↵
Time Complexity :- Initially one might think that we can get TLE because budget <= 1e9.↵
↵
But lets consider a worst case scenario :- ↵
B = 1e9↵
N = 1↵
A[1] = 1↵
In this case we add in the series 1 + 2+ 3 + 4 + — — — — +x such that x is the last price at which we buy.↵
↵
Here we can use the formula↵
x*(x+1)/2 <= B.↵
↵
So approximately x = sqrt(B) ~ sqrt(1e9) ~ 1e5↵
↵
Also x is the number of times we pop an element from the heap and add another so the final time complexity :- ↵
↵
O(sqrt(B)*log(n)).↵
↵
Space complexity = O(n). We only need to use the space used in the heap. ↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <queue>↵
↵
using namespace std;↵
↵
int main() {↵
/* I might use long long when int works and I suggest at least when learning competitive programming you should ignore space complexity most of the time.↵
Not that it is not important but currently let's focus on problem solving. */↵
↵
long long B;↵
cin >> B;↵
↵
int n;↵
cin >> n;↵
↵
vector<long long> a(n); // using long long for safety↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
}↵
↵
// Min heap declaration↵
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;↵
↵
for (int i = 0; i < n; ++i) {↵
pq.push({a[i], i + 1}); // pushing all the elements↵
}↵
↵
long long ans = 0;↵
while (!pq.empty()) {↵
if (B < pq.top().first) { // base condition when cheapest > remaining budget↵
break;↵
} else {↵
long long cur = pq.top().first; // get the cheapest fruit↵
long long ind = pq.top().second; // get the index↵
pq.pop(); // remove the chosen fruit↵
↵
B -= cur; // decrease budget↵
++ans; // One more fruit bought↵
↵
pq.push({cur + ind, ind}); // Update the minheap with new value↵
}↵
}↵
↵
cout << ans << endl; // Done output the answer↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[C. The AND Lock](https://mirror.codeforces.com/gym/633555/problem/C)↵
------------------↵
Author:[user:THE_DARKHORSE,2025-09-13]↵
↵
<spoiler summary="Problem Tags">↵
Bitmask, Data structure, Constructive algorithm, Math↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
Think about the bitwise AND condition for a query (l, r, q).↵
If a bit is 1 in q, then every element in [l, r] must have that bit set.↵
If a bit is 0 in q, then at least one element in [l, r] must have that bit unset.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Can you use difference array concept?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Key Observations↵
↵
For the bitwise AND of numbers in a range [l, r] to equal q, two properties must hold. Every bit that is set in q must also be set in all numbers within the segment [l, r]. Also, every bit that is not set in q must be absent in at least one number within the segment [l, r]. This allows for bit-by-bit thinking. Instead of dealing with entire numbers, we can check the conditions independently for each of the 30 bits. If a query requires bit j to be 1, we must set bit j to 1 for all positions in the range [l, r]. If a query requires bit j to be 0, it simply means that not all positions in the range [l, r] can have bit j set to 1.↵
↵
Constructive Strategy↵
↵
The strategy is to first force all required 1s. We can use a difference array, pref[j][i], to mark ranges where a bit must be set. For each query (l, r, q) and each bit j, if the j-th bit of q is 1, we increment pref[j][l] and decrement pref[j][r+1]. After computing prefix sums for each bit, a value of pref[j][i] > 0 means bit j must be set at position i.↵
↵
Next, we build a candidate array. For each position i, the value A[i] is formed by setting all bits j for which pref[j][i] is greater than 0.↵
↵
Finally, a verification step is needed. Our constructed array satisfies the conditions for bits that must be 1, but it might accidentally violate a condition where a bit needed to be 0. So, we must re-check all original queries. For each query (l, r, q), we compute the bitwise AND of the elements in our constructed array from l to r. If it does not match q, then an answer is not possible. If all queries match, we have a valid array.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#define all(x) (x).begin(), (x).end()↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
↵
using ull = unsigned long long;↵
using ll = long long;↵
template <typename T> using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
const int mod = 1e9 + 7;↵
const int inf = 2e9 + 5;↵
const int N = 1e5 + 5;↵
↵
int n, m, pref[30][N];↵
vector<pair<pair<int, int>, int>> queries;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
cin >> n >> m;↵
for (int i = 0; i < m; i++) {↵
int l, r, q;↵
cin >> l >> r >> q;↵
↵
for (int j = 0; j < 30; j++) {↵
if (q & (1 << j)) {↵
pref[j][l]++;↵
pref[j][r+1]--;↵
}↵
}↵
queries.push_back({{l, r}, q});↵
}↵
↵
for (int i = 0; i < 30; i++) {↵
for (int j = 1; j <= n; j++)↵
pref[i][j] += pref[i][j-1];↵
}↵
↵
for (int i = 0; i < 30; i++) {↵
for (int j = 1; j <= n; j++)↵
pref[i][j] = (pref[i][j] > 0);↵
}↵
↵
for (int i = 0; i < 30; i++) {↵
for (int j = 1; j <= n; j++)↵
pref[i][j] += pref[i][j-1];↵
}↵
↵
for (auto &p : queries) {↵
int l = p.first.first, r = p.first.second, q = p.second;↵
int ans = 0;↵
↵
for (int i = 0; i < 30; i++) {↵
if (pref[i][r] - pref[i][l-1] == r - l + 1)↵
ans |= (1 << i);↵
}↵
↵
if (ans != q) {↵
cout << "NO\n";↵
return 0;↵
}↵
}↵
↵
cout << "YES\n";↵
for (int i = 1; i <= n; i++) {↵
int ans = 0;↵
for (int j = 0; j < 30; j++) {↵
if (pref[j][i] - pref[j][i-1] == 1)↵
ans |= (1 << j);↵
}↵
cout << ans << " ";↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[D. Trusting the Blind Lawyer](https://mirror.codeforces.com/gym/633555/problem/D)↵
------------------↵
Author:[user:MattMurdock8,2025-09-13]↵
↵
<spoiler summary="Problem Tags">↵
Graphs, DFS, BFS, Grid traversal↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
Try to think from the end position E instead of the start S.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Imagine a situation like a narrow tunnel — once you enter, you can give the wrong direction to manipulate Elektra into reaching the exit.↵
Example:↵
↵
~~~~~↵
#####↵
#E..#↵
###.#↵
###S#↵
#####↵
~~~~~↵
↵
↵
↵
If we give the directions DDDR, Elektra will still reach E. Hence, in this case, we can set k = 0.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
From E, only extend into cells that have at most one free neighbor, and mark them. These cells form such tunnel-like paths. Finally, find the shortest distance from S to any marked position. If it’s not possible to reach, then the answer is -1.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
To solve the problem, we first read the grid and identify the positions of the start S and the exit E. The idea is to work backward from the exit rather than forward from the start. From the exit E, we perform a depth-first search (DFS) into neighboring '.' cells. However, this DFS is restricted: we only continue into a cell if it has at most one open neighbor. This condition ensures that the traversal follows tunnel-like paths without branching. All such valid cells are marked with '+'.↵
Once this marking step is done, we check the position of S. If the start cell is itself marked '+', it means Elektra can be manipulated to the exit immediately, so the answer is 0. Otherwise, we need to compute how far S is from any marked path or directly from E. For this, we use a breadth-first search (BFS) starting from S. The BFS explores all adjacent cells that are either '.', '+', or E, and maintains a distance matrix to track the number of steps taken.↵
The BFS terminates as soon as it reaches a marked cell or the exit E, and at that point we print the corresponding distance. If no such path exists, the answer is -1. This process is repeated independently for each test case.↵
↵
Complexity:↵
DFS and BFS each run in O(n*m) since every cell is visited at most once.↵
↵
Memory usage is also O(n*m) for storing the grid and distance matrix.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
typedef long long ll;↵
typedef vector<string> vstr;↵
↵
bool ch(ll x, ll y, vstr& s) {↵
ll count = 0;↵
ll n = s.size();↵
ll m = s[0].size();↵
↵
if ((x-1 >= 0) && (s[x-1][y] == '.')) count++;↵
if ((y-1 >= 0) && (s[x][y-1] == '.')) count++;↵
if ((x+1 < n) && (s[x+1][y] == '.')) count++;↵
if ((y+1 < m) && (s[x][y+1] == '.')) count++;↵
↵
return (count <= 1);↵
}↵
↵
void dfs(ll x , ll y , vstr &s) {↵
if (ch(x,y,s)) {↵
s[x][y] = '+';↵
ll n = s.size();↵
ll m = s[0].size();↵
↵
if ((x-1 >= 0) && s[x-1][y] == '.' ) dfs(x-1,y,s);↵
if ((y-1 >= 0) && s[x][y-1] == '.' ) dfs(x,y-1,s);↵
if ((x+1 < n) && s[x+1][y] == '.' ) dfs(x+1,y,s);↵
if ((y+1 < m) && s[x][y+1] == '.' ) dfs(x,y+1,s);↵
}↵
}↵
↵
ll bfs(vector<string>& s , ll xs , ll ys , ll n , ll m) {↵
vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};↵
queue<pair<int,int>> q;↵
vector<vector<int>> dist(n, vector<int>(m, -1));↵
↵
q.push({xs, ys});↵
dist[xs][ys] = 0;↵
↵
while (!q.empty()) {↵
auto [x, y] = q.front();↵
q.pop();↵
↵
if (s[x][y] == '+' || s[x][y] == 'E') {↵
return dist[x][y];↵
}↵
↵
for (auto [dx, dy] : directions) {↵
int nx = x + dx, ny = y + dy;↵
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {↵
if (s[nx][ny] == '.' || s[nx][ny] == '+' || s[nx][ny] == 'E') {↵
dist[nx][ny] = dist[x][y] + 1;↵
q.push({nx, ny});↵
}↵
}↵
}↵
}↵
return -1;↵
}↵
↵
void solve() {↵
ll n, m;↵
cin >> n >> m;↵
vstr s(n);↵
for (ll i = 0; i < n; i++) cin >> s[i];↵
↵
ll xs, ys, xe, ye;↵
for (ll i = 0; i < n; i++) {↵
for (ll j = 0; j < m; j++) {↵
if (s[i][j] == 'S') {↵
xs = i; ys = j;↵
s[i][j] = '.';↵
}↵
if (s[i][j] == 'E') {↵
xe = i; ye = j;↵
}↵
}↵
}↵
↵
if ((xe-1 >= 0) && s[xe-1][ye] == '.') dfs(xe-1,ye,s);↵
if ((ye-1 >= 0) && s[xe][ye-1] == '.') dfs(xe,ye-1,s);↵
if ((xe+1 < n) && s[xe+1][ye] == '.') dfs(xe+1,ye,s);↵
if ((ye+1 < m) && s[xe][ye+1] == '.') dfs(xe,ye+1,s);↵
↵
if (s[xs][ys] == '+') {↵
cout << 0;↵
} else {↵
s[xs][ys] = 'S';↵
cout << bfs(s , xs , ys , n , m);↵
}↵
cout << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
ll tt = 1;↵
cin >> tt;↵
while (tt--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
[E. Lost in Time (GCD Pairs)](https://mirror.codeforces.com/gym/633555/problem/E)↵
------------------↵
Author:[user:BLACKCOFFEE-420,2025-09-13]↵
↵
<spoiler summary="Problem Tags">↵
Number Theory, Inclusion-Exclusion, Mobius Function, GCD ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
If gcd(a[i], a[j]) = k, then both a[i] and a[j] must be divisible by k. ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Divide all numbers by k. Now the problem reduces to counting pairs with gcd = 1. ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
To count gcd = 1 pairs, we can use the Möbius function (μ) and inclusion-exclusion principle.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Step 1: Normalization ↵
Since we need gcd(a[i], a[j]) = k, we first check only numbers divisible by k. ↵
Let’s define b[i] = a[i] / k for all a[i] divisible by k. ↵
Now, our task is:Count pairs (i, j) such that gcd(b[i], b[j]) = 1. We will solve this using inclusion exclusion principle but it can also be solved using mobius function↵
↵
Step 2: Calculating coprime pairs(using inclusion exclusion)↵
The video link for Calculating coprime pairs:↵
https://www.youtube.com/live/znENoVN73G8?t=4207s↵
↵
Complexity Analysis↵
n=size of the array and N=size of freq and prs vector↵
Time complexity: O(n + N log N)↵
Space complexity: O(n + N)↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
using namespace std;↵
↵
void solve() {↵
long long n, k;↵
cin >> n >> k;↵
↵
vector<long long> a(n);↵
for (long long i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
↵
const long long N = 1000016; // 1e6 + 16↵
vector<long long> freq(N, 0);↵
↵
for (long long i = 0; i < n; i++) {↵
freq[a[i]]++;↵
}↵
↵
vector<long long> prs(N, 0);↵
↵
for (long long i = 1; i < N; i++) {↵
for (long long j = 2 * i; j < N; j += i) {↵
freq[i] += freq[j];↵
}↵
}↵
↵
for (long long i = N - 1; i > 0; i--) {↵
prs[i] = (freq[i] * (freq[i] - 1)) / 2;↵
for (long long j = 2 * i; j < N; j += i) {↵
prs[i] -= prs[j];↵
}↵
}↵
↵
cout << prs[k] << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t = 1;↵
// cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[A. Balance-Array](https://mirror.codeforces.com/gym/633555/problem/A)↵
------------------↵
Author:[user:justplaygame,2025-09-13]↵
↵
<spoiler summary="Problem Tags">↵
Math, Implementation↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
First check if the sum of the array is divisible by its size.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
If not, think about removing one element and what happens to the sum and the size.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
The element you remove must have the right remainder when divided by (n−1).↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
↵
We are given an array of size n with total sum S. If S is divisible by n, the array is already balanced and the answer is "YES". Otherwise, we can try deleting one element ai. After deletion, the new sum becomes S — ai and the new size becomes n — 1. For the new array to be balanced, (S — a[i]) must be divisible by (n — 1), which is the same as saying that ai must have the same remainder as S when divided by (n — 1). Thus, it is enough to check if there exists at least one element such that a[i] % (n — 1) == S % (n — 1). A special case is when n = 1, where the answer is always "YES" since deleting the single element leaves an empty array, which is considered balanced. The solution only requires scanning the array once, giving a time complexity of O(n) per test case.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) {↵
int n;↵
cin >> n;↵
vector<long long> a(n);↵
long long S = 0;↵
↵
// Read the array and calculate total sum S↵
for (int i = 0; i < n; i++) {↵
cin >> a[i];↵
S += a[i];↵
}↵
↵
// Special case: if array has only 1 element,↵
// we can always remove it -> empty array is balanced↵
if (n == 1) {↵
cout << "YES\n";↵
continue;↵
}↵
↵
// Case 1: Already balanced (S % n == 0)↵
if (S % n == 0) {↵
cout << "YES\n";↵
continue;↵
}↵
↵
// Case 2: Try deleting one element↵
bool ok = false;↵
for (int i = 0; i < n; i++) {↵
// After removing a[i], check if new array is balanced↵
// Condition: (S - a[i]) % (n - 1) == 0↵
if ((S - a[i]) % (n - 1) == 0) {↵
ok = true;↵
break;↵
}↵
}↵
↵
cout << (ok ? "YES\n" : "NO\n");↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[B. Fruit Dish](https://mirror.codeforces.com/gym/633555/problem/B)↵
------------------↵
Author:[user:Krish_M,2025-09-13]↵
↵
<spoiler summary="Problem Tags">↵
Sorting + greedy↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
We always want to choose the cheapest item available.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Think of data structure used to maintain the cheapest item.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
Use Minheap↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Push all the elements into a minheap while also storing their index. Then pop out the cheapest fruit and we buy it (decrease the remaining budget). Then we push the updated price of the fruit back into the heap. The updated price = price of fruit + index.↵
↵
We repeat the above process till the cheapest fruit that we get is costlier than the remaining budget.↵
↵
↵
Time Complexity :- Initially one might think that we can get TLE because budget <= 1e9.↵
↵
But lets consider a worst case scenario :- ↵
B = 1e9↵
N = 1↵
A[1] = 1↵
In this case we add in the series 1 + 2+ 3 + 4 + — — — — +x such that x is the last price at which we buy.↵
↵
Here we can use the formula↵
x*(x+1)/2 <= B.↵
↵
So approximately x = sqrt(B) ~ sqrt(1e9) ~ 1e5↵
↵
Also x is the number of times we pop an element from the heap and add another so the final time complexity :- ↵
↵
O(sqrt(B)*log(n)).↵
↵
Space complexity = O(n). We only need to use the space used in the heap. ↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
#include <queue>↵
↵
using namespace std;↵
↵
int main() {↵
/* I might use long long when int works and I suggest at least when learning competitive programming you should ignore space complexity most of the time.↵
Not that it is not important but currently let's focus on problem solving. */↵
↵
long long B;↵
cin >> B;↵
↵
int n;↵
cin >> n;↵
↵
vector<long long> a(n); // using long long for safety↵
for (int i = 0; i < n; ++i) {↵
cin >> a[i];↵
}↵
↵
// Min heap declaration↵
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;↵
↵
for (int i = 0; i < n; ++i) {↵
pq.push({a[i], i + 1}); // pushing all the elements↵
}↵
↵
long long ans = 0;↵
while (!pq.empty()) {↵
if (B < pq.top().first) { // base condition when cheapest > remaining budget↵
break;↵
} else {↵
long long cur = pq.top().first; // get the cheapest fruit↵
long long ind = pq.top().second; // get the index↵
pq.pop(); // remove the chosen fruit↵
↵
B -= cur; // decrease budget↵
++ans; // One more fruit bought↵
↵
pq.push({cur + ind, ind}); // Update the minheap with new value↵
}↵
}↵
↵
cout << ans << endl; // Done output the answer↵
↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
[C. The AND Lock](https://mirror.codeforces.com/gym/633555/problem/C)↵
------------------↵
Author:[user:THE_DARKHORSE,2025-09-13]↵
↵
<spoiler summary="Problem Tags">↵
Bitmask, Data structure, Constructive algorithm, Math↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
Think about the bitwise AND condition for a query (l, r, q).↵
If a bit is 1 in q, then every element in [l, r] must have that bit set.↵
If a bit is 0 in q, then at least one element in [l, r] must have that bit unset.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Can you use difference array concept?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Key Observations↵
↵
For the bitwise AND of numbers in a range [l, r] to equal q, two properties must hold. Every bit that is set in q must also be set in all numbers within the segment [l, r]. Also, every bit that is not set in q must be absent in at least one number within the segment [l, r]. This allows for bit-by-bit thinking. Instead of dealing with entire numbers, we can check the conditions independently for each of the 30 bits. If a query requires bit j to be 1, we must set bit j to 1 for all positions in the range [l, r]. If a query requires bit j to be 0, it simply means that not all positions in the range [l, r] can have bit j set to 1.↵
↵
Constructive Strategy↵
↵
The strategy is to first force all required 1s. We can use a difference array, pref[j][i], to mark ranges where a bit must be set. For each query (l, r, q) and each bit j, if the j-th bit of q is 1, we increment pref[j][l] and decrement pref[j][r+1]. After computing prefix sums for each bit, a value of pref[j][i] > 0 means bit j must be set at position i.↵
↵
Next, we build a candidate array. For each position i, the value A[i] is formed by setting all bits j for which pref[j][i] is greater than 0.↵
↵
Finally, a verification step is needed. Our constructed array satisfies the conditions for bits that must be 1, but it might accidentally violate a condition where a bit needed to be 0. So, we must re-check all original queries. For each query (l, r, q), we compute the bitwise AND of the elements in our constructed array from l to r. If it does not match q, then an answer is not possible. If all queries match, we have a valid array.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
#include <ext/pb_ds/assoc_container.hpp>↵
#define all(x) (x).begin(), (x).end()↵
↵
using namespace __gnu_pbds;↵
using namespace std;↵
↵
using ull = unsigned long long;↵
using ll = long long;↵
template <typename T> using ordered_set = tree<T, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;↵
↵
const int mod = 1e9 + 7;↵
const int inf = 2e9 + 5;↵
const int N = 1e5 + 5;↵
↵
int n, m, pref[30][N];↵
vector<pair<pair<int, int>, int>> queries;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr); cout.tie(nullptr);↵
↵
cin >> n >> m;↵
for (int i = 0; i < m; i++) {↵
int l, r, q;↵
cin >> l >> r >> q;↵
↵
for (int j = 0; j < 30; j++) {↵
if (q & (1 << j)) {↵
pref[j][l]++;↵
pref[j][r+1]--;↵
}↵
}↵
queries.push_back({{l, r}, q});↵
}↵
↵
for (int i = 0; i < 30; i++) {↵
for (int j = 1; j <= n; j++)↵
pref[i][j] += pref[i][j-1];↵
}↵
↵
for (int i = 0; i < 30; i++) {↵
for (int j = 1; j <= n; j++)↵
pref[i][j] = (pref[i][j] > 0);↵
}↵
↵
for (int i = 0; i < 30; i++) {↵
for (int j = 1; j <= n; j++)↵
pref[i][j] += pref[i][j-1];↵
}↵
↵
for (auto &p : queries) {↵
int l = p.first.first, r = p.first.second, q = p.second;↵
int ans = 0;↵
↵
for (int i = 0; i < 30; i++) {↵
if (pref[i][r] - pref[i][l-1] == r - l + 1)↵
ans |= (1 << i);↵
}↵
↵
if (ans != q) {↵
cout << "NO\n";↵
return 0;↵
}↵
}↵
↵
cout << "YES\n";↵
for (int i = 1; i <= n; i++) {↵
int ans = 0;↵
for (int j = 0; j < 30; j++) {↵
if (pref[j][i] - pref[j][i-1] == 1)↵
ans |= (1 << j);↵
}↵
cout << ans << " ";↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
[D. Trusting the Blind Lawyer](https://mirror.codeforces.com/gym/633555/problem/D)↵
------------------↵
Author:[user:MattMurdock8,2025-09-13]↵
↵
<spoiler summary="Problem Tags">↵
Graphs, DFS, BFS, Grid traversal↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
Try to think from the end position E instead of the start S.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Imagine a situation like a narrow tunnel — once you enter, you can give the wrong direction to manipulate Elektra into reaching the exit.↵
Example:↵
↵
~~~~~↵
#####↵
#E..#↵
###.#↵
###S#↵
#####↵
~~~~~↵
↵
↵
↵
If we give the directions DDDR, Elektra will still reach E. Hence, in this case, we can set k = 0.↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
From E, only extend into cells that have at most one free neighbor, and mark them. These cells form such tunnel-like paths. Finally, find the shortest distance from S to any marked position. If it’s not possible to reach, then the answer is -1.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
To solve the problem, we first read the grid and identify the positions of the start S and the exit E. The idea is to work backward from the exit rather than forward from the start. From the exit E, we perform a depth-first search (DFS) into neighboring '.' cells. However, this DFS is restricted: we only continue into a cell if it has at most one open neighbor. This condition ensures that the traversal follows tunnel-like paths without branching. All such valid cells are marked with '+'.↵
Once this marking step is done, we check the position of S. If the start cell is itself marked '+', it means Elektra can be manipulated to the exit immediately, so the answer is 0. Otherwise, we need to compute how far S is from any marked path or directly from E. For this, we use a breadth-first search (BFS) starting from S. The BFS explores all adjacent cells that are either '.', '+', or E, and maintains a distance matrix to track the number of steps taken.↵
The BFS terminates as soon as it reaches a marked cell or the exit E, and at that point we print the corresponding distance. If no such path exists, the answer is -1. This process is repeated independently for each test case.↵
↵
Complexity:↵
DFS and BFS each run in O(n*m) since every cell is visited at most once.↵
↵
Memory usage is also O(n*m) for storing the grid and distance matrix.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
typedef long long ll;↵
typedef vector<string> vstr;↵
↵
bool ch(ll x, ll y, vstr& s) {↵
ll count = 0;↵
ll n = s.size();↵
ll m = s[0].size();↵
↵
if ((x-1 >= 0) && (s[x-1][y] == '.')) count++;↵
if ((y-1 >= 0) && (s[x][y-1] == '.')) count++;↵
if ((x+1 < n) && (s[x+1][y] == '.')) count++;↵
if ((y+1 < m) && (s[x][y+1] == '.')) count++;↵
↵
return (count <= 1);↵
}↵
↵
void dfs(ll x , ll y , vstr &s) {↵
if (ch(x,y,s)) {↵
s[x][y] = '+';↵
ll n = s.size();↵
ll m = s[0].size();↵
↵
if ((x-1 >= 0) && s[x-1][y] == '.' ) dfs(x-1,y,s);↵
if ((y-1 >= 0) && s[x][y-1] == '.' ) dfs(x,y-1,s);↵
if ((x+1 < n) && s[x+1][y] == '.' ) dfs(x+1,y,s);↵
if ((y+1 < m) && s[x][y+1] == '.' ) dfs(x,y+1,s);↵
}↵
}↵
↵
ll bfs(vector<string>& s , ll xs , ll ys , ll n , ll m) {↵
vector<pair<int,int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};↵
queue<pair<int,int>> q;↵
vector<vector<int>> dist(n, vector<int>(m, -1));↵
↵
q.push({xs, ys});↵
dist[xs][ys] = 0;↵
↵
while (!q.empty()) {↵
auto [x, y] = q.front();↵
q.pop();↵
↵
if (s[x][y] == '+' || s[x][y] == 'E') {↵
return dist[x][y];↵
}↵
↵
for (auto [dx, dy] : directions) {↵
int nx = x + dx, ny = y + dy;↵
if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1) {↵
if (s[nx][ny] == '.' || s[nx][ny] == '+' || s[nx][ny] == 'E') {↵
dist[nx][ny] = dist[x][y] + 1;↵
q.push({nx, ny});↵
}↵
}↵
}↵
}↵
return -1;↵
}↵
↵
void solve() {↵
ll n, m;↵
cin >> n >> m;↵
vstr s(n);↵
for (ll i = 0; i < n; i++) cin >> s[i];↵
↵
ll xs, ys, xe, ye;↵
for (ll i = 0; i < n; i++) {↵
for (ll j = 0; j < m; j++) {↵
if (s[i][j] == 'S') {↵
xs = i; ys = j;↵
s[i][j] = '.';↵
}↵
if (s[i][j] == 'E') {↵
xe = i; ye = j;↵
}↵
}↵
}↵
↵
if ((xe-1 >= 0) && s[xe-1][ye] == '.') dfs(xe-1,ye,s);↵
if ((ye-1 >= 0) && s[xe][ye-1] == '.') dfs(xe,ye-1,s);↵
if ((xe+1 < n) && s[xe+1][ye] == '.') dfs(xe+1,ye,s);↵
if ((ye+1 < m) && s[xe][ye+1] == '.') dfs(xe,ye+1,s);↵
↵
if (s[xs][ys] == '+') {↵
cout << 0;↵
} else {↵
s[xs][ys] = 'S';↵
cout << bfs(s , xs , ys , n , m);↵
}↵
cout << "\n";↵
}↵
↵
int main() {↵
ios_base::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
ll tt = 1;↵
cin >> tt;↵
while (tt--) {↵
solve();↵
}↵
return 0;↵
}↵
↵
~~~~~↵
</spoiler>↵
↵
↵
[E. Lost in Time (GCD Pairs)](https://mirror.codeforces.com/gym/633555/problem/E)↵
------------------↵
Author:[user:BLACKCOFFEE-420,2025-09-13]↵
↵
<spoiler summary="Problem Tags">↵
Number Theory, Inclusion-Exclusion, Mobius Function, GCD ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 1">↵
If gcd(a[i], a[j]) = k, then both a[i] and a[j] must be divisible by k. ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 2">↵
Divide all numbers by k. Now the problem reduces to counting pairs with gcd = 1. ↵
</spoiler>↵
↵
↵
<spoiler summary="Hint 3">↵
To count gcd = 1 pairs, we can use the Möbius function (μ) and inclusion-exclusion principle.↵
</spoiler>↵
↵
↵
<spoiler summary="Solution">↵
Step 1: Normalization ↵
Since we need gcd(a[i], a[j]) = k, we first check only numbers divisible by k. ↵
Let’s define b[i] = a[i] / k for all a[i] divisible by k. ↵
Now, our task is:Count pairs (i, j) such that gcd(b[i], b[j]) = 1. We will solve this using inclusion exclusion principle but it can also be solved using mobius function↵
↵
Step 2: Calculating coprime pairs(using inclusion exclusion)↵
The video link for Calculating coprime pairs:↵
https://www.youtube.com/live/znENoVN73G8?t=4207s↵
↵
Complexity Analysis↵
n=size of the array and N=size of freq and prs vector↵
Time complexity: O(n + N log N)↵
Space complexity: O(n + N)↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
~~~~~↵
#include <iostream>↵
#include <vector>↵
using namespace std;↵
↵
void solve() {↵
long long n, k;↵
cin >> n >> k;↵
↵
vector<long long> a(n);↵
for (long long i = 0; i < n; i++) {↵
cin >> a[i];↵
}↵
↵
const long long N = 1000016; // 1e6 + 16↵
vector<long long> freq(N, 0);↵
↵
for (long long i = 0; i < n; i++) {↵
freq[a[i]]++;↵
}↵
↵
vector<long long> prs(N, 0);↵
↵
for (long long i = 1; i < N; i++) {↵
for (long long j = 2 * i; j < N; j += i) {↵
freq[i] += freq[j];↵
}↵
}↵
↵
for (long long i = N - 1; i > 0; i--) {↵
prs[i] = (freq[i] * (freq[i] - 1)) / 2;↵
for (long long j = 2 * i; j < N; j += i) {↵
prs[i] -= prs[j];↵
}↵
}↵
↵
cout << prs[k] << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t = 1;↵
// cin >> t;↵
while (t--) {↵
solve();↵
}↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
