# BINFUN - Editorial

Contest

Setter: Shashwat Chandra
Tester: Yash Chandnani
Editorialist: Rajarshi Basu

Easy

# PREREQUISITES:

Binary Representation

# PROBLEM:

Consider the following function, where `+` denotes string concatenation.

``````function BinaryConcatenation(integer X, integer Y):
string binX = binary representation of X without leading zeroes
string binY = binary representation of Y without leading zeroes

string binXplusY = binX + binY
string binYplusX = binY + binX

integer XplusY = Convert binary representation binXplusY to integer
integer YplusX = Convert binary representation binYplusX to integer
return XplusY - YplusX
``````

You are given a sequence A_1, A_2, \ldots, A_N, Find the maximum value of BinaryConcatenation(A_i, A_j) over all valid i and j.

# EXPLANATION:

Observation 1

If you think about how the binary strings are written, the expression essentially boils down to the following

• (2^{MSB_Y}*X + Y) - (2^{MSB_X}*Y + X)
Observation 2

Itâs always a good idea to fix some portion of the variables, and vary the others. What are reasonable choices to fix here?

• Lets try to fix MSB_X and MSB_Y. There are a total of 30*30 choices for this.

What to do after this?

Main Observation

Our Eqn now becomes:

• (A*X+Y)-(B*Y+X)
• = X*(A-1) - Y(B-1)
• A = 2^{MSB_Y}
• B = 2^{MSB_X}

Therefore, if we increase X, our solution doesnât become worse. Similarly, if we decrease Y our solution doesnât become worse. Hence, we can take the max value for X and the min value for Y.

For details on implementation, look at testerâs code.

# SOLUTION:

Testerâs Code
``````#include <bits/stdc++.h>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

void pre(){

}
ll f[2][31][31];
void solve(){
int n;cin>>n;
rep(i,2) rep(j,31) rep(k,31) f[i][j][k] = -(1ll<<60);
rep(i,n){
ll x;cin>>x;
int y = 64-__builtin_clzll(x);
repA(j,1,30){
f[0][y][j] = max(f[0][y][j],(x<<j)-x);
}
repA(j,1,30) f[1][j][y] = max(f[1][j][y],x-(x<<j));
}
ll ans = 0;
repA(i,1,30) repA(j,1,30) ans=max(ans,f[0][i][j]+f[1][i][j]);
cout<<ans<<'\n';

}

int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
int n;cin>>n;
rep(i,n) solve();
return 0;
}

``````
10 Likes

9 Likes

Somebody please explain which rocket science is going on in solve function?

20 Likes

For Sample 2nd Input max is 128 and min is 1 so X=128 and Y=1.
MSBy = 1, A = 2
MSBx = 8, B = 256
output = 128*(2-1)-1(256-1) => -127

2 Likes

@rajarshi_basu please explain this line.From where we observe that??

so, just take X as 1 and Y as 128 you will get answer as 127.

This question was awesome , but the creativity of question was neutralised by bad test cases as few of them cracked using funky logics!

10 Likes

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 * 2m + Y - (Y * 2n + X)
=> X * (2m-1) - Y * (2n-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.

My_solution

credits @anon88063409

20 Likes

Hey @rajarshi_basu please bro make test cases strong ,from last two contest , TCâs are poor and some hack / brute force passed.

6 Likes

As the binary representations are concatenated then you can consider as it begin left shifted, which basically means it is being multiplied by 2 and when you consider that number too than you can assume that it is being added.
example -
let a-10010 b-101
b concatenated to a will be like 10010101
which we can get by 10010000 (left shifting by b) + 101(then adding b)

The above is done for both according to question and we get the final results as explained.

1 Like

look observation 1.

1. now take the only part which coontains X. i.e. , 2^(MSYy)*X-X.
let X is constant ans msbY is variable here. then there are 1 to 31 possible value exist for MSBy. so were they are finding all 31 possible values of 2^(MSBy)*x-x and storing it.
here x are the all numbers we will gonna scan.
secondâŚ for Y , its similar but just negative of what I said just above.
anything can be X and Y so we they made three D array where f[0][i][j] is for x and
f[1][i][j] is for Y .
now they are maximising it everytime time they scan a new value as it is already mentioned in explanation that maximise X and minimise Y for constant [or we can say some perticular j ( bit shift value (1 to 31) ] to maximise your answer.
sorry , If you didnât understood my explanation. :
2 Likes

@rajarshi_basu
I understood the editorial and got most part of it but when it comes to code it has horrible readability. I was scratching my head to figure out what the tester wrote in his code and other people too faced the issue.

You only provided one code (only testerâs) and that too comprises of irrelevant macros, no comment and shorthand notation everywhere, donât get me wrong but its your or testerâs responsibility to provide a understandable code. I would not have commented but the code provided was really horrible, it would have taken only 5-6 more min to write the clean code but seems like you guys donât even have that.

Thanks @ssrivastava990 for commented and âreadableâ code.

13 Likes

but how formula you derived?

@gurav_123 @ameybhavsar
bro see, suppose we have two numbers X= 1100 and Y=101. so the BinXplusY will be 1100101. Here you can observe that each bit of X has been Left shifted by 3 places i.e multiply X by 2^3. Also 3 is the MSB of Y. so the BinXplusY is 1100000+101 i.e [X2^(MSB of Y) +Y ] .
similarly BinYplusX = [Y
2^(MSB of X) +X ].
thus we return BinXplusY - BinYplusX i.e [X2^(MSB of Y) +Y ] - [Y2^(MSB of X) +X ].

9 Likes

why my soln https://www.codechef.com/viewsolution/35952767 got WA?? it should be partially correct

Thank you for ur explanationâŚ Got it now

Please Like Share and Subscribe my channel if you understand the Solution.

Can anyone tell me why this code is giving partial ? @avi_cr7 @rajarshi_basu @shashwatchandr

https://ide.geeksforgeeks.org/TZanul1iUw

for example X=5,Y=9
5 in bin rep has 3 digits and 9 has 4 digits
(2^4)*5+9=89 =XplusY
(2^3)*9+5=77=YplusX

1 Like

@avi_cr7 Can anyone tell what is wrong in my code. It is giving WA instead of TLE.
https://www.codechef.com/viewsolution/35977430