Problem Link:Difficulty:Cakewalk Prerequisites:Ad Hoc Problem:Given N sticks of lengths L[1], L[2], ... L[N] and a positive integer D. Two sticks can be paired if the difference of their lengths is at most D. Pair up as many sticks as possible such that each stick is used at most once. Quick Explanation:Sort the sticks by their lengths and let L be the sorted array. If L[1] and L[2] cannot be paired, then the stick L[1] is useless. Otherwise, there exists an optimal pairing where L[1] gets paired with L[2]. This gives rise to the following algorithm:
Justifications:
Setter's Solution:Can be found here Tester's Solution:Can be found here
This question is marked "community wiki".
asked 22 Jul '13, 00:01

answered 14 Jul '14, 15:55

why my solution is giving TLE? http://www.codechef.com/viewsolution/4361912 answered 21 Jul '14, 13:47

//what is wrong with this #include<iostream> #include<algorithm> #define ll long long using namespace std; int main() { ll n,d; cin>>n>>d; ll a[n]; for(ll i=0;i<n;i++) cin="">>a[i]; sort(a,a+n); ll cnt=0; for(ll i=0;i<n;i++) { if(a[i+1]a[i]<=d) { cnt++; i+=1; }
} answered 31 Aug '14, 01:51

@anichavan20 you are accessing nth element of array, which is throwing some garbage value.. when i=n1,you try to compute a[n]a[n1]... solve this.. you may try this http://www.codechef.com/viewsolution/4361912 answered 27 Jun '15, 21:20

https://www.codechef.com/viewsolution/12375437 Can someone please help what is wrong with this?? Thank you. answered 31 Dec '16, 18:21

I have done with this can you please provide some more test case for this problem. answered 13 Jan '17, 10:07

Why my code is wrong : https://www.codechef.com/viewsolution/14081239 answered 05 Jun '17, 16:42

fix cook tag please
If L[1] and L[2] cannot be paired then L[1] < L[2] + D If L[1]=L[2]+D1. Then (L[2]L[1])=1D <=D It should be L[1]<L[2]D .
@maggu you are right. fixed.