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

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


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

Link to my submission CodeChef: Practical coding for everyone
It is based on priority queue

as i don’t know priorty queue I made it simple my submission

thanks buddy @galencolin

The priority queue approach is fine. But how to solve it using binary search. I tried but it gives me TLE.

You could binary search on the minimal x such that at least q_i numbers are less than or equal to x. That’s a bit more complicated and requires something like two pointers (or a second binary search), but you can try it if you want

1 Like

Thanks for replying! I tried exactly as you said, also referred the second approach mentioned in this official editorial. I have used binary search to find minimal x and then two pointers. My Solution; would be great if you can please see it. Maybe the time limit is too strict.

Yeah, actually, reading the constraints, it seems like it would be really hard to make that pass. I think you’ve written it right though - as far as I know, that’s the best binary search solution you could use.

1 Like

Thanks !