 # Can anybody explain the logic behind the lowest sum of contest 3 of dsa learning

please explain the lowest sum problem

You have to take all possible pair (satisfaction and motivation ) sum and find qith smallest sum

if i do in your apporach it will give TLE

So do you want to know approach?

Bro why we not calculate 3 4 before 1 5 & 1 6

It does not matter. They all result in 7.

why ??

We have to find sum. So, it does not effect which pair you add first.
1 + 4 = 5
2 + 4 = 6
1 + 5 = 6
3 + 4 = 7
1 + 6 = 7
2 + 5 = 7
2 + 6 = 8
3 + 5 = 8
3 + 6 = 9
Even if we add 3 and 4 first then also answer is 7.

brother if we calculate ist sum 5 2nd sum 6 and third is 7 and fourth is again 6

Bro we have to find Qi th smallest element

brother is the approach is to collect all pairs having sum 5 and then 6 and then 7

Yeah kind of

and then we have calculate qi th smallest element

have you solve this question

final res vector need to be sort in order to get kth smallest number

yes

anyone make this code if not lets have a challenge to solve it first!!

Here’s the idea. q_i is small. We can directly find the first 10^4 elements of the sum sequence in order by keeping a global priority queue (min-heap) that stores, for each a_i, the values of a_i + b_j, where b_j is the minimum value in b that has not yet been summed with a_i. Keep taking the top (minimum, in this case) element from the priority queue and putting new b_j's in until you get all the elements you want. Complexity is O(T\min(K^2, 10^4)\log{K}).