A. Find Min Operations
By nishkarsh
How many operations will have $$$x = 0$$$.
Try $$$k = 2$$$.
Answer will be the number of ones in binary representation of $$$n$$$.
If $$$k$$$ is 1, we can only subtract 1 in each operation, and our answer will be $$$n$$$.
Now, first, it can be seen that we have to apply at least $$$n$$$ mod $$$k$$$ operations of subtracting $$$k^0$$$ (as all the other operations will not change the value of $$$n$$$ mod $$$k$$$). Now, once $$$n$$$ is divisible by $$$k$$$, solving the problem for $$$n$$$ is equivalent to solving the problem for $$$\frac{n}{k}$$$ as subtracting $$$k^0$$$ will be useless because if we apply the $$$k^0$$$ subtraction operation, then $$$n$$$ mod $$$k$$$ becomes $$$k-1$$$, and we have to apply $$$k-1$$$ more operations to make $$$n$$$ divisible by $$$k$$$ (as the final result, i.e., 0 is divisible by $$$k$$$). Instead of doing these $$$k$$$ operations of subtracting $$$k^0$$$, a single operation subtracting $$$k^1$$$ will do the job.
So, our final answer becomes the sum of the digits of $$$n$$$ in base $$$k$$$.
The complexity of the solution is $$$O(\log_{k}{n})$$$ per testcase.
#include <bits/stdc++.h>
using namespace std;
int find_min_oper(int n, int k){
if(k == 1) return n;
int ans = 0;
while(n){
ans += n%k;
n /= k;
}
return ans;
}
int main()
{
int t;
cin >> t;
while(t--){
int n,k;
cin >> n >> k;
cout << find_min_oper(n,k) << "\n";
}
return 0;
}
B. Brightness Begins
By nishkarsh
The final state of $$$i$$$th bulb (on or off) is independent of $$$n$$$.
The final state of the $$$i$$$th bulb tells us about the parity of number of divisors of $$$i$$$.
For any bulb $$$i$$$, its final state depends on the parity of the number of divisors of $$$i$$$. If $$$i$$$ has an even number of divisors, then bulb $$$i$$$ will be on; else it will be off. This translates to, if $$$i$$$ is not a perfect square, bulb $$$i$$$ will be on; else it will be off. So now the problem is to find the $$$k$$$th number which is not a perfect square. This can be done by binary searching the value of $$$n$$$ such that $$$n- \lfloor \sqrt{n} \rfloor = k$$$ or the direct formula $$$n$$$ = $$$\lfloor k + \sqrt{k} + 0.5 \rfloor$$$.
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
long long k, l = 1, r = 2e18;
cin >> k;
while(r-l > 1){
long long mid = (l+r)>>1;
long long n = mid - int(sqrtl(mid));
if(n >= k) r = mid;
else l = mid;
}
cout << r << "\n";
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int main(){
int t;
cin >> t;
while(t--){
long long k;
cin >> k;
cout << k + int(sqrtl(k) + 0.5) << "\n";
}
return 0;
}
C. Bitwise Balancing
By P.V.Sekhar
Try to find some independent operations/combinations.
The expression is independent for each digit in binary representation
The first observation is that the expression $$$a$$$|$$$b$$$ - $$$a$$$&$$$c = d$$$ is bitwise independent. That is, the combination of a tuple of bits of $$$a, b, and\ c$$$ corresponding to the same power of 2 will only affect the bit value of $$$d$$$ at that power of 2 only.
This is because:
We are performing subtraction, so extra carry won't be generated to the next power of 2.
Any tuple of bits of $$$a$$$, $$$b$$$, and $$$c$$$ corresponding to the same power of 2 won't result in -1 for that power of 2. As that would require $$$a|b$$$ to be zero and $$$a$$$&$$$c$$$ to be one. The former condition requires the bit of $$$a$$$ to be zero, while the latter requires it to be one, which is contradicting.
Now, let us consider all 8 cases of bits of a, b, c and the corresponding bit value of d in the following table:
So, clearly, for different bits of $$$b, c,$$$ and $$$d$$$, we can find the value of the corresponding bit in $$$a$$$, provided it is not the case when bit values of $$$b, c,$$$ and $$$d$$$ are 1,0,0 or 0,1,1, which are not possible; so, in that case, the answer is -1.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve() {
ll a = 0, b, c, d, pos = 1, bit_b, bit_c, bit_d, mask = 1;
cin >> b >> c >> d;
for (ll i = 0; i < 62; i++) {
if (b&mask) bit_b = 1;
else bit_b = 0;
if (c&mask) bit_c = 1;
else bit_c = 0;
if (d&mask) bit_d = 1;
else bit_d = 0;
if ((bit_b && (!bit_c) && (!bit_d)) || ((!bit_b) && bit_c && bit_d)) {
pos = 0;
break;
}
if (bit_b && bit_c) {
a += (1ll-bit_d)*mask;
} else {
a += bit_d*mask;
}
mask<<=1;
}
if (pos) {
cout << a << "\n";
} else {
cout << -1 << "\n";
}
}
int main() {
ll t;
cin >> t;
while (t--) {
solve();
}
}
D. Connect the Dots
By P.V.Sekhar
The value of $$$d$$$ is very small.
Try using Disjoint Set Union (DSU).
The main idea is to take advantage of the low upper bound of $$$d_i$$$ and apply the Disjoint Set Union.
We will consider $$$dp[j][w]$$$, which denotes the number of ranges that contain the $$$j$$$ node in connection by the triplets/ranges with $$$w$$$ as $$$d$$$ and $$$j$$$ is not $$$a\ +\ k\ *\ d$$$, and $$$id[j][w]$$$, which denotes the node that represents an overall connected component of which $$$j$$$ node is part of for now.
The size of both $$$dp$$$ and $$$id$$$ is $$$max_j * max_w = (n) * 10 = 10\ n$$$.
We will maintain two other arrays, $$$Start_cnt[j][w]$$$ and $$$End_cnt[j][w]$$$, which store the number of triplets with $$$j$$$ as $$$a_i$$$ and $$$a_i+k_i*d_i$$$, respectively, and with $$$w$$$ as $$$d_i$$$, to help us maintain the beginning and end of ranges.
We will now apply Disjoint Set Union. For each $$$i$$$th triplet, we assume $$$a_i$$$ will be the parent node of the Set created by $$$a_i$$$, $$$a_i$$$ + $$$d_i$$$, ..., $$$a_i+k_i*d_i$$$.
The transitions of $$$dp$$$ are as follows:
1) if $$$j \ge 10$$$ (max of $$$d_i$$$): for all $$$w$$$, $$$dp[j][w]$$$ are the same as $$$dp[j-w][w]$$$, just with some possible changes. These changes are due to $$$j$$$ being the start or the end of some triplet with $$$d_i$$$ as $$$w.$$$ So, let us start with $$$dp[j][w]$$$ as $$$Start_cnt[j][w] - End_cnt[j][w]$$$. If $$$dp[j-w][w]$$$ is non-zero, then perform a union operation (of DSU) between the $$$j$$$ node and $$$id[j-w][w]$$$, increment $$$dp[j][w]$$$ by $$$dp[j-w][w]$$$, and assign $$$id[j][w]$$$ as $$$id[j-w][w]$$$. This unites the ranges over the $$$j$$$ node.
2) if $$$j \lt 10$$$ (max of $$$d_i$$$): we do the same as above; rather than doing for all $$$w,$$$ we would restrict ourselves with $$$w$$$ from $$$0$$$ to $$$j-1$$$.
The net time complexity = updation of $$$dp[j][w]$$$ value by $$$Start_cnt$$$ and $$$End_cnt$$$ + union operations due to union of $$$id[j-w][w]$$$ with $$$j$$$ over all $$$w$$$ + incrementing $$$dp$$$ values (by $$$dp[j-w][w]$$$) + copying $$$id$$$ values = $$$10\ n + 10\ nlogn + 10\ n + 10\ n= 10 nlogn + 30n$$$ (in worst case) = $$$O(max_d*n*logn)$$$.
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll N = 2e5+2;
const ll C = 10 + 1;
vector<ll> par(N), sz(N, 0);
vector<vector<ll>> dp(N, vector<ll> (C, 0)), ind(N, vector<ll> (C, 0)), start_cnt(N, vector<ll> (C, 0)), end_cnt(N, vector<ll> (C,0));
ll find_par(ll a) {
if (par[a] == a) return a;
return par[a] = find_par(par[a]);
}
void unite(ll a, ll b){
a = find_par(a), b = find_par(b);
if (a == b) return;
if (sz[b] > sz[a]) swap(a, b);
sz[a] += sz[b];
par[b] = a;
}
void reset(ll n) {
for (ll i = 1; i <= n; i++) {
par[i] = i;
sz[i] = 1;
for (ll j = 1; j < C; j++) {
dp[i][j] = start_cnt[i][j] = end_cnt[i][j] = 0;
ind[i][j] = i;
}
}
}
void solve() {
ll n, m, a, d, k;
cin >> n >> m;
reset(n);
for (ll i = 0; i < m; i++) {
cin >> a >> d >> k;
start_cnt[a][d]++;
end_cnt[a + k * d][d]++;
}
for (ll i = 1; i <= n; i++) {
for (ll j = 1; j < C; j++) {
dp[i][j] = start_cnt[i][j] - end_cnt[i][j];
if (i-j < 1) continue;
if (dp[i-j][j]) {
unite(ind[i-j][j], i);
ind[i][j] = ind[i-j][j];
dp[i][j] += dp[i-j][j];
}
}
}
ll ans = 0;
for (ll i = 1; i <= n; i++) {
if (find_par(i) == i) ans++;
}
cout << ans << "\n";
}
int main() {
ll t;
cin >> t;
while (t--) {
solve();
}
}
E. Expected Power
By nishkarsh
Try to find the expected value of $$$f(S)$$$ rather than $$$(f(S))^2$$$.
Write the binary representation of $$$f(S)$$$ and find $$$(f(S))^2$$$.
Let the binary representation of the $$$Power$$$ be $$$b_{20}b_{19}...b_{0}$$$. Now $$$Power^2$$$ is $$$\sum_{i=0}^{20} \sum_{j=0}^{20} b_i b_j * 2^{i+j}$$$. Now if we compute the expected value of $$$b_ib_j$$$ for every pair $$$(i,j)$$$, then we are done.
We can achieve this by dynamic programming. For each pair $$$i,j$$$, there are only 4 possible values of $$$b_i,b_j$$$. For every possible value, we can maintain the probability of reaching it, and we are done.
The complexity of the solution is $$$O(n.log(max(a_i))^2)$$$.
#include <bits/stdc++.h>
using namespace std;
int fast_exp(int b, int e, int mod){
int ans = 1;
while(e){
if(e&1) ans = (1ll*ans*b) % mod;
b = (1ll*b*b) % mod;
e >>= 1;
}
return ans;
}
const int mod = 1e9+7;
const int bits = 11;
int inv(int n){
return fast_exp(n,mod-2,mod);
}
const int inverse_1e4 = inv(10000);
int dp[bits][bits][2][2];
void transition(int a, int p){
p = (1ll*p*inverse_1e4) % mod;
int negp = (mod+1-p) % mod;
int bin[bits];
for(int i = 0; i < bits; i++){
bin[i] = a&1;
a >>= 1;
}
for(int i = 0; i < bits; i++){
for(int j = 0; j < bits; j++){
int temp[2][2];
for(int k : {0,1}) for(int l : {0,1}) temp[k][l] = (1ll*dp[i][j][k][l]*negp + 1ll*dp[i][j][k^bin[i]][l^bin[j]]*p) % mod;
for(int k : {0,1}) for(int l : {0,1}) dp[i][j][k][l] = temp[k][l];
}
}
}
int main() {
int t;
cin >> t;
while(t--){
int n;
cin >> n;
int a[n],p[n];
for(int i = 0; i < n; i++) cin >> a[i];
for(int i = 0; i < n; i++) cin >> p[i];
for(int i = 0; i < bits; i++) for(int j = 0; j < bits; j++) dp[i][j][0][0] = 1;
for(int i = 0; i < n; i++) transition(a[i],p[i]);
int ans = 0;
for(int i = 0; i < bits; i++){
for(int j = 0; j < bits; j++){
int pw2 = (1ll<<(i+j)) % mod;
ans += (1ll*pw2*dp[i][j][1][1]) % mod;
ans %= mod;
for(int k : {0,1}) for(int l : {0,1}) dp[i][j][k][l] = 0;
}
}
cout << ans << "\n";
}
return 0;
}
F. Count Leaves
By nishkarsh
$$$f$$$ satisfies a special property for fixed d.
$$$f$$$ is multiplicative i.e. $$$f(x.y)$$$ = $$$f(x) * f(y)$$$ if $$$x,y$$$ are coprime, for fixed d.
It can be observed that the number of leaves is equal to the number of ways of choosing $$$d$$$ integers $$$a_0,a_1,a_2...a_d$$$ with $$$a_d = n$$$ and $$$a_i divides a_{i+1}$$$ for all $$$(0 \le i \le d-1)$$$.
Lets define $$$g(n) = f(n,d)$$$ for given $$$d$$$. It can be seen that the function $$$g$$$ is multiplicative i.e. $$$g(p*q) = g(p)*g(q)$$$ if $$$p$$$ and $$$q$$$ are coprime.
Now, lets try to calculate $$$g(n)$$$ when $$$n$$$ is of the form $$$p^x$$$ where $$$p$$$ is a prime number and $$$x$$$ is any non negative integer. From the first observation, we can say that here all the $$$a_i$$$ will be a power of $$$p$$$. Therefore $$$a_0,a_1,a_2...a_d$$$ can be written as $$$p^{b_0},p^{b_1},p^{b_2}...p^{b_d}$$$. Now we just have to ensure that $$$0 \le b_0 \le b_1 \le b_2 ... \le b_d = x$$$. The number of ways of doing so is $$$\binom{x+d}{d}$$$.
Now, lets make a dp (inspired by the idea of the dp used in fast prime counting) where $$$dp(n,x) = \sum_{i=1, spf(i) >= x}^{n} g(i)$$$. Here $$$spf(i)$$$ means smallest prime factor of $$$i$$$.
Our required answer is $$$dp(n,2)$$$.
The overall complexity of the solution is $$$O(n^{\frac{2}{3}})$$$.
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
ll ans=1;
if(base<0) base+=mod;
while(exponent){
if(exponent&1)ans=(ans*base)%mod;
base=(base*base)%mod;
exponent/=2;
}
return ans;
}
ll gcd(ll a, ll b){
if(b==0) return a;
else return gcd(b,a%b);
}
const int INF = 2e9;
const ll INFLL = 4e18;
const int small_lim = 1e6+1;
const int mod = 1e9+7;
const int big_lim = 1e3+1;
ll primes_till_i[small_lim];
ll primes_till_bigger_i[big_lim];
vl sieved_primes[small_lim];
vl sieved_primes_big[big_lim];
vi prime;
int N,k,d;
void sieve(){
vi lpf(small_lim);
ll pw;
for(int i = 2; i < small_lim; i++){
if(! lpf[i]){
prime.pb(i);
lpf[i] = i;
}
for(int j : prime){
if((j > lpf[i]) || (j*i >= small_lim)) break;
lpf[j*i] = j;
}
}
for(int i = 2; i < small_lim; i++){
primes_till_i[i] = primes_till_i[i-1] + (lpf[i] == i);
}
}
ll count_primes(ll n, int ind){
if(ind < 0) return n-1;
if(1ll*prime[ind]*prime[ind] > n){
if(n < small_lim) return primes_till_i[n];
if(primes_till_bigger_i[N/n]) return primes_till_bigger_i[N/n];
int l = -1, r = ind;
while(r-l > 1){
int mid = (l+r)>>1;
if(1ll*prime[mid]*prime[mid] > n) r = mid;
else l = mid;
}
return primes_till_bigger_i[N/n] = count_primes(n,l);
}
int sz;
if(n < small_lim) sz = sieved_primes[n].size();
else sz = sieved_primes_big[N/n].size();
ll ans;
if(sz <= ind){
ans = count_primes(n,ind-1);
ans -= count_primes(n/prime[ind],ind-1);
ans += ind;
if(n < small_lim) sieved_primes[n].pb(ans);
else sieved_primes_big[N/n].pb(ans);
}
if(n < small_lim) return sieved_primes[n][ind];
else return sieved_primes_big[N/n][ind];
}
ll count_primes(ll n){
if(n < small_lim) return primes_till_i[n];
if(primes_till_bigger_i[N/n]) return primes_till_bigger_i[N/n];
return count_primes(n,prime.size()-1);
}
const int ncrlim = 3.5e6;
int fact[ncrlim];
int invfact[ncrlim];
void init_fact(){
fact[0] = 1;
for(int i = 1; i < ncrlim; i++) fact[i] = (1ll*fact[i-1]*i)%mod;
invfact[ncrlim-1] = powmod(fact[ncrlim-1], mod-2, mod);
for(int i = ncrlim-1; i > 0; i--) invfact[i-1] = (1ll*invfact[i]*i)%mod;
}
int ncr(int n, int r){
if(r > n || r < 0) return 0;
int ans = fact[n];
ans = (1ll*ans*invfact[n-r]) % mod;
ans = (1ll*ans*invfact[r]) % mod;
return ans;
}
ll calculate_dp(ll n, int ind){
if(n == 0) return 0;
if(prime[ind] > n) return 1;
ll ans = 1,temp;
if(1ll*prime[ind]*prime[ind] > n){
temp = ncr(k+d,d);
temp *= count_primes(n)-ind;
ans+=temp; ans %= mod;
return ans;
}
ans = 0;
ll gg = 1;
ll mult = d;
while(gg <= n){
temp = calculate_dp(n/gg,ind+1);
temp *= ncr(mult,d);
ans += temp;
ans %= mod;
mult += k;
gg *= prime[ind];
}
return ans;
}
int main(){
sieve();
init_fact();
int t;
sd(t);
while(t--){
sd(N);sd(k);sd(d);
plldn(calculate_dp(N,0));
for(int i = 1; i < big_lim; i++){
primes_till_bigger_i[i] = 0;
sieved_primes_big[i].clear();
}
}
return 0;
}
whats the point of allowing $$$O(n \cdot 1024)$$$ solutions in E
well, we reduced the bound on A to make sure nlog^2A passes.
We didn't knew that these solutions existed.
know*
I think $$$a_i < 2^{14}$$$ or something would've been the optimal choice if i am not mistaken $$$O(n \log^2 A)$$$ should pass as long as there is no bad constant factor and the more naive solution wouldn't have passed but i am sure it was hard to predict that such solutions would pop up + thanks for the amazing contest.
It's not hard to expect that the dp 1024n is too easy and obvious to anyone who has solved dp+ev before
Yes it is straight forward but $$$n$$$ is still upto $$$2 \cdot 10^5$$$ so passing shouldn't seem smooth, some people even got TLE.
my O(n * 1024) solution passed (4000ms), so I optimized to O(min(n, 1024) * 1024) and it passed 2500ms.
This also didn't seem intended but yeah this solution also exists and it runs in $$$O(\text{max } a_i^2)$$$.
Can anyone explain how did we get the direct formula in B??
Every number has an even number of factors, except square numbers.
We can prove the first fact by finding a factor a of number n. Then, if n is not a square n/a is another factor of n.
If n is a square, then we double count sqrt(n), as we count n/sqrt(n) and sqrt(n) which are the same value. This leads to an odd number of factors(every other factor + 1).
Using this, if a switch is flipped an even number of times, it returns back to 1. If it flipped an odd number of times, it returns to 0.
what is the explanation of n-sqrt(n)>=k?
sqrt(n) gives how many square numbers are there for n, since squares cant be On we need to subtract them to get total lights on and the RHS is since we need to check if ON is atleast k to get the binary search going.
Check the solution discution on YT.
even divisor ...so it will be on
This does not answer the question which was about how to get the direct formula: $$$n=⌊k+\sqrt{k}+0.5⌋$$$
I personally guess it was a trap for chatgpt
This was a good round, unless I FST ofc, then it was a horrible round. I think that there should be more problems like this — problems that don't require so much IQ, but $$$do$$$ require coding. These problems are what might be called chill problems.
Now after seeing the solution of B problem.... I just want to cry ):
I was able to figure out that number of ON bulbs after n operations is related to sqrt(n) but was going in opposite track. Here only perfect squares are off and other are ON.
I understood the binary search solution for problem B. But, I am not able to figure out how direct formula $$$n = \lfloor k + \sqrt{k} +0.5 \rfloor$$$ came. Can anyone please explain it?
dont think abt that farmula number of number of perfect squares<=k and add to k(ie (int)sqrt(k)) now we can only cross atmost one more square in b/w [k,k+(int)sqrt(k)] which is ((int)sqrt(k)+1)^2 check for that and add 1 the farmula given directly checks it mathematically
In problem B, how do we derive the formula $$$( n = \left\lfloor k + \sqrt{k} + 0.5 \right\rfloor )$$$ from the equation $$$( n - \left\lfloor \sqrt{n} \right\rfloor = k )$$$?
If maxa is sth like 2^20, E will be a good problem. What a pity.
A O(1) solution for C exists its just
b ^ d
or -1. This comes from simplifying the truth table.O(1) solution for B exists too
cout << k + (int)sqrtl(k + (int)sqrtl(k)) << endl;
I don't think this is O(1) since sqrt is log(n) time complexity
It's considered to be constant in bit complexity, just as how we consider other arithmetic operations to have constant complexity.
Amazing
In problem C simply set a to b xor d and check if it works
You put image of editorial C to editorial D. By accident I suppose
I got the idea of problem B fast because of 1909E - Multiple Lamps.
Doing what problem B does solves this when $$$n \ge 20$$$.
its an extremely well known riddle, here is a youtube link for n = 100
https://www.youtube.com/watch?v=xwWdBj5WfCo
How was I supposed to solve that B problem, I literally had 0 idea that I will have to build a formulae for that, plus the observation required for the problem isn't normal at all.
Binary search is an alternative solution
contest is too math
In B no need for a formula, you can just binary search for the answer, it only needs that observation
That observation is too much for me, tell me how much more I need to practice in order to get that B always right.
I saw that observation before in blogs but usually you just need practice to get observations fast, if you aren't sure how to practice correctly I think there's lots of cf blogs on it
I personally guess that formula was a trap for chatgpt cheaters
Can someone help me with my code for E. I am finding probability for each bit to be active or not then for all number adding it's contribution to expectation.
z[i][0][j] represent prob in first i element our subset's xor will have j'th bit set
z[i][1][j] represent prob in first i element our subset's xor will not have j'th bit set
then for each number(0-1023) i add contribution number 5's contribution would be simply (z[n-1][0][0]*z[n-1][1][1]*z[n-1][2][0])*5*5
Squaring is not linear so you can't handle bit by bit without doing the editorial's trick, what works is z[i][j] represents probability in first i element that the xor is equal to j
i do understand editorial's way but can't find mistake in my own approch. can you may be give me little example
Oh I didn't understand your solution, it looks like it should work, there might be an implementation mistake somewhere
At first I thought of something similar for this problem. The issue is that the probability of getting a 1 on the ith bit is not independent to the probability of getting a 1 on the jth bit. An example of this may be that given the case:
1
3
5000
I can either take the 2^0 bit and the 2^1 bit or I can take neither, yet your implementation may give some probability to 2's contribution.
Makes sense I think that's the problem with the solution
Ahhh!! you are absolutely right i see problem now.
The editorial solution for E is too complicated. There is a much easier O(1024 * n) dynamic programming solution which comfortably fits within time limit.
Probably it was not intended. But I don't know why they even allowed O(1024n) to pass. Could've had a[i]<10^9 and time limit 4 seconds or something like that
They said they didn't know such solution exists: https://mirror.codeforces.com/blog/entry/134516?#comment-1203470
Why is Carrot not working !?
E can (accidentally) be solved with FWT: https://mirror.codeforces.com/contest/2020/submission/283601247
Seems like you didnt consider two much easier solutions in D and E
Problem D has a much easier $$$O(nd^2 + m)$$$ solution.
Hello can anyone help me why B submission is getting WA on Test case 8?
Can anyone tell me what I am doing wrong looking at my profile, I am unable to reach pupil
$$$O(nd+m)$$$ solution to D: 283633809 We can brute force all edges and run dfs for connected components, since there are at most $$$2*d$$$ edges per node.
Can anyone help me debug my code, It failed test case 8. I tried so hard today but not enough :(
Submission:283668245
For C, can someone explain why it is bit independent? I am unable to wrap my head around it
Assume it is not bit independent. Then there must be some i, for which (a|b)'s i-th bit is not set and (a&c)'s i-th bit is set. If (a&c)'s i-th bit is set, then a's i-th bit must also be set. But if a's i-th bit is set, then (a|b)'s i-th set must also be set, which is a contradiction. Therefore it is bit independent.
Oh yes! That makes sense. THANKS!
Also if you can, can you tell why this submission is failing?
283672706
An alternative solution to the problem D in $$$O(max_d * n + m)$$$
Consider the point $$$x$$$, note that it can only be connected to the $$$max_d$$$ points that go in front of it. We will support $$$dp[x][d] = k$$$, where $$$x$$$ is the coordinate of a point on a numeric line, $$$d$$$ is the length of the reverse step, $$$k$$$ is the maximum number of steps that will be taken from point $$$x$$$ with step $$$d$$$. Then note that we can move from point $$$x - d$$$ to point $$$d$$$ only if $$$dp[x - d][d] > 0$$$. In this case, we will draw an undirected edge between the points $$$x - d$$$ and $$$d$$$. Recalculate the dynamics for point $$$x$$$ as follows $$$dp[x][d] = max(dp[x][d], dp[x - d][d] - 1)$$$
Dynamics base, initially for all $$$x$$$ and $$$d$$$, $$$dp[x][d] = 0$$$. Now for all m triples $$$a_i, d_i, k_i$$$ we get $$$dp[a_i][d_i] = max(dp[a_i][d_i], k_i)$$$
At the end, using dfs, we will find the number of connectivity components
Code of this solution: 283668708
i did similar but used dsu for counting
In the editorial of F, I think it should be $$$f(p^{ik},d)$$$ instead of $$$f(p^{i}k,d)$$$
https://mirror.codeforces.com/contest/2020/submission/283572788
can anyone help me why above is wrong
might be a rounding issue. generally a good idea to avoid non-integer types unless absolutely necessary
Where's the originality?
Problem Codeforces 976 Div2 $$$F$$$ be directly copied from AtCoder Beginner Contest 370 G link: https://atcoder.jp/contests/abc370/editorial/10906
The core idea of both problems is absolutely identical, including the approach of solving them with a convolution technique. The only noticeable difference between the two problems lies in how the function $$$f(prime)$$$ and $$$f(prime^{ki}, b)$$$ is computed. Other than that, the rest of the structure, including the logic and solution techniques, are the same. This raises concerns about originality and fair practice in problem setting across competitive programming platforms.
Problem Codeforces 976 Div2 $$$E$$$ has solution with the most basic dp idea with $$$O(n \cdot 1024)$$$.
As someone who placed officially 12-th in Div 2, I’m absolutely disappointed with how Codeforces 976 Div2 F turned out.
for problem b, Doing the same idea but initializing right bound as 2*k instead of 2e18 is considered wrong answer on test 8. how helpful
An easier alternate solution to D which doesn't use DP: Similar to editorial solution I used a DSU to keep track of components, but to check whether elements $$$i$$$ and $$$i+d_i$$$ are connected, I simply need to check among operations $$$j$$$ where $$$d_j = d_i$$$, and $$$a_j \% d_j = i\%d_i$$$. I used a map to store sets of operations together based on $$$d_j$$$ and $$$a_j\%d_j$$$, and I stored each operation as a pair $$$[ a_j, a_j + k_j \cdot d_j ]$$$. Since each operation can now simply be represented as an interval, I used a datastructure which I called an
IntervalSet
which internally uses anstd::set
to efficiently a store intervals in amortized $$$O(\text{log n})$$$ and query whether an interval is completely included in the set in $$$O(\text{log n})$$$ where $$$n$$$ is the number of intervals in the set. This allows me to simply query whether $$$[i,i+d_i]$$$ is included in the among the operations with $$$d_j = d_i$$$, and $$$a_j \% d_j = i\%d_i$$$ which makes the code very simple.My submission: 283669482
PS: I used ChatGPT to help in implementing the IntervalSet class so its not in a great state rn;) and I haven't seen any implementations of such an IntervalSet class, so I would love to learn about any other implementations you guys know about.