ZIO16004 - Editorial

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