You are not logged in. Please login at www.codechef.com to post your questions!

×

TACHSTCK - Editorial

5
4

Problem Link:

Practice
Contest

Difficulty:

Cakewalk

Pre-requisites:

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:

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

Justifications:

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

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

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

utkarsh_lath's gravatar image

5★utkarsh_lath ♦♦
255385251
accept rate: 0%

edited 06 Feb '14, 01:54

garakchy's gravatar image

1★garakchy
1.1k163048

fix cook tag please

(22 Jul '13, 00:06) jarekczek3★

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

(22 Jul '13, 00:26) maggu2★

@maggu you are right. fixed.

(22 Jul '13, 00:33) utkarsh_lath ♦♦5★

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

link

answered 21 Jul '14, 13:47

arjun045's gravatar image

1★arjun045
1
accept rate: 0%

//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; }

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

}

link

answered 31 Aug '14, 01:51

anichavan20's gravatar image

2★anichavan20
9314
accept rate: 0%

edited 31 Aug '14, 01:52

@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

link

answered 27 Jun '15, 21:20

shashaa35's gravatar image

4★shashaa35
15114
accept rate: 0%

edited 27 Jun '15, 21:20

https://www.codechef.com/viewsolution/12375437 Can someone please help what is wrong with this?? Thank you.

link

answered 31 Dec '16, 18:21

rs_14's gravatar image

3★rs_14
1
accept rate: 0%

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

link

answered 13 Jan, 10:07

krishnakumarag's gravatar image

0★krishnakumarag
1
accept rate: 0%

link

answered 05 Jun, 16:42

ankushar456's gravatar image

1★ankushar456
3
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,340
×1,155
×738
×592
×8
×3

question asked: 22 Jul '13, 00:01

question was seen: 4,534 times

last updated: 05 Jun, 16:42