Binfun proof or logic

editorial
1 
while(t-->0)
   {
	  
	   
	   int n=ni();
	   long arr[]=new long[n];
	   long totalmax=-1;
	   for(int i=0;i<n;i++)
		   {arr[i]=nl();
		   totalmax=Math.max(totalmax, arr[i]);
		   }
	   long max=-1;
	   if(n<=800) {
	   for(int i=0;i<n;i++)
	   {
		   for(int j=0;j<n;j++)
		   {
			   String fir=Long.toBinaryString(arr[i])+Long.toBinaryString(arr[j]);
			   String sec=Long.toBinaryString(arr[j])+Long.toBinaryString(arr[i]);
			   
			   long ntr=Long.parseLong(fir,2);
			   long mtr=Long.parseLong(sec,2);
			   max=Math.max(max,ntr-mtr );
		   }
	   }
	   pn(max+"");
	   }
	   else
	   {
		   
			   for(int j=0;j<n;j++)
			   {
				   String fir=Long.toBinaryString(totalmax)+Long.toBinaryString(arr[j]);
				   String sec=Long.toBinaryString(arr[j])+Long.toBinaryString(totalmax);
				   
				   long ntr=Long.parseLong(fir,2);
				   long mtr=Long.parseLong(sec,2);
				   max=Math.max(max,ntr-mtr );
			   }
			   pn(max+"");
	   }
		  
	  
	   
   }

what is the concrete logic or proof for this algorithm?
Can someone please help me?

PS: this gives AC

2

The logic used here is to

  1. Bruteforce for N \le 10^3
  2. Sort the array.
  3. Calculate BinaryConcatenation() \forall A_i in A with max(A) and store the maximum.

This is incorrect actually but is Accepted due to weak test cases.

1 Like
3

Thanks bro. Yes I got it