PROBLEM LINK:
Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1
Author: Soumyadeep Pal
Tester: Manan Grover
Editorialist: Vichitr Gandas
DIFFICULTY:
SIMPLE
PREREQUISITES:
NONE
PROBLEM:
Value of an array A of length L is defined as the sum of (A_i⊕i) for all 0≤i<L, where ⊕ denotes bitwise xor operation. Note that array indices start from zero.
You are given an integer N. Then you create an array A consisting of 2^N integers where A_i=i for all 0≤i<2^N.
You can do at most K operations on this array. In one operation, you can choose two indices i and j (0≤i,j<2^N) and swap A_i and A_j.
What is the maximum value of array A you can obtain after at most K operations?
EXPLANATION
Initially A_i = i hence A_i ⊕ i = 0 for all 0 \le i < 2^N. Here we can get max xor A_i ⊕ i = 2^N -1 by setting A_i = i ⊕ (2^N - 1). In one operation we are swapping two elements so we can make two elements equal to 2^N-1. So best way is to swap A_i with A_i ⊕ (2^N-1).
So we just need to find out how many elements we would be able to make equal to 2^N-1 in K moves. In one move, we can make two elements, hence in K moves at most 2 \cdot K. But also there are only 2^N elements hence take the minimum i.e. min(2 \cdot K, 2^N).
After these operations if i^{th} element has become A_i = i ⊕ (2^N-1) then it would contribute 2^N-1 to the value because A_i ⊕ i = i ⊕ (2^N-1) ⊕ i = 2^N-1. And all other elements would contribute 0 as they are not changed. Hence answer is min(2 \cdot K, 2^N) \times (2^N-1).
TIME COMPLEXITY:
O(N) per test case
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
int n, k; cin >> n >> k;
int x = 1;
for (int i = 0; i < n - 1; i++) x *= 2;
int ans = 2 * min(x, k) * (x * 2 - 1);
cout << ans << '\n';
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
long long n, k;
cin>>n>>k;
long long temp = pow(2, n);
long long ans = min(2 * k, temp) * (temp - 1);
cout<<ans<<"\n";
}
return 0;
}
Editorialist's Solution
/*
* @author: vichitr
* @date: 24th July 2021
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);
void solve() {
int N, K; cin >> N >> K;
int twoPowerN = 1;
for (int i = 0; i < N; i++)
twoPowerN *= 2;
int ans = min(twoPowerN, K * 2) * (twoPowerN - 1);
cout << ans << '\n';
}
signed main() {
fast;
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
cin >> t;
for (int tt = 1; tt <= t; tt++) {
// cout << "Case #" << tt << ": ";
solve();
}
return 0;
}
VIDEO EDITORIAL:
If you have other approaches or solutions, let’s discuss in comments.If you have other approaches or solutions, let’s discuss in comments.