Hey there!
Thank you for being part of the ICPC India Prelims 2024! 🚀
I've put together hints and solutions for the problems to help you reflect on the challenges. As the contest admin, I even recorded myself solving the problems live — it's a mix of strategy, insights, and a behind-the-scenes look at my thought process.
🎥 Watch the video here: https://youtu.be/NsIj7CgDPY8
Let me know what you think, and feel free to share your thoughts or questions! 😊
The problems are ordered from easy to hard.
Unsatisfying Array
Hint
First, set all numbers to one. Increase if necessary.
Solution
t = int(input())
while t > 0:
t -= 1
n, k = map(int, input().split())
triplets = [[] for i in range(n + 1)]
while k > 0:
k -= 1
l, r, m = map(int, input().split())
triplets[m].append((l - 1, r)) # [l, r)
a = [1] * n
for i in range(1, n + 1):
for rng in triplets[i]:
if min(a[rng[0]:rng[1]]) == i:
a[rng[0]:rng[1]] = [i + 1] * (rng[1] - rng[0])
if n + 1 in a:
print(-1)
else:
print(*a)
AND Quest
Hint
Don't pick numbers that if you pick them, AND will not become k for sure. Pick everything else.
Solution
t = int(input())
while t > 0:
t -= 1
n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = []
cur = (1 << 30) - 1
for i in range(n):
if a[i] & k == k:
ans.append(i + 1)
cur &= a[i]
if cur == k:
print('YES', '\n', len(ans), '\n', *ans)
else:
print('NO')
Small Indices
Hint
Backtrack and dp both work.
Solution
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 100000;
int n, a[MAX_N], b[MAX_N];
int solve(int i = 0, int mx = INT_MIN, int level = INT_MIN) {
if (i == n)
return 0;
if (b[i] <= level || a[i] > level)
return solve(i + 1, max(mx, b[i]), max(level, mx + b[i])) + (b[i] <= level);
return max(solve(i + 1, max(mx, a[i]), max(level, mx + a[i])) + 1,
solve(i + 1, max(mx, b[i]), max(level, mx + b[i])));
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
for (int i = 0; i < n; ++i) {
cin >> b[i];
if (a[i] > b[i])
swap(a[i], b[i]);
}
cout << solve() << '\n';
}
}
Yet Another GCD Problem
Hint
Use some primes, and also 6.
Solution
MAX_N = 2000000
is_p = [True] * MAX_N
for i in range(2, MAX_N):
if not is_p[i]:
continue
for j in range(i * i, MAX_N, i):
is_p[j] = False
prs = [i for i in range(2, MAX_N) if is_p[i]]
t = int(input())
while t > 0:
t -= 1
n, k = map(int, input().split())
if k > n * (n - 1) / 2:
print(-1)
continue
ptr = len(prs) - 1
while n or k:
if k >= n - 1:
print(prs[ptr], end=' ')
ptr -= 1
k -= n - 1
n -= 1
else:
if ptr > 0:
ptr = 1
print(6, end=' ')
else:
print(2, end=' ')
n -= 1
print()
Equations
Hint
DSU, but hard!
Solution
// In the name of Allah.
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200000;
int p[MAX_N], val[MAX_N], k[MAX_N], rev[MAX_N];
// if p[i] == -1: a[i] = val[i]
// o.w. a[i] = k[i] + rev[i] * a[p[i]]
int root(int v) {
if (p[v] == -1)
return v;
int r = root(p[v]);
if (r == p[v])
return r;
// a[v] = k[v] + rev[v] * a[p[v]]
// a[p[v]] = k[p[v]] + rev[p[v]] * a[r]
// => a[v] = k[v] + rev[v] * k[p[v]] + rev[v] * rev[p[v]] * a[r]
// a[v] = k'[v] + rev'[v] * a[r]
k[v] += rev[v] * k[p[v]];
rev[v] *= rev[p[v]];
return p[v] = r;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
fill(p, p + n, -1);
fill(val, val + n, -1);
fill(rev, rev + n, 1);
while (q--) {
int t, i, j, qk;
cin >> t >> i >> j;
--i;
--j;
if (t == 1) {
cin >> qk;
// a[i] + a[j] = qk
int ri = root(i), rj = root(j);
// cerr << ri << ' ' << rj << '\n';
if (ri == rj) {
// cerr << "r: " << rev[i] << ' ' << rev[j] << '\n';
if (val[ri] != -1 || rev[i] != rev[j])
continue;
// a[i] = k[i] + rev[i] * a[ri]
// a[j] = k[j] + rev[j] * a[ri]
// => 2 * rev[i] * a[ri] = qk - k[i] - k[j]
// a[ri] = (qk - k[i] - k[j]) / (2 * rev[i])
// cerr << "found!\n";
val[ri] = (qk - k[i] - k[j]) / (2 * rev[i]);
}
else {
// Make ri parent of rj
// a[i] = k[i] + rev[i] * a[ri]
// a[j] = k[j] + rev[j] * a[rj]
if (val[rj] != -1) {
// k[i] + rev[i] * a[ri] + k[j] + rev[j] * a[rj] = qk
val[ri] = (qk - (k[i] + k[j] + rev[j] * val[rj])) * rev[i];
continue;
}
// a[rj] = k[rj] + rev[rj] * a[ri]
// a[rj] = (qk - (k[i] + rev[i] * a[ri] + k[j])) * rev[j]
// a[rj] = rev[j] * (qk - k[i] - k[j]) - rev[i] * rev[j] * a[ri]
k[rj] = rev[j] * (qk - k[i] - k[j]);
rev[rj] = -rev[i] * rev[j];
p[rj] = ri;
}
}
else {
int ri = root(i), rj = root(j);
if (val[ri] != -1 && val[rj] != -1)
cout << k[i] + rev[i] * val[ri] + k[j] + rev[j] * val[rj] << '\n';
else if (ri == rj && rev[i] != rev[j]) {
// a[i] = k[i] + rev[i] * a[ri]
// a[j] = k[j] + rev[j] * a[ri]
cout << k[i] + k[j] << '\n';
}
else
cout << "-1\n";
}
}
}
Thanks for the fast editorial.
There was a sudden rise in the number of submissions of small indices. Hope Codechef has a good plag checker.
Why was there a test case with K=0 in problem Yet Another GCD Problem? The constraint mentioned in the problem states that 1<=K<=1e9
At what testcase was your answer failing?
third
Apologies for this error. We will re-judge the solution which failed due to this and the penalties will be adjusted accordingly.
What about the time wasted because of that?
we were stuck on this problem for $$$58$$$ mins, this is not a small mistake? You can't make such mistakes in ICPC....
when will the problems be made available for practice [wanna submit some solutions]
[deleted]
umm , we came 2nd in our college and in top 100 overall, the first place team from our college had chosen amritapuri and one more region and we had only chosen amritapuri , so is there much chance of us getting selected or no? ;-;
+1
Amritapuri has more seats and 2 teams from the same institute cam get selected.
You have good really good chances as per the amritapuri selection process.
How can we run backtrack for n=3000??
What is the proof for Small Indices problem that the proposed backtracking solution works in O(n^2). Also could you share the dynamic programming solution of the same?
Update:
The proof is as follows:
b[i] > level (b[i] > sum of 2 previous max numbers) can only occur about O(logn) times.
So at O(logn) times we have 2 choices to explore and hence works in the given time complexity
Damn, wild to think brute force works. If someone would have just tried brute force, would work. I did think that it was possible to do so, but I couldn't prove that time complexity would be n**2.
I think someone randomly used GPT and it got accepted. That's why we might have as many solves as we did
In small indices, if the array size is n then elements of array are <= 2*n and not <= 6000. right? Arpa Enigma27
Yeah, I verified that with asserts
Thanks, got my mistake