XOXO - Editorial

PROBLEM LINK:

Practice
Contest

Setter: Shahjalal Shohag
Tester: Rahul Dugar
Editorialist: Ishmeet Singh Saggu

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic Programming

PROBLEM:

You are given three integers N, K and X. Is it possible to find a sequence of non-negative integers A_1,A_2,…,A_N such that the number of pairs of indices (i,j) (1≤i≤j≤N) satisfying Ai⊕Aj=X is equal to K? Here, is the bitwise XOR operator.

QUICK EXPLANATION:

  • If we have a sequence of length L which satisfies the condition of having the number of pairs = K, then we can make a sequence of greater length also. (by appending an integer which does not form X, when XORed with any integer in the sequence).
  • Basic construction of sequence will be as : consider two integers a and b such that a⊕b=X, where frequency of a in sequence is f1 and frequency of b in sequence is f2 and f1*f2 = K. its length will be f1+f2. And final sequence will be the concatenation of such sequences, such that the condition \sum(f_i1 * f_i2) = K and \sum(f_i1+f_i2) \leq N is satisfied.
  • Let dp[k] = minimum \sum(f_i1 + f_i2) such that \sum(f_i1 * f_i2) = K.
  • We can initialize dp[i] as min(x+y) such that x*y = i using Sieve of Eratosthenes.
  • And now for each i in range [1, 3*10^5], dp[i] = min(dp[i], dp[j]+dp[i-j]) where 1 \leq j \leq 2 * \sqrt{i}. Note that the order of evaluation of i will be from 1 to 3*10^5.

EXPLANATION:

Let M = 10^5.
Suppose we have a sequence of length L which satisfies the condition of having the number of pairs = K, then we can make a sequence of greater length also. (by appending an integer which does not form X, when XORed with any integer in the sequence). So to solve the problem we have to find the minimum length of the sequence such that the number of pairs = K, and if its length is less than or equal to N then the answer is “YES” else the answer is “NO”.

One thing to note is that as there is no constraint on the magnitude of A_i so there are infinite ways to get 2 numbers such that there XOR is equal to X. One example of a construction will be, suppose two integers a and b such that a⊕b=X, where frequency of a in sequence is f1 and frequency of b in sequence is f2 and f1*f2 = K. its length will be f1+f2.

Now we know that the minimum length of the sequence having K pairs is the concatenation of one or more sequences of the above type. So to solve the problem we have to find a sequence which satisfy the condition \sum(f_i1 * f_i2) = K and \sum(f_i1+f_i2) \leq N.

We can solve this problem by using dynamic programming :

  • Let dp[k] = minimum \sum(f_i1 + f_i2) such that \sum(f_i1 * f_i2) = K.
  • We will precompute all the values of dp[i] for each i in range [1, 3*10^5].
  • We can initialize dp[i] as min(x+y) such that x*y = i using Sieve of Eratosthenes.
int N = 3e5+1;
for (int i = 1; i < N; i++) {
	for (int j = i; j < N; j += i) {
		int x = i, y = j/i;
		dp[j] = min(dp[j], x+y);
	}
}
  • And now for each i in range [1, 3*10^5], dp[i] = min(dp[i], dp[j]+dp[i-j]) where 1 \leq j < i. Note that the order of evaluation of i will be from 1 to 3*10^5. Now the runtime to run the algorithm will be O(M^2) which will give TLE, but we can reduce it, Note that for each i it is enough to iterate j till 2 * \sqrt{i} for optimal answer(explained below), hence we reduced the time complexity to O(M * \sqrt{M}).

For i * j = k, (i + j) is minimum when i and j are closer to each other.
so dp[k] \ge 2 \sqrt{k}

What is the minimum value we have to subtract from k s.t. it becomes a perfect square?

As (x + 1)^2 - x^2 = 2x + 1, we have to subtract at most 2 \sqrt{k} to make k a perfect square.

So for any k, dp[k] \le \sqrt{k} + \sqrt{k} + dp[k - \sqrt{k}\sqrt{k}] \le 2\sqrt{k} + dp[2\sqrt{k}]

