MAXIMISEBITS-Editorial

Setter: Satyam
Tester: Nishank Suresh, Abhinav sharma
Editorialist: Devendra Singh

2010

None

PROBLEM:

Let f(X) denote the number of set bits in X.

Given integers N and K, construct an array A of length N such that:

• 0 \leq A_i \leq K for all (1 \le i \le N);
• \sum_{i=1}^{N} A_i = K

Over all such possible arrays, find the maximum value of \sum_{i=1}^{N} f(A_i).

EXPLANATION:

Claim : Each bit that is present in the numbers (except the most significant bit) of all the numbers is either present in all N numbers or N-1 numbers.

Proof

Let us suppose there exists a bit at position i which is set to 1 in N-2 or less numbers and a bit i+1 is set to 1 in at least one number in A, then we can unset the bit i+1 from a number and set i^{th} bit in two numbers in which it was unset earlier. This increases the total number of set bits without changing the sum of the numbers.

Start iterating from i=0 to i=30 or until K>0. There are three cases now:

• If K\leq N set K bits at the i^{th} position and end the loop.
• If K>N and the parity of N and K is same then some higher bit will be set in the next steps to achieve the sum K. This means i^{th} bit has to be set in either N numbers or N-1 numbers. Since the parity is same we have to set it to N numbers.
• If K>N and the parity of N and K is not same then some higher bit will be set in the next steps to achieve the sum K. This means i^{th} bit has to be set in either N numbers or N-1 numbers. Since the parity is not same we have to set it to N-1 numbers.
Remove the contribution of each bit after each step from the sum by subtracting the number of bits taken and dividing K by 2.

TIME COMPLEXITY:

O(log(K)) for each test case.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#define all(v) v.begin(),v.end()
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(string x){cerr<<x;}
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using muloset=tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=500500;
void solve(){
ll n,x; cin>>n>>x;
ll ans=0;
while(x){
ll cur=min(x,n);
if((cur&1)!=(x&1)){
cur--;
}
ans+=cur;
x=(x-cur)/2;
}
cout<<ans<<nline;
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(15);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}


Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
void sol(void)
{
int n, k;
cin >> n >> k;
ll ans = 0;
for (int i = 0; i < 30; i++)
{
if (n % 2 == k % 2)
{
ans += min(n, k);
k -= min(n, k);
}
else
{
ans += min((n - 1), k);
k -= min(n - 1, k);
}
k /= 2;
}
cout << ans << '\n';
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}


3 Likes

I really enjoyed this problem. I had a different solution that passes tasks 2 and 3, but not the first. Could someone please provide a test case that breaks my code?
https://www.codechef.com/viewsolution/66431986

3 Likes

Try the test case
2 11
For this ans should be 4, but yours should give 5

3 Likes

This is my code: Solution: 66432740 | CodeChef
It fails on 2 of the test cases but I am not able to figure out those test cases.
Could someone please point out where is this code failing?

1 Like

This was a challenging problem (atleast for me ) I had some difficulty in passing the first testcase, may someone please help me with it. Thanks in advance
https://www.codechef.com/viewsolution/66422586

2 Likes

Thankyou! I’m looking into my code now

Goddammit , i don’t know why i thought that sum all the Ai elements should be <=k .
I did this using binary search and it passed all the test cases now but in the contest it only passes 2 , 3 case . .

my solution : solution

Edit: My approach @tushar_kumar1 .

1. Think that what is the minimum value (V ) you can put at each position such that V has maximum set bits and the sum of all v is less than K then we subtract n*v from k.
The ans till now n x (set Bits in V).

Values of v that has highest bit set → 1 ->(1) , 11->(3) , 111->(7), 1111->(15) , 11111 ->(31) … so on

lstBit= set Bit in V

next val is lstBit+1

1. Now for the remaining K we check how many next value of V we can put at last value of V Because last value has less bit set and next value has more bit set as we know so it is optimal t remove last value from that index and put new V that has more bit set .

for finding how much last values we have to remove we can using Binary search .

after that same addition and multiplication . you can check my code i have updated : updated Solution

I hope it helps

2 Likes
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define long long int

int solve(int n,int k)
{
if(n==0 or k==0)
{
return 0;
}
if(n==1)
{
return __builtin_popcount(k);
}

int ans = 0;
for(int i = 1;i<=32;i++)
{
int p = 1<<i;
p--;
int req_n = k/p;
if(k%p!=0)
{
req_n++;
}
// cout<<i<<" "<<req_n<<"\n";
if(n>=req_n)
{
// cout<<ans<<" /";
ans += (k/p)*i;

if(k%p!=0){
int x = k%p;
ans += solve(n-(k/p),k-(k/p)*(p));
//this x can be breakdown

// ans += ;
}
break;
}
}
return ans;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;

while(t--)
{
int n,k;
cin>>n>>k;
int ans = solve(n,k);
cout<<ans<<"\n";
}
return 0;
}


