RLCAT - Robert Langdon & Class Attendance

no tags 

With growing popularity of Robert in Harvard, many students have started opting for his course on Symbolism as institute elective course. Class strength has increased to an extent that even with his eidetic memory; Robert is having a hard time remembering faces of the students in his class. This made him switch to using attendance sheet to take attendance of the class.
Imagine N students sitting in a straight row, students are numbered 1 to N. Attendance sheet is first given to student 1, who uses his own pen to sign the sheet. Then he passes the sheet to student 2, and chooses wheather or not to give him the pen too. If student 2 doesn't get a pen from student 1, he will take out his own pen. Student 2, after signing the sheet, will pass the sheet to student 3, and again makes a choice wheather or not to pass the pen. Note that he can even pass the pen that came to him from student 1.
So first student's pen might end up being used by the entire class.
A person becomes annoyed if his pen is used by someone who is not his friend. Each person has a "compatibility value", and two students are friends if the absolute difference of their compatibility values is less than or equal to a given threshold D.
Given compatibility values of each student in the class, find the minimum number of students that must take out their pens to sign so that no one gets annoyed.
NOTE : it is not allowed that a person gets a pen from his neighbour, and passes it along without using it (i.e., uses his own pen for his attendance and passes ahead the pen of his neighbour).
INPUT:
First line contains T, number of test cases
Each test case has two lines
First line of each test case contains two space separated integers N and D, indicating the number of students in the class and friendship threshold respectively.
Next line contains a space separated array A of N elements, A[i] being the compatibility value of ith student.
OUTPUT:
For each testcase, output in a single line minimum number of pens that must be taken out so that the whole class is able to mark the attendance and no one gets annoyed.
EXAMPLE INPUT:
2
5 2
3 1 2 4 5
5 3
1 4 7 1 5
EXAMPLE OUTPUT:
1
2
CONSTRAINTS:
1<=T<=1000
1<=N<=300000
1<=D<=10^9
Sum of all N over all test cases will not exceed 300000
1<=A[i]<=10^9

With growing popularity of Robert in Harvard, many students have started opting for his course on Symbolism as institute elective course. Class strength has increased to an extent that even with his eidetic memory; Robert is having a hard time remembering faces of the students in his class. This made him switch to using attendance sheet to take attendance of the class.

Imagine N students sitting in a straight row, students are numbered 1 to N. Attendance sheet is first given to student 1, who uses his own pen to sign the sheet. Then he passes the sheet to student 2, and chooses wheather or not to give him the pen too. If student 2 doesn't get a pen from student 1, he will take out his own pen. Student 2, after signing the sheet, will pass the sheet to student 3, and again makes a choice wheather or not to pass the pen. Note that he can even pass the pen that came to him from student 1.

So first student's pen might end up being used by the entire class.

A person becomes annoyed if his pen is used by someone who is not his friend. Each person has a "compatibility value", and two students are friends if the absolute difference of their compatibility values is less than or equal to a given threshold D.

Given compatibility values of each student in the class, find the minimum number of students that must take out their pens to sign so that no one gets annoyed.

 

NOTE : it is not allowed that a person gets a pen from his neighbour, and passes it along without using it (i.e., uses his own pen for his attendance and passes ahead the pen of his neighbour).

 

INPUT:

First line contains T, number of test cases

Each test case has two lines

First line of each test case contains two space separated integers N and D, indicating the number of students in the class and friendship threshold respectively.

Next line contains a space separated array A of N elements, A[i] being the compatibility value of ith student.

 

OUTPUT:

For each testcase, output in a single line minimum number of pens that must be taken out so that the whole class is able to mark the attendance and no one gets annoyed.

 

EXAMPLE INPUT:

2

5 2

3 1 2 4 5

5 3

1 4 7 1 5

 

EXAMPLE OUTPUT:

1

2

 

CONSTRAINTS:

1<=T<=1000

1<=N<=300000

1<=D<=109

Sum of all N over all test cases will not exceed 300000

1<=A[i]<=109


hide comments
heatOn: 2014-02-01 18:19:49

Why isn't there c++11 on spoj ?


Added by:Piyush Kumar
Date:2014-01-15
Time limit:1s-1.939s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM32-GCC MAWK BC C-CLANG NCSHARP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:IIT Bombay Coding GC