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

×

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

This question is marked "community wiki".

asked 29 Jun '14, 14:01

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
accept rate: 0%

edited 16 Jun '15, 12:02

vicky002's gravatar image

1★vicky002 ♦♦
2561314

please check what is wrong in the given code. online judge gave wrong answer for this

include<iostream>

include<algorithm>

using namespace std; int main() { int t,n,i,j; cin>>t; while(t--) { cin>>n; int a[n]; for(i=0;i<n;i++) cin="">>a[i]; sort(a,a+n); cout<<a[0]+a[1];

}
return 0;

}

(22 Jul '14, 09:25) ritujain10710★

can u suggest me few test cases also

(22 Jul '14, 09:29) ritujain10710★

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.

link

answered 29 Jun '14, 15:36

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

That is not important in fact. If you get i > j, then you can swap the values of i and j so that i < j.

In 2 1 3 4 we have i = 1, j = 2. Here you probably think that you should have i < j AND a[i] < a[j] but there was no such constraint in the statement.

(29 Jun '14, 15:42) xcwgf666 ♦♦6★

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

link

answered 29 Jun '14, 16:53

the65bit's gravatar image

4★the65bit
1.1k101328
accept rate: 13%

edited 29 Jun '14, 16:55

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

link

answered 20 Sep '14, 09:27

ketanhwr's gravatar image

6★ketanhwr
1.9k31844
accept rate: 15%

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

link

answered 29 Jun '14, 14:17

arajparaj's gravatar image

2★arajparaj
11
accept rate: 0%

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

(29 Jun '14, 14:28) brobear19952★

But sorting needs O(nlogn) complexity.

(29 Jun '14, 17:51) arajparaj2★

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

link

answered 29 Jun '14, 14:34

pvkcse's gravatar image

2★pvkcse
223
accept rate: 0%

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!

link

answered 29 Jun '14, 15:08

AnkitAti's gravatar image

1★AnkitAti
214
accept rate: 0%

Hey guys. My logic seems correct still I was getting WA for 3/4 of test cases. http://pastebin.com/pWZdstGV Any suggestion ?

link

answered 29 Jun '14, 16:44

y0g1337h's gravatar image

2★y0g1337h
11
accept rate: 0%

your code fails for test case

1

3

4 8 2

(01 Jul '14, 14:28) tech_boy2★

Please help me and tell whats the mistake in my code http://www.codechef.com/viewsolution/4168005

link
This answer is marked "community wiki".

answered 01 Jul '14, 02:49

naman1g2_10's gravatar image

2★naman1g2_10
11
accept rate: 0%

Please explain what is your logic as it hard to understands others code!

(01 Jul '14, 14:31) tech_boy2★

Probably you have misunderstood the question. It is not that complicated as you think.

(01 Jul '14, 19:56) yash_155★

@yash_15 tell the mistake?

(01 Jul '14, 23:35) tech_boy2★

Can you please give me some test cases for which my code fails so that i could improve it. Thanks for helping me.

(02 Jul '14, 17:29) naman1g2_102★

My ans is accepted by making some modifications.Thank for ur help.

(02 Jul '14, 20:56) naman1g2_102★

I really got frustrated when my code http://www.codechef.com/viewsolution/4157055>here din't work at all There might be some silly mistake I am doing But I don't know what is it?

link

answered 01 Jul '14, 17:50

nikhilnikhil's gravatar image

1★nikhilnikhil
1
accept rate: 0%

Since your code does not work for n=2 also, there must be some problem in your input. I dont think that the complex things you did to 'save' space was needed at all.

(01 Jul '14, 20:01) yash_155★

Hey!. Congrats your problem is solved you didn't put \n in printf due to which you were getting wa. But now 3 cases are solved and only 1 is left. So keep trying...

(02 Jul '14, 17:58) naman1g2_102★

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

link

answered 09 Jul '14, 15:39

max0505's gravatar image

1★max0505
1
accept rate: 0%

removing $memset$ should work! You don't need to initialize the array everytime.

(30 Dec '15, 16:19) sarvagya39434★

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.

link

answered 22 Jun '15, 20:55

vinay_2003's gravatar image

1★vinay_2003
313
accept rate: 0%

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

link

answered 30 Jun '15, 23:13

theweblover007's gravatar image

2★theweblover007
10116
accept rate: 0%

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

link

answered 27 Jul '15, 22:51

deeksha_garg's gravatar image

3★deeksha_garg
254
accept rate: 0%

include<iostream>

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???

link

answered 29 Dec '15, 17:51

shivam2296's gravatar image

3★shivam2296
173
accept rate: 0%

what is wrong in my code.....its showing wrong answer

include<iostream>

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

link

answered 02 Mar '16, 17:59

yash_23's gravatar image

0★yash_23
1
accept rate: 0%

link

answered 15 Jul '16, 21:01

abhishek893rai's gravatar image

0★abhishek893rai
1
accept rate: 0%

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 <iostream>

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?

link
This answer is marked "community wiki".

answered 16 Jul '17, 12:33

gokul27's gravatar image

2★gokul27
31
accept rate: 0%

include<iostream>

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??

link

answered 09 Aug '18, 01:22

maruf_hasan's gravatar image

1★maruf_hasan
1
accept rate: 0%

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:

×1,613
×775
×13

question asked: 29 Jun '14, 14:01

question was seen: 7,453 times

last updated: 09 Aug '18, 01:22