PROBLEM LINK:
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. 
), 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.
hopefully the editorialist clarifies their proof tho