MAXIMISEBITS-Editorial

editorial
, ,
21

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
22

thank u so much

23

why you are consedering <k condetion in step 2 , we have to make sum==k

24

In second case:

I am unable to prove both the statements. Can someone provide proof please?

25

Don’t know why but this editorial went over my head.

26

hi @adityagamer can you explain ur approach a little , i have seen ur code , what is the significance of have and need variable. Thanks in advance.

28

Actually the code is just a bit different than in editorial description(but same as editorialist code) which will require extra proof. Code for editorial solution:: Solution: 66470577 | CodeChef

29

can someone tell me which test case is not running ?
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
#ifndef ONLINE_JUDGE
freopen(“input.txt”, “r”, stdin);
freopen(“output.txt”, “w”, stdout);

#endif // ONLINE_JUDGE
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while (t–)
{
ll n, k;
cin >> n >> k;
//cout << (1 << 2) << “ram\n”;
if (n < k)
{
ll cnt = 0;
ll k1 = 0;
ll cnt1 = 0;
int flag1 = 0;
for (int i = 0; i < 31; i++)
{
k1 = (1 << i);
if (k1 * n <= k)
{
cnt1 += n;
k -= (k1 * n);
}
else
{
cnt1 += (k / k1);
k -= k1 * n;
break;
}

     }
     cout << cnt1 << "\n";
  }
  else cout << k << "\n";

}

return 0;
}

30

Can we solve this question by calculating bit count, if we can, can anyone tell me the approach? I tried but didn’t clear private testcases

31

Could someone please tell me the logic for the same parity and different parity if K > N?

32

https://www.codechef.com/viewsolution/66414975

The code is passing for test cases 2 and 3 but failing for the first one. As mentioned in few of the comments I tried those test cases but it is giving me correct answer on those. Could somebody pls help me to find out where is it going wrong ?
Thanks a lot in advance :slight_smile:

33

Because i want to put next big value at the previous values only such that sum should be <=k and in the 3- step i’m making sure that total sum ==k .
please read my edited code you will understand better

34

Thank you! Good problem!

In fact, we can fill N numbers from LSB to MSB 1 by 1 bit. If it’s possible to fill all of N numbers for current bit, then consider the left bit.

  int tc, n, k;
  scanf("%d", &tc);
  while (tc--) {
    scanf("%d%d", &n, &k);
    int res {};

    if (n >= k) {
      printf("%d\n", k);
      continue;
    }

    while (k > n) {
      if (k % 2 == n % 2) {
        res += n;
        k -= n;
      } else {
        res += n - 1;
        k -= n - 1;
      }

      k /= 2;
    }
    if (k) res += k;

    printf("%d\n", res);
  }
35

Bhai, Can You please send your code, You explained it so well.

1 Like
36

Be aware that I am using Java. I added some comments to my contest submission. I advice you to look at the improved submission.

contest submission: CodeChef: Practical coding for everyone
submission with comments: CodeChef: Practical coding for everyone

1 Like
37

I solved this problem with exactly the same idea as the editorial.
It’s a greedy solution. For each bit from lowest to highest, we want to set as most as possible 1s at current bit. But, if parity of K and N is different, we can’t set N 1s on that bit, because then we can not reach K no matter how to set on higher bits.

1 Like
38

can you please elaborate ?

39

First, we want to set as most as possible 1s at lower bit, because a higher bit costs at least 2 times to K. then, if parity of K and N is different, if we set N 1s on kth bit, we will get K - N left which is not divisible by 2^{k + 1}.

40

@majay1638 Your approach is same as mine just wanted to add my c++ code to it. Link below:
https://www.codechef.com/viewsolution/66413887

Time complexity is same as the original Editorial solution, ie, O(Log(k))

41

My solution also passes the tasks 2 and 3 but not the first. can anyone help me .
https://www.codechef.com/viewsolution/66486010