APPROX2 - Editorial

editorial
, ,
7

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

8

@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
9

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;

}

10

CodeChef: Practical coding for everyone . Please point out whats wrong in this code. It give TLE for subtask 2.

11

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

12

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

13

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

14

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

15

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
16

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
17

@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-CodeChef: Practical coding for everyone

1 Like
18

initialize

c=0;

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

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

1 Like
19

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

20

@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

21

thanks fr your help guys…

22

Nice .
Btw did you try to submit this one ?

23

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.

24

@aayush yes it is working

25

@aayush just submitted

26

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