# 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)?

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

My python solution does exactly this and only gets 31 points

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.

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