 Cakewalk

# Problem:

Given N sticks of lengths L, L, … 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 and L cannot be paired, then the stick L is useless.
Otherwise, there exists an optimal pairing where L gets paired with L.

This gives rise to the following algorithm:

``` numpairs = 0 for ( i = 1; i < N; ) if (L* >= L[i+1] -D) // L and L can be paired numpairs++, // pair them up i += 2; else i++; // eliminate L ```

# Justifications:

• If L and L cannot be paired then
L < L - D
But, L <= L* for every i > 1
So    L < L - D* for every i > 1
Hence, L cannot be paired with anyone.

• If L and L can be paired.
Consider any optimal pairing and it can be transformed to a pairing where L and L are paired.
a) If the optimal pairing pairs L with L then we are done.
b) If only one of L and L is paired with someone, then we can replace that pair by (L, L).
c) If both L and L are paired and L is paired with L[n] and L with L[m], then we might as well form pairs (L, L) and (L[n], L[m]).
This is because
L <= L[m] <= L + D
L <= L[n] <= L + D <= L + D
⇒   -D <= L[m] - L[n] <= D

# Setter’s Solution:

Can be found here

# Tester’s Solution:

Can be found here

6 Likes

why my solution is giving TLE?
http://www.codechef.com/viewsolution/4361912

//what is wrong with this

#include
#include
#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*;
sort(a,a+n);
ll cnt=0;
for(ll i=0;i<n;i++)
{
if(a[i+1]-a*<=d)
{
cnt++;
i+=1;
}

``````}
cout<<cnt<<endl;
return 0;
``````

}

@anichavan20
you are accessing nth element of array,
which is throwing some garbage value…

when i=n-1,you try to compute a[n]-a[n-1]…

solve this…
you may try this http://www.codechef.com/viewsolution/4361912

https://www.codechef.com/viewsolution/12375437
Thank you.

I have done with this can you please provide some more test case for this problem.

Why my code is wrong : https://www.codechef.com/viewsolution/14081239

fix cook tag please

If L and L cannot be paired then
L < L + D
If L=L+D-1. Then (L-L)=1-D <=D
It should be L<L-D .

@maggu you are right. fixed.

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.
;
import java.io.;
import java.util.Arrays;
/
Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc= new Scanner(System.in);
int n,d,c=0,j=0;
n=sc.nextInt();
d=sc.nextInt();
int len[]=new int[n];
for(int i=0;i<n;i++)
{
len[i]=sc.nextInt();
}
Arrays.sort(len);
while(j<n-1)
{
if((len[j]-len[j+1])<=d)
{
c++;
j+=2;

``````	    }
else
{
j+=1;
}
}
System.out.println(c);
}
``````

}

Can someone help me. What is wrong with this solution?It is running in other editors but codechef is not submitting it .

#include
#include <bits/stdc++.h>
using namespace std;

int main() {
long n,d;
cin >> n;
cin >> d;
long arr[n];
int count=0;
for(int i=1;i<=n;i++){
cin >> arr[i];
}
int i=1;
int j=1;
long int max=0;
while(i<n)
{
j=i+1;
for(int m=j;m<=n;m++)
{
if(abs(arr[m]-arr[i])<=d)
{
count+=1;
max+=99;
arr[m]= max;
max+=99;
arr[i]=max;
break;
}
}
i++;
}

``````cout << count;
return 0;
``````

}

Giving TLE!!

This part of your code does not logically agree to the question. Also, you should increase the array size of arr[] by 1 else accessing arr[n] may return some garbage value.

#include <stdio.h>

int main(void)
{
// your code goes here
int n;
long d;
scanf("%d %ld",&n,&d);
int l[n];
int i;
for(i=0;i<n;i++)
{
scanf("%d",&l[i]);
}
i=0;
int k=0;
int j;
while(i<n-1)
{
for(j=i+1;j<n;j++)
{
if(l[i]>l[j])
{
if(d>=(l[i]-l[j]))
{
k++;
l[j]=‘x’;
break;

``````            }
}
else
{
if(d>=(l[j]-l[i]))
{
k++;
l[j]='x';
break;

}
}
}
i++;
}
printf("%d\n",k);
return 0;
``````

}

whats wrong in this can anyone explain me ??

https://www.codechef.com/submit/TACHSTCK
here it is

I understood what your code is doing, but not to ‘EXACTLY’ tell you that, here is a test case where your code is failing
4 1
1 2 121 121

Correct output- 2.

Try yourself and then look at the hints below.

Hint 1

There is a bug in line numbers 27 and 37

Hint 2

Initialize the l[i] to INT_MIN. That will prevent the error. Why this is happening coz the value of ‘x’ is 120 if you go to ascii chart. So, you are initializing l[i] to 120 everyone the difference is smaller. Initializing it to INT_MIN will solve the probelm

Hope this helps and please try yourself before looking at the hints. 1 Like