iamdumb's blog

Correctness and Explaination of This DP solution Needed
By iamdumb, history, 9 years ago, In English

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)

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

They just forgot to check if the difference is bigger than d.

→ Reply