My solution passes third test cases but dosen’t pass testcase 1 and 2. I have tried to think for testcases that fails but I am not able to find any such testcases.
Can anyone provide any testcases for this code?

My Approach: I have tried to have numbers with maximum set bits. For Example
If n = 8 and k = 5 then i will have 5 ‘1s’ and 3 ‘0s’.
if n= 4 and k =5 then I will try to have ‘3s’ and ‘1’ .
In the same way i have tried to have numbers who are having all bits set(power of 2 - 1) .

2 Likes

thanks

WA on the following test:
1
7 10

7
8

1 Like

What are the error in this code ?

#include<bits/stdc++.h>
using namespace std;

#ifdef LOCAL
#include “algo/debug.h”
#else
#define debug(…) 42
#endif

int fun(int n)
{
int val = 0;
for(int i = 0; i <= 30; i++) {
if(n & (1 << i)) val++;
}
return val;
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t; cin >> t;
while(t–) {
int N, K;
cin >> N >> K;
vector take;
for(int i = 1; i <= 30; i++) {
if(((1 << i) - 1) > K)
break;
take.push_back((1 << i) - 1);
}
int sz = take.size();
int j = sz - 1;
int sum = 0;
vector used(sz);
while(j >= 0) {
while((K / take[j]) < N) j–;
if((K / take[j]) > N) j++;
if(used[j] == true) break;
if(!used[j]) {
sum += (fun(take[j]) * (K / take[j]));
used[j] = true;
}
N -= (K / take[j]);
K -= (take[j] * (K / take[j]));
if(K == 0) break;
}
sum += fun(K);
cout << sum << endl;
}
return 0;
}

WA on the following test:
1
5 10

8
7

This editorial sucks !!

10 Likes

Thanks man your approach is way more understandable then the editorial.

1 Like

Hey Brother can you please explain step 2 more clearly and why you are doing it.

1 Like

take an example : n=3 ,k=6
after our first step : ans arr will =[1,1,1,] right ?
prevk = sum(ans)==3
but still we have k-3 left right ?
so in the 2-setp we are checking next value that is bigger than previous value and that we can put,
in this example next value would be 3 so we are checking how many 3 we can put at previous value(1) places such that we still have sum of values <=k
in this example we can put first place 3 resulting into ans = [3,1,1] the sum is still <=k and our ans increased

2 Likes

I am not able to understand this logic properly. can any one clarify little bit in different way?

1 Like

Thanks for replying, Now I get it.
Thanks once again

1 Like

I did it similarly but I skipped the Binary Search approach.

Step 0:
return k if n==1

Step 1:
realize that for values 0, 1, 3, 7, 15, 31, … 2^x-1, the set bits are maximized and that you want to fill the array with these numbers. (Reason: there is no number between(exclusive), for example, 15 and 31 that has more set bits than 15)

Step 2:
Example: n=5, k=34
now we find which (2^x-1)-number can be used to fully fill up our array. The solution is 3, because 3 * 5 <= 34 and 7 * 5 > 34.
Our array at this point: 3 3 3 3 3

Step 3:
realize that we only used 3 * 5 = 15 values of 34, we therefore have 19 to spare and can replace 3’s with 7’s.
Our array after the update: 7 7 7 7 3

Step 4:
now we take a step back. We realize that we used 31 of 34 values. We are forced to somehow use the remaining 3. This can be tricky and the only approach that always works is to remove the last 2 values and “brute force” a correct combination for the last 2 values.
Our array now: 7 7 7 ? ?

Step 5:
we brute force the last 2 values in a smart way. We need to find 2 values that sum up to 13 and have their set bits maximized. This can only happen if one number is of type (2^x-1). So we iterate over these numbers (0, 1, 3, 7, 15, 31 …), and calculate the second summand. We only care about (2^x-1) that are <= 13:
(0, 13), (1, 12), (3, 10), (7, 6). Now we find the amount of bits for each of these numbers and realize that the pair (7,6) has the most set bits.

Our final array looks like this:
7 7 7 7 6
this array has 14 set bits.

Note: step 0,3 and 4 can be done in O(1) - we can calculate the amount of our numbers with formulas.
step 2 and 5 take O(log k)

7 Likes

thank u so much