How to approach BINFUN for 100 Points?

help
1

Problem: BINFUN

1 Like
2

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
3

Ah!! I was too close… :pensive: btw, nice explaination. :wink:

4

can u please give some counter test case where “CodeChef: Practical coding for everyone” fails ?

5

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

1 Like
6

1
5
10 7 8 9 5
Ans is 49

7 
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?

8

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
9

Thank you bro :slight_smile: