×

# APPROX2 - Editorial

 0 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 This question is marked "community wiki". asked 25 May '14, 14:00 719●43●63●77 accept rate: 0% I would request the tester to explain the O(NlogN) solution used by him . I am unable to understand from his code . (25 May '14, 15:12) @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 (25 May '14, 15:45)

@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<bits stdc++.h="">

using namespace std; vector<int> 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<int> :: 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;

}

1.7k11730
accept rate: 11%

Nice . Btw did you try to submit this one ?

(25 May '14, 16:42)

@aayush yes it is working

(26 May '14, 01:00)

@aayush just submitted

(26 May '14, 01:24)

is this work O(nlogn) in count solns for following test- 1 10 8 4 4 4 4 4 4 4 4 4 4

(26 May '14, 19:46)
1

@joney for each of test case it is O(nlog(n))

(26 May '14, 19:48)

O notation implies worst case for any type of the test case

(26 May '14, 19:48)

if you have any doubts regarding this post the ask i will try to clear your doubt

(26 May '14, 19:49)
showing 5 of 7 show all
 0 Why does my solution got timed out (in Scala)? The same logic when implemented in C++ gave AC. answered 25 May '14, 14:06 2★knb_dtu 410●6●20 accept rate: 22% That is possible if the Problem Setter doesn't increase the multiplier for that particular language. (25 May '14, 14:28) 1 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. (25 May '14, 15:15) knb_dtu2★
 0 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
 0 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? answered 25 May '14, 14:14 336●2●11●19 accept rate: 9%
 0 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;j2) { if(n%2==0) { min=Math.abs((a[0]+a[1])-k); for(p=0;p
 0 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 #include 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>a[i]; m = 1000000; for(i=0;i
 0 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 #include long long unsigned int notest,array[1002],n,c,d,swap,k,min1,min2,minval,count,absval,e; char temp; main() { scanf("%llu",¬est); 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; }  answered 25 May '14, 15:44 14●1●2●5 accept rate: 0%

Where I am getting it wrong ?

# include <cmath>

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;


}

2★specty
1
accept rate: 0%

 0 http://www.codechef.com/viewsolution/3950897 . Please point out whats wrong in this code. It give TLE for subtask 2. answered 28 May '14, 11:35 26●2 accept rate: 0%
 0 This can be solved using dp (kind of) solution : https://www.codechef.com/viewsolution/11052793 answered 06 Aug '16, 23:43 1 accept rate: 0%
 0 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 answered 03 Jan, 00:43 1●1 accept rate: 0% @ma5termind Please answer my dout (03 Jan, 00:46)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×1,688
×5

question asked: 25 May '14, 14:00

question was seen: 4,337 times

last updated: 03 Jan, 00:47