So dp[k] \le 2\sqrt{k} + 2\sqrt{2\sqrt{k}} + 2\sqrt{2\sqrt{2\sqrt{k}}} + \ldots

As the lower bound is really close to the upper bound, it turns out that iterating on the larger values doesn’t give an optimal value as it suggests that if we use large values then they will add up to a larger value than our upper bound of dp[k]. As taking j = 2\sqrt{k} gave us the upper bound of dp[k], it turns out that it will be enough to iterate j up to 2 \sqrt{k}. For validation, you can check with an offline brute force.

TIME COMPLEXITY:

  • Time complexity for precomputation is O(M * \sqrt{M}). After precomputation each testcase can be answered in O(1).

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
 
const int N = 3e5 + 9;
int dp[N], f[N];
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  for (int i = 1; i < N; i++) {
    f[i] = i + 1;
  }
  for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) {
      f[j] = min(f[j], i + j / i);
    }
  }
  for (int i = 1; i < N; i++) {
    int lim = min(i, 2 * (int)sqrt(i));
    dp[i] = f[i];
    for (int j = 1; j <= lim; j++) {
      dp[i] = min(dp[i], f[j] + dp[i - j]);
    }
    int lb = 2 * sqrt(i), ub = 2 * sqrt(i) + 2 * sqrt(2 * sqrt(i)) + 2 * sqrt(2 * sqrt(2 * sqrt(i)));
    assert(dp[i] >= lb);
    assert(dp[i] <= ub);
  }
  int t; cin >> t;
  while (t--) {
    int n, k, x; cin >> n >> k >> x;
    if (dp[k] <= n) {
      cout << "YES\n";
    }
    else {
      cout << "NO\n";
    }
  }
  return 0;
} 
Tester's Solution
    #include <bits/stdc++.h>
    using namespace std;
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/rope>
    using namespace __gnu_pbds;
    using namespace __gnu_cxx;
    #ifndef rd
    #define trace(...)
    #define endl '\n'
    #endif
    #define pb push_back
    #define fi first
    #define se second
    #define int long long
    typedef long long ll;
    typedef long double f80;
    #define double long double
    #define pii pair<int,int>
    #define pll pair<ll,ll>
    #define sz(x) ((long long)x.size())
    #define fr(a,b,c) for(int a=b; a<=c; a++)
    #define rep(a,b,c) for(int a=b; a<c; a++)
    #define trav(a,x) for(auto &a:x)
    #define all(con) con.begin(),con.end()
    const ll infl=0x3f3f3f3f3f3f3f3fLL;
    const int infi=0x3f3f3f3f;
    const int mod=998244353;
    //const int mod=1000000007;
    typedef vector<int> vi;
    typedef vector<ll> vl;
     
    typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
    auto clk=clock();
    mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
    int rng(int lim) {
    	uniform_int_distribution<int> uid(0,lim-1);
    	return uid(rang);
    }
    int powm(int a, int b) {
    	int res=1;
    	while(b) {
    		if(b&1)
    			res=(res*a)%mod;
    		a=(a*a)%mod;
    		b>>=1;
    	}
    	return res;
    }
     
     
    long long readInt(long long l,long long r,char endd){
    	long long x=0;
    	int cnt=0;
    	int fi=-1;
    	bool is_neg=false;
    	while(true){
    		char g=getchar();
    		if(g=='-'){
    			assert(fi==-1);
    			is_neg=true;
    			continue;
    		}
    		if('0'<=g && g<='9'){
    			x*=10;
    			x+=g-'0';
    			if(cnt==0){
    				fi=g-'0';
    			}
    			cnt++;
    			assert(fi!=0 || cnt==1);
    			assert(fi!=0 || is_neg==false);
     
    			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
    		} else if(g==endd){
    			if(is_neg){
    				x= -x;
    			}
    			assert(l<=x && x<=r);
    			return x;
    		} else {
    			assert(false);
    		}
    	}
    }
    string readString(int l,int r,char endd){
    	string ret="";
    	int cnt=0;
    	while(true){
    		char g=getchar();
    		assert(g!=-1);
    		if(g==endd){
    			break;
    		}
    		cnt++;
    		ret+=g;
    	}
    	assert(l<=cnt && cnt<=r);
    	return ret;
    }
    long long readIntSp(long long l,long long r){
    	return readInt(l,r,' ');
    }
    long long readIntLn(long long l,long long r){
    	return readInt(l,r,'\n');
    }
    string readStringLn(int l,int r){
    	return readString(l,r,'\n');
    }
    string readStringSp(int l,int r){
    	return readString(l,r,' ');
    }
     
    int anser[300005];
    void pre() {
    	fr(i,1,300000)
    		anser[i]=i+1;
    	for(int i=1; i<=300000; i++)
    		for(int j=1; i*j<=300000; j++)
    			anser[i*j]=min(anser[i*j],i+j);
    	for(int i=1; i<=300000; i++)
    		for(int j=1; j<=1000&&j<i; j++)
    			anser[i]=min(anser[i],anser[i-j]+anser[j]);
    }
    void solve() {
    	int n=readIntSp(1,300000),k=readIntSp(1,300000),x=readIntLn(1,300000);
    	if(anser[k]<=n) {
    		cout<<"YES"<<endl;
    	} else
    		cout<<"NO"<<endl;
    }
    signed main() {
    	pre();
    	ios_base::sync_with_stdio(0),cin.tie(0);
    	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
    	cout<<fixed<<setprecision(8);
    	int t=readIntLn(1,1000000);
    //	cin>>t;
    	fr(i,1,t) {
    		solve();
    	}
    	assert(getchar()==EOF);
    #ifdef rd
    	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
    #endif
    	return 0;
    }
     

