MAXIMISEBITS-Editorial

editorial
, ,
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

42

Nice explanation !Better than the editorialist.

1 Like
43

your implementations is good .

1 Like