SMPAIR - Editorial

Problem link : contest practice

Difficulty : CakeWalk

Pre-requisites : Sorting

Problem : Given a sequence a1, a2, …, aN. Find the smallest possible value of ai + aj, where 1 ≤ i < jN

Explanation

This problem was the easiest one in the set and it was intended to enable everybody to get some points.

How to get 13 points

Here you have only two integers a1 and a2, so the only possible sum will be a1+a2.

How to get 60 points

The constraints were designed in such a way that you can iterate through all the possible pairs (i, j), where 1 ≤ i < jN and check for every obtained sum, whether it’s the minimal one.

How to get 100 points

The answer is basically the sum of the minimal and the second-minimal element in the array. So you can simply iterate through all the numbers, keeping track of the minimal and the second-minimal number. Or if your programming language has built-in sorting, you can act even simpler, because after the sorting of the array in increasing order, the required minimal and the second-minimal will be the first and the second elements of the sorted array.

Related links

  • Reference in the built-in sorting for C++ users

Solutions : setter tester

1 Like

It can be done without sorting also.Check my solution click here

yeah no need to sort the inputs…just an inbuilt min() is enough in python…

Sorting will increase the complexity to O(nlogn), but a simple approach will be of O(n) i.e. iterating through the elements once or twice. Hence I preferred O(n) approach!

3 Likes

The question says i<j.
So for

2,1,3,4

the answer should be 1+3 =4 but sorting gives answer 1+2=3.
Please clarify my doubts.

4 Likes

Hey guys. My logic seems correct still I was getting WA for 3/4 of test cases.

Any suggestion ?

@y0g1337h your code is giving wrong answer [here][1] .output should be 4 but it is giving 6. Hope it helps . Here is your corrected


[2]


  [1]: https://ideone.com/W5hmPn
  [2]: http://www.codechef.com/viewsolution/4162583
1 Like

Please help me and tell whats the mistake in my code CodeChef: Practical coding for everyone

I really got frustrated when my code here din’t work at all
There might be some silly mistake I am doing
But I don’t know what is it?

guys my submission for this question is giving TLE for first two cases but correct for the other two . Can I know why is it happening so ?

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

The problem statement says, find smallest a[i]+a[j] such that 1 <= i < j <= n. If we sort the array, won’t that disturb the order? If this algo is giving AC, then the problem statement shold be changed to 1 <= i,j <= N

5 Likes

Yeah it is too easy for me as i have written it for 13pts(and i have achieved it) its just the sum of those 2 input value here is my code…


program SMPAIR;

var
   T,num,sum:longint;
   N:smallint;
begin
	(* Solution to SMPAIR *)
	readln(T);
	while T <> 0 do
	begin
	readln(N);
	sum := 0;
	while N <> 0 do
	begin
	read(num);
	sum := sum + num;
	dec(N);
	end;
	writeln(sum);
	dec(T);
	end;
end.

Only using printf and cout made a difference , it failed last subtask with cout but passed with printf , same code :stuck_out_tongue: Also, I wasted a hour finding the bug which was just the absence of newline character :stuck_out_tongue:

i m not getting this constraint concept… plzz explain one constriant in brief so thati can code

#include
using namespace std;
int main()
{long long t,n,i,min;

cin>>t;
while(t–)
{ cin>>n;
long long A[n];
for(i=0;i<n;i++)
{cin>>A[i];
}
min=A[0]+A[1];
for(i=0;i<n;i++)
{ if((A[i]+A[i+1])<=min)
min=A[i]+A[i+1];
}
cout<<min<<endl;
}
return 0;
}

wats d problem in my code???

what is wrong in my code…its showing wrong answer
#include
using namespace std;
int main()
{
int t,n,y,largest,smallest,secondSmallest;
cin>>t;
while(t–)
{
cin>>n;
int a[n];
y=0;
while(y<n)
{
cin>>a[y];
y++;
}
largest=a[0];
smallest=a[0];
y=1;
while(y<=n)
{
if(a[y]>largest) largest=a[y];
if(a[y]<smallest) smallest=a[y];
y++;
}
if(smallest!=largest)
{
secondSmallest=largest;
y=0;
while(y<=n)
{
if(a[y]<secondSmallest && a[y]!=smallest) secondSmallest=a[y];
y++;
}
}
cout<<smallest+secondSmallest<<endl;
}
}

Java code : AC 100 pts
https://www.codechef.com/viewsolution/10829126

hey i get the result as wrong answer in codechef for my code but while executing the code in my compiler it runs good and gives correct answer

#include

using namespace std;

int main()
{int t,n,a[10],sum,j,i,temp=1000;
cin>>t;
while(t–)
{cin>>n;
for(i=0;i<n;i++)
{cin>>a[i];
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
sum=a[i]+a[j];
if(sum<temp)
temp=sum;

}

}
cout<<temp<<endl;

}
return 0;
}

whats wrong i it?

#include
using namespace std;

int main()
{
long long t,n,sum=0,i,min=1000000;
long long a[1000];
cin>>t;
int j=0;
while(j<t)
{
cin>>n;
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<n-1;i++)
{
sum=a[i]+a[i+1];
if(sum<min)min=sum;
}
cout<<min<<endl;
j++;
}

return 0;

}
why i am getting WA??Can anyone help??

but you are essentially finding the smallest and second smallest element.