Feel free to share your approach. In case of any doubt or anything is unclear please ask it in the comment section. Any suggestions are welcomed. :smile:

7 Likes

I just have one question. Is it not true that I can always make atmost n/2 * n/2 pairs of whatever xor I need ?
Example the xor I need is 34 , K=6, N=6.
I can always do
0 0 0 34 34 1
Wouldn’t this kind of a formation always assure I have exactly 6 pairs with XOR = X.
when N is odd it wud be N/2 * (N/2+1) obviously.
Point being , K > (n/2 *n/2) then “NO” . why wouldn’t this work?

5 Likes

WOW, I was literally 1 line away from AC. There goes my 6 star lol

My solution: https://www.codechef.com/viewsolution/39027670

4 Likes

Tried somewhat similar approach! Got WA. There must be a counter case. If someone can help us with it.
So what I did was to see if K can be partitioned into two parts A and B with AB=K and |A| + |B| <= N. All the elements in A can have elements as X and all elements in B will be 0. The remaining elements can be anything. Now number of pairs satisfying the condition would simply be AB. Pick any element from A and match it with any element in B. But this gave wrong answer. Anyone can point out where would this go wrong?? Thanks!

public static String solve(int n, int k, int x) {
		if(k>(n*(n-1))/2) {
			return "NO";
		}
		
		
		for (int i = 1; i * i <= k; ++i) {
			int m = k % i;
			if (m == 0) {
				int d = k / i;
				if (d + i <= n) {
					return "YES";
				}
			}
		}
		return "NO";
	}
2 Likes

Yeah, I’m also having same doubt regarding this logic.
Can anyone please explain what is wrong in this??

Here is a counter test you can look for

1
798 81108 100

The answer to this is “YES”.

If you’re trying to simply split it into parts with the help of divisors closest to each other like 108 * 751 (which I was also doing in the contest :sob: ), then it requires 108+751 elements in the array, so your answer will be “NO”. But it can be minimized it even further with the help of dp.

Have a look at tourist’s code for better understanding.

2 Likes

This will not work in cases where the value of K can be decomposed into multiple pairs of A and B which are then added to form K.
eg. for K = 19, you can have K decomposed into 3 x 5 + 1 x 4
in which case you can have 0, 0, 0, 19, 19, 19, 19, 19, 1, 18, 18, 18, 18.
i.e. 0&19 for 3 x 5 pair and 1&18 for 1 x 4 pair.

