APPROX2 - Editorial

Problem link : contest practice

Difficulty : CakeWalk

Pre-requisites : Basic programming language constructions knowledge

Problem : find the number of pairs for which |ai+aj-K| is minimal possible (and this minimal possible value), having the array a[] and the integer K given.

Explanation :

There were two subtasks.

In the first one N equals to 2. That means that the minimal difference will always be |a1+a2-K| because totally there will be only one pair.

In the second one, N is still fairly small, so we can check all possible pairs of {ai, aj} via a brute force. I.e. we can make two nested cycles, the first one for i and the second one for j and there check that |ai+aj-K| has the minimal possible value.

Actually, the problem can be solved for N <= 106 within the same time bounds, but it was decided not to add this subtask in order to enable more people to get the full points. See tester’s solution for the details on this solution.

Solutions : Setter Tester

Why does my solution got timed out (in Scala)?

Link- http://www.codechef.com/viewsolution/3943345

The same logic when implemented in C++ gave AC.

Link-http://www.codechef.com/viewsolution/3939668

My python solution does exactly this and only gets 31 points :frowning:

Here:

def read_mapped(func=lambda x:x):
    return map(func, raw_input().split(" "))
def read_int():
    return int(raw_input())

T = read_int()

for case in xrange(T):
    n, k = read_mapped(int)
    a = read_mapped(int)
    low = 10000000000
    low_c = 0
    for i in xrange(len(a)):
        for j in xrange(i+1, len(a)):
            currr = abs(a[i]+a[j]-k)
            if currr<low:
                low = currr
                low_c = 1
            elif currr==low:
                low_c += 1
    print low, low_c

to reduce time complexity,i have done like this:http://www.codechef.com/viewsolution/3942983
but still wrong answer:p
can anyone help?
what is the problem with sorting?

My java code is also having same logic but gets only 31 points. Please tell me why is it so…???

import java.util.*;
import java.lang.*;
class Main
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int t,n,i,j,p,l,c;
long k,s,ans,min;

t=sc.nextInt();
for(i=1;i<=t;i++)
{
n=sc.nextInt();
k=sc.nextLong();
long a[]=new long[n];
c=0;

for(j=0;j<n;j++)
{
	a[j]=sc.nextLong();
}

if(n==2)
{
	s=a[0]+a[1];

ans=Math.abs(s-k);
System.out.println(ans+" "+"1");
}

else if(n>2)
{
if(n%2==0)
{
 min=Math.abs((a[0]+a[1])-k);

for(p=0;p<n;p++)
{
  for(l=p++;l<n;l++)
  {
  	s=Math.abs((a[p]+a[l])-k);
  	if(s<min)
  	{
  		min=s;
  	}
  	else
  		min=min;
}
   }

for(p=0;p<n;p++)
{
  for(l=p++;l<n;l++)
  {
  	s=Math.abs((a[p]+a[l])-k);
  	if(s==min)
  	{
  		c++;
  	}
  	else
  		c=c;
}
       }
     System.out.println(min+" "+c);
    }

else
{
min=Math.abs((a[0]+a[1])-k);

for(p=0;p<n;p++)
{
	if(p<(n-1))
	{
  for(l=p++;l<n;l++)
  {
  	s=Math.abs((a[p]+a[l])-k);
  	if(s<min)
  	{
  		min=s;
  	}
  	else
  		min=min;
}
     }
    }

for(p=0;p<n;p++)
{
	if(p<(n-1))
	{
  for(l=p++;l<n;l++)
  {
  	s=Math.abs((a[p]+a[l])-k);
  	if(s==min)
  	{
  		c++;
  	}
  	else
  		c=c;
}
    }
     }
System.out.println(min+" "+c);
     }
     }
  }
    }
         }

can someone please pinpoint to me my mistake in this code…i was getting correct answer on my console but WA when i try 2 submit dis…

#include<iostream>
#include<stdlib.h>
using namespace std;

int main()
{
    long long int t,i,m,n,j,c,k,a[1000],b;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cin>>k;
        for(i=0;i<n;i++)
            cin>>a[i];
        m = 1000000;
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                b = abs(a[i] + a[j] - k);
                if(b<m)
                {
                    m = b;
                    c = 1;
                }
                else if(b==m)
                    c++;
            }
        }
        cout<<m<<" "<<c<<endl;
    }
    return 0;
}
2 Likes

My code looks complicated compared to others. But it was working on my console, but gave wrong answer for codechef judge.
It became complicated because

  • I thought scanf will not read variable number of integers on single line and hence read things character by character.
  • I thought even though long long int will store one array element properly, it will not store sum of two very large numbers a[i]+a[j]. Hence used long long unsigned int. Now I am realising few guys with only int also got correct answer
  • Since I used long long unsigned int , abs does not have prototype for unsigned int, so manually created absolute.

I want to be sure if array elements were actually provided on single line separated by single space. Otherwise I dont know what could have gone wrong. If someone takes effort to read this code and suggest what could have gone wrong, it will really help.


#include<stdio.h>
#include<stdlib.h>
long long unsigned int notest,array[1002],n,c,d,swap,k,min1,min2,minval,count,absval,e;
char temp;

