given two numbers x and y such that x+y=c (constant).
to maximize p=xy ,it can be proven that x=y=c/2 (by taking derivative and setting it to zero).
Thus product is maximized when two numbers are equal.
Consequently, we will move towards the greater product when two numbers tend towards being equal to each other (since the function is continuous).
Its given that D and E have a fixed sum equal to 2^N - C but I found that fixed sum is equal to 2^N - 1 - C. Kindly check this in the editorial.
Thanks!
Can you ples tell, why it is giving WA!
I also approached the ques , same way as you did.
'''
if x==y==0 , set the bit
elif x==y==1 , unset the bit
elif x==0 , y==1 or x==1, y==0:
we are sure we can set the bit(bcz either it will benefit from a or benefit from b), but we need to see...
secondly , we want product to be maximised, so eventually we want
a^x and b^x to have minimum difference and be close as much as possible.
So, we need to see if difference is increasing, we will set the bit such that min(a, b) will benefit and difference will decrease..
'''
def solve():
n ,a ,b = map(int, input().split())
c = 0
for i in range(n-1, - 1, -1):
x = a&(1<<i)
y = b&(1<<i)
if x==0 and y==0:
c+=(1<<i)
elif (x==0 and y==1) or (x==1 and y==0):
cur = (a^c)*(b^c) # ans with unset
newc = c+(1<<i)
new = (a^newc)*(b^newc) # ans with set
if new>cur:
c = newc
print(c)
for testis in range(int(input())):
solve()
Thanks.
well could add some proof for why you started out with the most significant bit (1<<n) and not from the 0th bit?
Well, it’s matter of choice, you can do it both ways
#include <bits/stdc++.h>
#define int long long int
void solve(){
int n, a, b;
std::cin >> n >> a >> b;
int num = 1, ans = 0;
while(n--){
int k = num+ans;
int x = (a^ans)*(b^ans);
int y = (a^k)*(b^k);
if(y > x)
ans += num;
num <<= 1;
}
std::cout << ans << "\n";
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
int t = 1;
std::cin >> t;
while(t--){
solve();
}
}
Here, starting from first bit
Change this to
x = (a>>i)&1
y = (b>>i)&1
It will get accepted
Hey, thanks for reply.
Aren’t both the same things?
We are checking if ith bit is set or not…
What is mistake in my way of checking.
Suppose a = 13 i.e. 1101, we have to check 3rd bit is set or not
- a&(1<<2) = (1101)&(0100) == 100 which is not equal to 1
- (a>>2)&1 = (0001)&(0001) == 001 which is equal to 1
If you want your code to work using first operation then change if and elif conditions to !x and !y, !x and y or x and !y…Don’t compare with x==0, x==1, this will give wrong answer
Accepted
def solve():
n ,a ,b = map(int, input().split())
c = 0
for i in range(n-1, - 1, -1):
x = a&(1<<i)
y = b&(1<<i)
if x == 0 and y == 0:
c+=(1<<i)
elif (x == 0 and y) or (x and y == 0):
cur = (a^c)*(b^c) # ans with unset
newc = c+(1<<i)
new = (a^newc)*(b^newc) # ans with set
if new>cur:
c = newc
print(c)
for testis in range(int(input())):
solve()
That was very silly, I shud have checked =0 and !=0.
Thnx for the reply. Appreciate it.
Bro you have done a tiny but big mistake. when you take AND of two numbers it can be any value. Not just 1 and 0. If bit is not set, then AND would be 0 using the mask(1<<i) but suppose if bit was set, the AND of that bit and mask would be a power of 2 not necesserily 1. If it was 1st bit, then AND would be 2, if 2nd bit, then 4. Simple words Take AND of 6 and 2, and we are checking for 1st bit ,then it is 2 not 1, cause in binary we see them as (110 and 010) and when you take their AND it becomes 010 which is 2 not 1 so in your if condition where you have written x==1 or y==1, write x!=0 or y!=0.
// Be greedy !!!
void Solve() {
ll n, a, b;
cin >> n >> a >> b;
ll x = 0;
for (ll i = n - 1; i >= 0; i--) {
// need to check whether by set this bit is maximize the result or not
ll prev = (a ^ x) * (b ^ x);
ll cur = (a ^ (x + (1LL << i))) * (b ^ ((x + (1LL << i))));
if (cur > prev) {
x += (1LL << i);
}
}
cout << x << endl;
}
why greedy approach should work?
Hey is writing “x |= (1<<i)” same as “x += (1<<i)” , if it is so then how ?
if let say ith bit is 0 then answer will be same in both cases but if ith bit is 1 then it changes. please tell.
Thanks for correcting!
heres my greedy approach:
You can always think in terms of binary representation…Check for yourself…Doing OR or simply adding won’t make any difference if not both of bits are same. In general OR of two numbers and adding will only be different when both bits are set…
1+0 == 1
1|0 == 1
0+1 == 1
0|1 == 1
0+0 == 0
0|0 == 0
But,…
1+1 == 2 i.e. 10
1|1 == 1 i.e. 01
But in this question, num always is power of 2, like 1000…and we are adding 1 bit to 0 bit, so it’s kind of similar to doing OR.
That actually sums up everything! Thank you 
A little bit twiddling:
#include <stdio.h>
int main() {
int n, a, b, r;
for(scanf("%*d"); ~scanf("%d%d%d", &n, &a, &b);) {
b ^= a;
r = b ? ~(a | b) | a & b ^ 1 << 31 - __builtin_clz(b) : ~a;
printf("%d\n", r & ((1 << n) - 1));
}
return 0;
}