Problem : Given a sequence a1, a2, …, aN. Find the smallest possible value of ai + aj, where 1 ≤ i < j ≤ N
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 < j ≤ N 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.
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!
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
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 Also, I wasted a hour finding the bug which was just the absence of newline character
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++;
}