Hello guys,Few days ago this question was asked in Codechef cookoff.I was able to understand greedy part of the editorial but could not convince myself with DP approach.
Things I did not understand, In the picking of Pairs,where are we checking the conditions in which pair's difference is strictly less than D.I could not see it anywhere.
So basically I want you to please explain it to me.The more detailed the more helpful(as I am dumb :P).Thank you have a nice day.
[](https://discuss.codechef.com/questions/72500/sumpair-editorial)
It doesn't say anything about any DP approach in the link you provided :/
But DP might be overkill, There is a very simple solution. Since ai > 0, we can see that for the smallest possible sum of ai + aj the pair of values should be minimum possible since for any other pair of numbers (ai', aj'), their sum will be bigger than the greedy solution since either ai' > ai or aj' > aj . So simply sort the array and find the two smallest umbers in the array. :)
They just forgot to check if the difference is bigger than d.