 # How to approach BINFUN for 100 Points?

Problem: BINFUN

1 Like

If you think about what the function is really doing,
XplusY = X left shifted by length of binary representation of Y + Y
YplusX = Y left shifted by length of binary representation of X + X
And then maximizing, XplusY - YplusX

By length of binary representation I mean,
The number of bits upto the MSB
6-> 110, length = 3
12-> 1100, length = 4

let n = length of binary representation of X
let m = length of binary representation of Y

We have to maximize, X * 2^m + Y - (Y * 2^n + X)
=> X * (2^m-1) - Y * (2^n - 1)

To maximize this, notice that n and m can only be in range [1, 30]
For a fixed (n,m) we can maximize this by taking the maximum X (having n bits) and minimum Y (having m bits). Do this for every (n,m) pair.
Reference

21 Likes

Ah!! I was too close… btw, nice explaination. can u please give some counter test case where “https://www.codechef.com/viewsolution/36019868” fails ?

1 3 4 5
Correct output: 9 (using 3 and 4)

1 Like

1
5
10 7 8 9 5
Ans is 49

``````void solve(){
int n;
cin >> n;
ll a[n];
for (int i = 0; i < n; ++i)
{
cin >> a[i];
}
ll X = {noOfBits(a), a};
ll Y = {noOfBits(a), a};
// X*(2^n - 1) - Y*(2^m - 1)
// find smallest m -> with biggest X
// find biggest n -> with smallest Y
for (int i = 1; i<n; i++) {
int temp = noOfBits(a[i]);
if (temp < X ) {
X = temp;
X = a[i];
}
else if (temp == X) {
if (a[i] > X ) {
X = a[i];
}
}
if (temp > Y ) {
Y = temp;
Y = a[i];
}
else if (temp == Y) {
if (a[i] < Y ) {
Y = a[i];
}
}
}

cout << (X * ((1<<Y) - 1)) - (Y * ((1<<X) - 1)) << "\n";
}
``````

I am choosing biggest X with smallest “m” bits and vice-versa for Y.
What’s wrong with this?

Hello @gajrajgchouhan.
Considering the expression - X*(2^n - 1) - Y*(2^m - 1) , you are maximising (2^n-1) and minimising (2^m-1), which doesn’t necessarily maximise the expression before.
A simple example to counter your approach is with integers - 2, 6;
Binary Representation of 2,6 is 10,110 respectively.
BinaryConcatenation(2,6) = (10110) - (11010) = -4
BinaryConcatenation(6,2) = (11010) - (10110) = 4

Your approach gives -4 as result, but the maximum value would be 4.
Hope this was helpful to you.

1 Like

Thank you bro 