3 Likes

Could someone explain why \sqrt{k} + \sqrt{k} + dp[k - \sqrt{k}\sqrt{k}] \leq 2\sqrt{k} + dp[2\sqrt{k}]?

This obviously implies that dp[k - \sqrt{k}\sqrt{k}] \leq dp[2\sqrt{k}] and it’s also true that k - \sqrt{k}\sqrt{k} \leq 2\sqrt{k}, but we can’t make any assumption about the monotonicity of the dp values, so I’m kinda confused.

1 Like

It is not true that the dp values are monotonically increasing. An easy to see counter case is that dp[5]=6 and dp[6]=5.

1 Like

Can u pls look into my solution. Its giving right answer on test case provided by you but not an AC.
Thanks in advance.
https://www.codechef.com/viewsolution/39027026

Hey guys.
Can someone tell me why below logic won’t work?

If I was given a number n , and I fill the n numbers with pairs of the number that form the required XOR like if I am given 4 3 3 and I make [1,2,1,2] then maximum pairs possible according to given condition become 4(which are Max pair I guess) and is more than required , so it’s always possible to alter array to print YES like [1,2,2,2]. So I tried like this making pairs of no. to get Max XOR and if Max is greater than required , then it’s always a YES. it passed sample cases but failed in test cases. Can anyone correct me plz.

Link to my code https://www.codechef.com/viewsolution/39018815

I have used this to initialize my dp still working fine(AC), I have used the condition (i%j==0) to initialize my dp[i], i.e I’m storing the minimum sum of two values such that thier product is i
i=x*y => dp[i]=x+y (max(x,y) is minimum possible which leads to dp[i] minimum for product of two value)
I just want to know that what is difference if I don’t use that condition (i%j==0) to initialize as it is mentioned in Editorial.

rep(i,1,MAXN-1) {
irep(j,sqrt(i),1) {
if(i%j==0) {
dp[i]=j+(i/j);
break;
}
}
}

Looks like many people have tried this. I also tried exactly the same approach and got wrong answer.
https://www.codechef.com/viewsolution/39017397

For everyone who had just split n into two equal parts (n/2) and (n-n/2) and checked if their product is greater than equal to k for the answer to be YES, here’s a testcase -
1
6 7 1
The answer is NO because the minimum n required to get k=7 is n=7 for which the expression is 2×3+1×1. But your codes will give YES as (n/2)*(n-n/2) = 3×3 = 9 >= k.

2 Likes

yeah I figured it wasn’t, which is why I don’t understand the editorial when it claims that dp[k - \sqrt{k}\sqrt{k}] \leq dp[2\sqrt{k}] (where \sqrt{k} denotes \lfloor \sqrt{k} \rfloor )

I too feel there’s something wrong here. Consider k=14. Here, \sqrt{k}=3. So, k-\sqrt{k}\sqrt{k}=5 and 2\sqrt{k}=6. But dp[5]>dp[6] which violates the condition.

1 Like

ah, thanks for a specific counterexample! just curious, when you got an AC on this problem in the contest, did you have some other proof that only checking the first 2\sqrt{k} transitions was sufficient for computing dp[k]? if you used a different method than the editorial then I guess the question doesn’t apply lol

Although I don’t have any proof for my solution. But it seems logical to check transitions only upto a number i such that k-i is of the form a^2-1 (which is at max 2\sqrt{k}) because a^2 and a^2-1 will have the same value and it may be beneficial to switch to a^2-1. Any other number less than a^2-1 seems worse because we want the two divisors to be as close as possible. I arrived at this observation by brute-forcing the first 100 numbers and it showed that checking upto 2\sqrt{k} is sufficient. And then I submitted the solution which passed.

hmmm, not sure if I buy the intuition exactly since it doesn’t disprove that you could also pick some k - i = b^2 such that b^2 < a^2. anyways, I guess I should’ve tried brute forcing something to check like what you did :slight_smile: hopefully the editorialist clarifies their proof tho

Thanks! Got it!