BINFUN - Editorial

editorial
, , , ,
42

Here it is sir.

Screenshot (143)
Screenshot (143)1207×656 49.3 KB

43

That made me scratch my head a bit. But it is still wrong.
To make it easier for me to produce a counterexample I will assume your program only uses the approach for n\geq 1000. In that case it will give WA for the following case:

1
3
7 9 10

There exist similar cases where n\geq 1000 but those are much harder to understand.

1 Like
44

Sir, my code give 42 as answer.

45

Also if you modify your code to comply with this assumption?
Generating a test case with 1000 or more values is

  1. a lot of work
  2. doesn’t give a clear idea why a program breaks.

That is why I only made this small case.

Edit: If you want a larger test case: just duplicate one of the numbers until there are more than 1000 numbers

46

Ok @spaanse sir. Thanks for your time. I will go with your suggestion . :slightly_smiling_face:

47

In Simple way:-

Equation boils to (2MSBY​∗X+Y)−(2MSBX​∗Y+X) means suppose you have x=8 and y=4 then in binary 8 is 1000 and 4 is 100 now if you do x+y it becomes 1000100 means you can see bits of x are left shifted
by an amount of 3(and this 3 is len or msb of y) so by bits rule you can write x+y as x(2^msbY)+y and vice verse for y i.e; y*(2^msbX)+x so this part is clear.

1.Now after simplifying this eqaution becomes X*(2^msbY-1)-Y*(2^msbX-1) so you can see to maximize this the first part(X*(2^msbY-1)) should be maximum and second part(Y*(2^msbX-1)) should minimum.
2.So for this you can observe that as you maximize X its msbX is also maximize and as you minimize Y its msbY is also minimum.
3. Now take two array one for max_array_bit(of size 32 because at most bits size will be 32(A is 2^30) and one for min_array_bit
4.Max_array contain the array element whose msb is maximum and also the number itself should be maximum and min_array contains array element whose msb is min and number itself is minimum
5. 4 points explanation suppose 8 and 10 then both have msb as 4 but to maximize first part X should be maximum so we need 10 here and for second part to be minimum Y is minimum so take 8 here.
This is why we need max_bit array and min_bits_array.
6. Now two loop i and j from (1,32) here each i and j in max_array and min_array indicates the msb length of that number.
link:- 67kDhn - Online Python3 Interpreter & Debugging Tool - Ideone.com
That is all Thanks:)

3 Likes
48

@shashwatchandr Could you add some test cases to practice using the following generator. It generates test files that defeat algorithms that try to find the optimal solution using the largest value.

#include <iostream>
#include <vector>
#include <algorithm>
#include <time.h>
#include <stdlib.h>
#include <random>
using namespace std;

int randInRange(int min, int max) {
	return min + (rand() % (max-min));
}

int main() {
	srand(time(0));
	int numCase = 10;
	cout << numCase << endl;
	while (numCase--) {
		int N = 100000;
		cout << N << endl;

		int A = (1<<29);
		int Q = randInRange(0,(A-2)/3);
		int K = randInRange(0,Q);
		int P = randInRange(Q,(A-2)/3);

		vector<int> values(N);
		for (int i = 0; i < N; i++) {
			int type = rand()&1;
			if (type) {
				values[i] = randInRange(A+Q,A+P);
			} else {
				values[i] = randInRange(A-K,A);
			}
		}
		std::random_device rd;
	    std::mt19937 g(rd());
		shuffle(values.begin(), values.end(), g);
		for (int i = 0; i < N; i++) {
			if (i > 0) cout << " ";
			cout << values[i];
		}
		cout << endl;
	}
	return 0;
}
2 Likes
49

same as mine :stuck_out_tongue_winking_eye:

here is c++ solution

50

thank you bro!

51

please help,Shows wrong answer

#include
#include
#include
#include
#include
using namespace std;
int main(){
long long t{};
vector result{};
cin>>t;
for(long long i{};i<t;i++){
vector a{};

    long long n{},maxs{-1},mins{100000000000},sums{-1},msb{},msa{},maxsums{-1};
    cin>>n;
    for(long long j{};j<n;j++){
        long long b{};
        cin>>b;
        a.push_back(b);}
    sort(a.begin(),a.end());

vector v[32];
for(long long c:a)
{long long x{log2©+1};
v[x].push_back©;}
for(auto i:v)
sort(i.begin(),i.end());
for(long long j{};j<32;j++){
for(long long k{};k<32;k++){
if(v[k].empty() or v[j].empty())
continue;
mins = v[j][0];
maxs = v[k][v[k].size()-1];
msb = log2(v[j][0])+1;
msa = log2(v[k][v[k].size()-1])+1;
sums = abs((pow(2,msb)*maxs+mins)-(pow(2,msa)*mins+maxs));
if(sums>maxsums)
maxsums = sums;
}
}

result.push_back(maxsums);

}

for(long long c:result)
cout<<c<<endl;

}

53

format your code @g_himanshu0100

55

I am getting WA even though I am applying correct formula. Here is my code CodeChef: Practical coding for everyone

56

your explanation was good, i have derived the formula and got partial but was unable to get full.

1 Like