ZIO20003 - Editorial

editorial
, , , ,
1

Editorialist: Sudheera Y S

Problem Link : https://www.iarcs.org.in/inoi/2020/zio2020/zio2020-question-paper.pdf

Prerequisites : Sorting

Problem statement :

Given the scores of those who participated in ZIO and ZCO 2120 , you have to select the cutoff for ZIO say X and ZCO say Y , such that exactly K participants are selected and we have to minimize the difference |X-Y| and have to maximize X+Y if the difference is the same for two X and Y . We have to report X+Y

Idea :

We will sort the scores of all students ( it will be easy to calculate the number of students who will be selected if we keep some cutoff if we sort it ) and then for all i from min(0,k-m) to n ( where n is the number of participants in ZIO and m is the number of participants in ZCO ) we will have to select i students from ZIO and we have to select k-i students from ZCO and then calculate X-Y and also calculate X+Y and in all X-Y , we will take the least one and if there are many with the same difference we will select the one with maximum X+Y and that would be our answer :slight_smile:

Subtask A :

K = 6

Scores in ZIO: { 29 , 60 , 5 , 31 , 23 , 22 }

Scores in ZCO: { 18 , 1, 22 , 9 , 2 , 8 , 35 }

Sorted ZIO scores : { 5 , 22 , 23 , 29 , 31 , 60 }

Sorted ZCO scores : { 1 , 2 , 8 , 9 , 18 , 22 , 35 }

Note : Here i denotes the number of students selected from ZIO and k-i denotes the number of students selected from ZCO and we should also note that there are more ZCO students than K so when we say k-i , we need to be a bit more careful selecting the cutoff :

Goal : Minimize X and maximize Y making the difference X-Y minimum

  1. i = 0 , k-i = 6 → X = 61 , Y = 2 , X-Y = 59 , X+Y = 63
  2. i = 1 , k-i = 5 → X = 32 ( not 60 but 32 as we have to minimize X and Pejawara Matha if we keep it 31 , the number of students selected will increase ) , Y = 8 ( not 9 as the number of students selected will decrease ), X-Y = 24 , X+Y = 40
  3. i = 2 , k-i = 4 → X = 30 ( not 31 but 30 ) , Y = 9 , X-Y = 21 , X+Y = 39
  4. i = 3 , k-i = 3 → X = 24 , Y = 18 , X-Y = 6 , X+Y = 44
  5. i = 4 , k-i = 2 → X = 23 , Y = 22 , X-Y = 1, X+Y = 45
  6. i = 5 , k-i = 1 → X = 22 , Y = 23 , |X-Y| = 1 , X+Y = 45
  7. i = 6 , k-i = 0 → X = 5, Y = 36, |X-Y| = 31 , X+Y = 41

Note : In the last two cases ( i = 5 , i = 6 ) we maximized X and minimized Y because X < Y

Here we see that minimum X-Y is 1 and the maximum X+Y for those who has difference 1 is 45

Answer : 45

Subtask B :

K = 11

Scores in ZIO: { 21 , 10 , 9 , 45 , 7 , 12 , 14 , 47 , 29 , 17 }

Scores in ZCO: { 29 , 5 , 8 , 46 , 1 , 27 , 13 , 7 , 32 , 2 , 15 , 12 }

Sorted ZIO scores : { 7 , 9 , 10 , 12 , 14 , 17, 21 , 29 , 45 , 47 }

Sorted ZCO scores : { 1 , 2 , 5 , 7 , 8 , 12 , 13 , 15 , 27 , 29 , 32 , 46 }

Note : Here i denotes the number of students selected from ZIO and k-i denotes the number of students selected from ZCO and we should also note that there are more ZCO students than K so when we say k-i , we need to be a bit more careful selecting the cutoff :

Goal : Minimize X and maximize Y ( if X > Y ) and ( if X < Y ) then maximize X and minimize Y making the difference X-Y minimum

  1. i = 0 , k-i = 11 → X = 48 , Y = 2 , X-Y = 46, X+Y = 50
  2. i = 1 , k-i = 10 → X = 46 , Y = 5 , X-Y = 41 , X+Y = 51
  3. i = 2 , k-i = 9 → X = 30, Y = 7 , X-Y = 23 , X+Y = 37
  4. i = 3 , k-i = 8 → X = 22 , Y = 8 , X-Y = 14 , X+Y = 30
  5. i = 4 , k-i = 7 → X = 18, Y = 12 , X-Y = 6, X+Y = 30
  6. i = 5 , k-i = 6 → X = 15 , Y = 13 , X-Y = 2 , X+Y = 28

