# 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[2] = {noOfBits(a[0]), a[0]};
ll Y[2] = {noOfBits(a[0]), a[0]};
// 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[0] ) {
X[0] = temp;
X[1] = a[i];
}
else if (temp == X[0]) {
if (a[i] > X[1] ) {
X[1] = a[i];
}
}
if (temp > Y[0] ) {
Y[0] = temp;
Y[1] = a[i];
}
else if (temp == Y[0]) {
if (a[i] < Y[1] ) {
Y[1] = a[i];
}
}
}

cout << (X[1] * ((1<<Y[0]) - 1)) - (Y[1] * ((1<<X[0]) - 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