main()
{
scanf("%llu",&notest);
while (notest–)
{
scanf("%llu %llu",&n,&k);
min2 = 0;
minval = 0;
d = 1;

  e = 0;
  
  while(1)
	{

		temp = getchar();

	   if ((d==1) && (temp==10))
		continue;
	   if ((temp== 32) || (temp == '\t'))
		if (e!=0)
		{
		array[d++] = e;
		e = 0;
		continue;

		}
		else 
			continue;

	   if (temp== 10)
		break;

		if ((temp >=48) && (temp <=57))		   
			e = e* 10 + temp - 48;
	}
	array[d] = e;


	
	count = 0;
  	minval = 1000000001;

	for (c=1;c<=n;c++)
		for (d=c+1;d<=n;d++)
		{


		if ((array[c]+array[d])  > k)
			absval = array[c]+array[d] - k;
		else
			absval = k - (array[c]+array[d]);

		if (absval <  minval)
			{
				minval = absval;
				count = 1;
			}
		else if (absval ==  minval)
			{
				count++ ;
			}


		}

	printf("%llu %llu\n",minval,count);

}
return 0;
}

@aayushaggarwal although i have not participated in this contest but i would like to tell you O(nlog(n)) approached which is developed by me because i first thought that O(n^2) will not pass the test data.

so here is my approach
.firstly sort the given array
.for this mod(ai+aj-k) to be minimal you required (ai+aj) close to k
now start from the first element do this binary search for k-a[i] you can use lower_bound STL function now this number or the number just before this number are the only two number which can give ai+aj close to k now count the occurence of of this number if anyone of these may be your answer that can be easily find in logn using binary search but there is a flow in this algorithm you have to find the number of unordered pairs which can be find by avoiding duplicates This can also be done in a clever manner .whenever you do binary_search do it between the element next to the current element and the last element of the array .look at this code its a tested code

#include
#include<bits/stdc++.h>
using namespace std;
vector arr;
#define all(b) b.begin(),b.end()
int main(){

int t;
cin>>t;
while(t–){

int n,k;
cin>>n>>k;
arr.resize(n);
for(int i=0;i<n;i++)
cin>>arr[i];

int ans=INT_MAX,ans_count=0,num1;

sort(all(arr));

vector :: iterator it,it1;

for(it=arr.begin();it!=arr.end();++it){

 int num=k-*it;

 it1=lower_bound(it+1,arr.end(),num);
 if(it1!=arr.end()){
   num1=*it1;
   if(ans>abs(*it+num1-k)){
     ans=abs(*it+num1-k);
     ans_count=upper_bound(it+1,arr.end(),num1)-lower_bound(it+1,arr.end(),num1);
   }else if(ans==abs(*it+num1-k)){
     ans_count+=upper_bound(it+1,arr.end(),num1)-lower_bound(it+1,arr.end(),num1);
   }
 }
 it1--;
 if(it1!=it){
   num1=*it1;
   if(ans>abs(*it+num1-k)){
     ans=abs(*it+num1-k);
     ans_count=upper_bound(it+1,arr.end(),num1)-lower_bound(it+1,arr.end(),num1);
   }else if(ans==abs(*it+num1-k)){
     ans_count+=upper_bound(it+1,arr.end(),num1)-lower_bound(it+1,arr.end(),num1);
   }
 }

}

cout<<ans<<" "<<ans_count<<endl;
}

return 0;

}

6 Likes

Where I am getting it wrong ?
#include
#include
using namespace std;

int main()
{
int t,i ;
cin>>t;

for(i=0;i<t;i++)
{
    int n,j,m;
    long long int k,x,count=0;
   cin>>n;
   cin>>k;
    long long int a[1000];
    
    for(j=0;j<n;j++)
    {
        cin>>a[i];
    }

long long int min=2000000000;

    for(j=0;j<n;j++)
    {
        for(m=0;m<n;m++)
        {
            if(abs(a[j]+a[m]-k) < min )
            {
                if(j!=m)
                { 
                    min=abs(a[j]+a[m]-k);
                }
            }
             
        }
            
    }
    
    for(j=0;j<n;j++)
    {
        for(m=0;m<n;m++)
        {
            if(j==m)
            break;
            
          
            
            if(min==abs(a[j]+a[m]-k))
            if(j!=m)
            {
                count++;
            }
        }
    
    }
    
cout<< min;
cout<<" ";
cout<<count;    

}


    
    return 0;

}

http://www.codechef.com/viewsolution/3950897 . Please point out whats wrong in this code. It give TLE for subtask 2.

This can be solved using dp (kind of)
solution : https://www.codechef.com/viewsolution/11052793

https://discuss.codechef.com/users/25511/ma5termind
why are you using two condition of itrator

if(it!=arr.end())

And
it1–

If(it1!=it)
In your code please explain me

That is possible if the Problem Setter doesn’t increase the multiplier for that particular language.

I would request the tester to explain the O(NlogN) solution used by him . I am unable to understand from his code .

The problem setter should have either increased the multiplier for slow languages or he should have put restrictions on the slow languages(particularly functional languages) before putting up a contest.And because of such things the contestants who code using slow languages during contest despite of their logic,their effort goes waste.

1 Like

Even I was not able to get correct answer till end. But one possible error in your code can be initial value of m might be too small. Considering both a[i] and k can be up to 10^9, if all values are greater than your initial value 10^6, this answer will come wrong. Also if two array values are close to 10^9 then sum might not fit in long long int. but I found few solutions with long long int in correct answers. So test data might not have that scenario.

1 Like

@skysarthak: You are getting WA because of small value of m(as the value of a[j]+a[k] will be of atmost 2000000000).Hence you must set your value of m larger than 2000000000.Thus by making minor change in your code,it gave AC for all test cases.

Link-http://www.codechef.com/viewsolution/3943611

1 Like

initialize

c=0;

m=abs(a[0]+a[1]-k);

http://www.codechef.com/viewsolution/3943661

1 Like

Maximum value of abs(a[i]+a[j]-k) is 2*10^9 and not 10^9.

@aayush aggarwal i have provided an explanation of O(nlogn) solution at the end of this post .hope this will help you or if you find any difficuly then comment