You are not logged in. Please login at www.codechef.com to post your questions!

×

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

This question is marked "community wiki".

asked 25 May '14, 14:00

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
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) aayushagarwal2★

@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) ma5termind3★

@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<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){

 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;

}

link

answered 25 May '14, 15:44

ma5termind's gravatar image

3★ma5termind
1.7k11730
accept rate: 11%

Nice . Btw did you try to submit this one ?

(25 May '14, 16:42) aayushagarwal2★

@aayush yes it is working

(26 May '14, 01:00) ma5termind3★

@aayush just submitted

(26 May '14, 01:24) ma5termind3★

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) joney_0004★
1

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

(26 May '14, 19:48) ma5termind3★

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

(26 May '14, 19:48) ma5termind3★

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

(26 May '14, 19:49) ma5termind3★
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.

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

link

answered 25 May '14, 14:06

knb_dtu's gravatar image

2★knb_dtu
410620
accept rate: 22%

edited 25 May '14, 15:25

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

(25 May '14, 14:28) wittyceaser2★
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★

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
link

answered 25 May '14, 14:11

svineet's gravatar image

3★svineet
362410
accept rate: 0%

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

(25 May '14, 15:37) sniper62★

low is 10*10 not 10**9. And it hits a TLE in the second subtask, even though the same thing in c++ gets through.

(25 May '14, 18:08) svineet3★

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?

link

answered 25 May '14, 14:14

rudra_sarraf's gravatar image

3★rudra_sarraf
33621119
accept rate: 9%

edited 25 May '14, 14:21

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);
     }
     }
  }
    }
         }
link

answered 25 May '14, 14:20

heart1_winner1's gravatar image

2★heart1_winner1
1
accept rate: 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<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;
}
link

answered 25 May '14, 14:37

skysarthak's gravatar image

3★skysarthak
453
accept rate: 0%

edited 25 May '14, 14:39

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) ravikadam2★
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.

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

(25 May '14, 15:21) knb_dtu2★
1

initialize

c=0;

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

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

(25 May '14, 15:29) letsctheworld3★

thanks fr your help guys...

(25 May '14, 16:08) skysarthak3★

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",¬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;
} 
`
link

answered 25 May '14, 15:44

ravikadam's gravatar image

2★ravikadam
14125
accept rate: 0%

edited 25 May '14, 15:54

Where I am getting it wrong ?

include <iostream>

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;

}

link

answered 25 May '14, 17:22

specty's gravatar image

2★specty
1
accept rate: 0%

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

link

answered 28 May '14, 11:35

aditya1495's gravatar image

6★aditya1495
262
accept rate: 0%

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

link

answered 06 Aug '16, 23:43

saurabh_mumbai's gravatar image

2★saurabh_mumbai
1
accept rate: 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

link

answered 03 Jan, 00:43

its__nishant's gravatar image

3★its__nishant
11
accept rate: 0%

edited 03 Jan, 00:47

@ma5termind Please answer my dout

(03 Jan, 00:46) its__nishant3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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