1043F-Make It One
Solved it using binary search over \(1\) to \(N\). But it wasnt necessary as it can be seen that if the gcd of some subset is \(1\) where \(A_i \leq 300,000\), then the size of that subset can be maximum \(7\) (so bruteforce over \(1\) to \(7\) would have worked).
Proof: It’s \(7\) because if we take small primes greedily and making their gcd not equal to \(1\), then after \(8^{th}\) element, it would exceed \(300,000\).
1271E-Common Number
Required \(2\) different binary searches for odd and even number, but found out that.. it’s not necessary to do \(2\) seperate searches. As, we can simply to do binary search for even numbers and check if \(2\cdot k+1\) satifies or not.
1
2
3
4
5
| for(int bits = 60; bits>=0; bits--)
if(func(answer + (1LL<<bits)) >= K)
answer += 1LL<<bits;
// always use 1LL << bits " for integers not fitting in int (32 bits)"
|
This way of binary search first goes on with even number and at the end checks if we can add \(1\) or not. So, it was ideal for this question.
BANQUNT-Banned Quotient
Got the main idea during contest, but didn’t knew how to count the number of groups (of size \(p\)), for this the whole segement \([1, N]\) can be divided into segments \([L_i, R_i]\) where every group starting from a number in these segments ( will have some particular size \(p\)), and hence we can calculate the number of numbers which aren’t divisible by \(K\).
EZRMQ-Carry Bed
Some new ideas used in this problem -> Barricade DP and converting the given array into binary tree such that \(LCA(u, v)\) would be the index of element which holds the maxmimum value in range \([u, v]\). And then doing barricade kinda DP on the given binary tree.
Also, the main thing for complexity is it’s \(O(N^2)\), as each pair of nodes is evaluted just once while considering their \(LCA\).
1
2
3
4
5
6
7
8
9
10
11
| int construct_tree(int l, int r){
if(r<l){
return -1;
}
int in = l;
for(int i=l;i<=r;i++)
if(v[i]>v[in]) in = i;
int vs[2] = {construct_tree(l, in-1),construct_tree(in+1,r)};
forn(i,2) if(vs[i]!=-1) adj[in].pb(vs[i]);
return in;
}
|
HXR-Xor Jar Muluk Tar
Simple Problem related to Matrix Exponentiation with XOR “ rather than addition “, to solve it efficiently, we can maintain bitsets (both Rows and Columns) and calculate Matrix multiplication.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| bitset<N> row[MAXN], col[MAXN];
bitset<N> mrow[MAXN], mcol[MAXN];
void mul_mat(bitset<N> *r, bitset<N> *c, bitset<N> *c2){
bitset<N> rx[MAXN], cx[MAXN];
forn(i,n)
forn(j,n){
rx[i][j] = cx[j][i] = (r[i]&c2[j]).count()&1;
}
forn(i,n) r[i] = rx[i], c[i] = cx[i];
}
void expo(int k){
forn(i,n) mrow[i][i] = mcol[i][i] = 1;
while(k){
if(k&1) mul_mat(mrow,mcol,col);
mul_mat(row,col,col);
k>>=1;
}
}
|