SMPAIR - Editorial

general
, ,
1

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

Related links

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

Solutions : setter tester

1 Like
2

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

3

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

4

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

5

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!

6

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.

1 Like
7

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.

8

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

9

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

But sorting needs O(nlogn) complexity.

11

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

12

your code fails for test case

1

3

4 8 2

13

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

14

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?

15

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

16

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.

17

@yash_15 tell the mistake?

18

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

19

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…

20

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