Editorialist: Shubham Matta
Problem link: https://www.iarcs.org.in/inoi/2016/zio2016/zio2016-question-paper.pdf
8 Short Description : Given a list we have to choose the largest subset such that no pair differs by K.
Subset -
If A and B are sets and every element of A is also an element of B, then :
- A is a subset of B
a) Concept:
In above array we start by picking elements from left and leave the element ‘elem’ if ‘elem-K’ is already chosen in the final subset.
There may be multiple solutions but we just need length of largest subset.
So , start with 2:
2 --- pick
3 --- pick
7 --- pick
8 --- leave ( since 2 is already taken )
9 --- leave (Since 3 is already taken)
10 --- pick
13 --- leave ( Since 7 is already taken )
14 --- pick ( Since we did not pick 8)
15 --- pick ( Since we did not pick 9)
16 --- leave ( Since 10 already taken )
19 --- pick ( Since we did not pick 13)
20 --- leave
21 --- leave
22 --- pick
.
.
.
.
Final Subset
{ 2 , 3 , 7 , 10 , 14 , 15 , 19 , 22 , 26 , 27 , 31 , 34 , 38 }
With length = 13
b) Applying the above concept to this array:
2 --- pick
5 --- pick
9 --- leave (2 already taken )
11 --- pick
12 --- leave (5 already taken)
16 --- pick
.
.
.
.
.
Final subset
{2 , 5 , 11 , 16 , 19 , 25 , 30 , 33 , 44 , 58}
With length$ = 10$
c) Final Subset:
{2 , 3 , 4 , 6 , 7 , 8 , 12 , 16 , 18 , 20 , 22 , 26 }
With length = 12