Problem link : contest practice Difficulty : CakeWalk Prerequisites : Basic programming language constructions knowledge Problem : find the number of pairs for which a_{i}+a_{j}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 a_{1}+a_{2}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 {a_{i}, a_{j}} 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 a_{i}+a_{j}K has the minimal possible value. Actually, the problem can be solved for N <= 10^{6} 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.
This question is marked "community wiki".
asked 25 May '14, 14:00

@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+ajk) to be minimal you required (ai+aj) close to k now start from the first element do this binary search for ka[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<iostream>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){
} cout<<ans<<" "<<ans_count<<endl; } return 0; } answered 25 May '14, 15:44
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)
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

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. answered 25 May '14, 14:06
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)

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

My java code is also having same logic but gets only 31 points. Please tell me why is it so...???
answered 25 May '14, 14:20

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...........
answered 25 May '14, 14:37
1
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.
(25 May '14, 15:17)
1
@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.
(25 May '14, 15:21)
1
(25 May '14, 15:29)
thanks fr your help guys...
(25 May '14, 16:08)

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.
answered 25 May '14, 15:44

Where I am getting it wrong ? include <iostream>include <cmath>using namespace std; int main() { int t,i ; cin>>t;
long long int min=2000000000;
} answered 25 May '14, 17:22

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

This can be solved using dp (kind of) solution : https://www.codechef.com/viewsolution/11052793 answered 06 Aug '16, 23:43

https://discuss.codechef.com/users/25511/ma5termind if(it!=arr.end()) And If(it1!=it) answered 03 Jan, 00:43
@ma5termind Please answer my dout
(03 Jan, 00:46)

I would request the tester to explain the O(NlogN) solution used by him . I am unable to understand from his code .
@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