From here , we need to maximize X and minimize Y because X < Y minimizing X-Y

  1. i = 6 , k-i = 5 → X = 14, Y = 14, |X-Y| = 0 , X+Y = 28
  2. i = 7 , k-i = 4 → X = 12, Y = 16, |X-Y| = 4 , X+Y = 30
  3. i = 8 , k-i = 3 → X = 10, Y = 28, |X-Y| = 18 , X+Y = 38
  4. i = 9 , k-i = 2 → X = 9, Y = 30, |X-Y| = 21 , X+Y = 39
  5. i = 10 , k-i = 1 → X = 7, Y = 33, |X-Y| = 26 , X+Y = 41

Note : Here we cant take i = 11 , k-i = 0 because the total number of participants in ZIO is 10 and we cant select 11 participants from ZIO

Here we see that minimum X-Y is 0 and the maximum X+Y for those who has difference 0 is 28

Answer : 28

Subtask C :

K = 16

Scores in ZIO: { 47 , 28 , 49 , 35 , 52 , 38 , 43 , 39 , 34 , 57 , 20 , 18 , 48 }

Scores in ZCO: { 33 , 46 , 28 , 51 , 39 , 36 , 44 , 21 , 55 , 37 , 59 , 38 , 47 , 40 }

Sorted ZIO scores : { 18 , 20 , 28 , 34 , 35 , 38 , 39 , 43 , 47 , 48 , 49 , 52 , 57 }

Sorted ZCO scores : { 21 , 28 , 33 , 36 , 37 , 38 , 39 , 40 , 44 , 46 , 47 , 51 , 55 , 59 }

Note : Here i denotes the number of students selected from ZIO and k-i denotes the number of students selected from ZCO

Goal : Minimize X and maximize Y ( if X > Y ) and ( if X < Y ) then maximize X and minimize Y making the difference X-Y minimum

Note : Here the total number of participants in ZIO and ZCO are 13 and 14 respectively therefore we should select at least 2 participants from ZIO

  1. i = 2 , k-i = 14 → X = 50 , Y = 21 , X-Y = 29, X+Y = 71
  2. i = 3 , k-i = 13 → X = 49 , Y = 28 , X-Y = 21 , X+Y = 77
  3. i = 4 , k-i = 12 → X = 48, Y = 33 , X-Y = 15 , X+Y = 81
  4. i = 5 , k-i = 11 → X = 44 , Y = 36, X-Y = 8, X+Y = 80
  5. i = 6 , k-i = 10 → X = 40 , Y = 37, X-Y = 3, X+Y = 77
  6. i = 7 , k-i = 9 → X = 39 , Y = 38, X-Y = 1, X+Y = 77

From here , we need to maximize X and minimize Y because X < Y minimizing X-Y

  1. i = 8 , k-i = 8 → X = 38, Y = 39, |X-Y| = 1, X+Y = 77
  2. i = 9 , k-i = 7 → X = 35, Y = 40, |X-Y| = 5, X+Y = 75
  3. i = 10 , k-i = 6 → X = 34, Y = 41, |X-Y| = 7, X+Y = 75
  4. i = 11 , k-i = 5 → X = 28, Y = 45, |X-Y| = 17, X+Y = 73
  5. i = 12 , k-i = 4 → X = 20, Y = 47, |X-Y| = 27, X+Y = 67
  6. i = 13 , k-i = 3 → X = 18, Y = 48, |X-Y| = 30, X+Y = 66

Note : Here we are just consider i till 13 because the total number of participants of ZIO is 13 and we cant select more than 13 participants from ZIO

Here we can see that minimum X-Y is 1 and the maximum X+Y for those who has difference 1 is 77

Answer : 77

Hope you understood :slight_smile:

4 Likes
2

This is the best possible approach. Thanks for the efforts.

3 Likes
3

it’s tooooo long instead do one thing note that x-y=0 is best possible thing we can go for now see try to take most preferable numbers if still we cant get desired no. of students then go for x-y=1 and then try same way again…

4

Is there any good way to sort the list on pen paper as one would do in the actual ZIO?

5

Do we get a pen paper in ZCO to think?

6

We get a pen paper in ZIO to think and solve, not in ZCO.

7

Thats bad.
I have to think mentally then?
i read somewhere that we can use Paper Pen in ZCO

8

You do get paper in ZCO at the centre. You have to carry your own pen though.