BINFUN - Editorial

PROBLEM LINK:

Contest

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

DIFFICULTY:

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?

Answer
  • 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

Please add simple explanation how it boils down to these.

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
but answer is 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

Video Tutorial : https://www.youtube.com/watch?v=ZLv_ugOUh2c
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