IARCS Zonal Informatics Olympiad Question Paper ZIO 2018
Name of the Organisation : IARCS | Indian Association for Research in Computing Science
Name of the Paper : Zonal Informatics Olympiad Question Paper
Year : 2016,2017,2018
Website : http://www.iarcs.org.in/inoi/
Download Sample Question Paper :
2016 : https://www.pdfquestion.in/uploads/22908-zio2016.pdf
2017 : https://www.pdfquestion.in/uploads/22908-zio2017.pdf
2018 : https://www.pdfquestion.in/uploads/22908-zio2018.pdf
IARCS Zonal Informatics Olympiad Question
ZIO-2018 :
** The Zonal Informatics Olympiad, 2018 (ZIO-2018) was held at 34 cities across India on Saturday, 18 November, 2017. About 410 students wrote ZIO-2018.
Related : IARCS Zonal Informatics Olympiad Question Paper 2015 : www.pdfquestion.in/8176.html
Instructions to candidates
1. The question paper carries 80 marks, broken up into four problems of 20 marks each. Each problem has three Test Cases. If you solve all three Test Cases correctly, you get 20 marks for that problem. Otherwise, you get 5 marks for each Test Case that you solve correctly.
2. All the 4 3 = 12 Test Cases appear as separate Ques- tions in the right panel (\Question Palette”). The rst three Questions correspond to the three Test Cases of Problem 1, the next three correspond to the three Test Cases of Problem 2 and so on. A question icon turning green in the Question Palette, does not mean that it is correct. It just denotes that you have attempted it. All the questions will be evaluated later.
3. Attempt all questions. There are no optional questions.
4. There are no negative marks.
5. All expected answers are integers. Type in only the in- teger. So, if your answer is \162″, enter only \162″. Not \0162″, or \162.0″, etc.
6. Remember to save each answer. Only your nal saved answers will be considered.
7. Near the top-right corner, you should be able to see a calculator icon. Clicking it pops up a calculator which you may use.
Questions
1. You are given a list with N distinct positive integers: A[1];A[2]; : : : ;A[N]. A subset of these is said to be Good if all their indices have different remainders when divided by 5. In other words, consider a subset fA[i1];A[i2]; : : : ;A[ik]g. This is Good, if there are no x and y such that A[x] and A[y] have been selected to be in the subset, and the remainder when you divide x by 5 is the same as the remainder you get when you divide y by 5.
For instance, if the list has 30 elements A[1] to A[30], a Good subset cannot include both A[9] and A[24] because both 9 and 24 have remainder 4 when divided by 5. The Score of a subset is the sum of the values in it. You are given an integer K, and you should nd a Good subset of size at most K whose Score is maximized.Compute the maximum Score for the following instances.
(a) N = 21, K = 6,
A = [3; 8; 21; 13; 15; 4; 10; 17; 6; 12; 1; 11; 20; 14; 16; 5; 18; 19; 7; 9; 2]
|i.e., A[1] = 3, A[2] = 8, . . . , A[21] = 2
(b) N = 23, K = 4,
A = [4; 23; 15; 7; 9; 3; 20; 19; 8; 10; 1; 22; 16; 6; 14; 5; 21; 17; 11; 12; 2; 18; 13]
|i.e., A[1] = 4, A[2] = 23, . . . , A[23] = 13.
(c) N = 23, K = 4,
A = [17; 5; 21; 12; 1; 11; 10; 19; 9; 6; 18; 8; 23; 14; 2; 15; 3; 22; 13; 4; 16; 7; 20]
|i.e., A[1] = 17, A[2] = 5, . . . , A[23] = 20.
2. You have many balls. Each ball has a colour. The colours are numbered from 1 to 12. You are given a list with 12 integers: A[1];A[2]; : : : ;A[12]. You have a total of A[1] balls of Colour 1, A[2] balls of colour 2, . . . , A[12] balls of Colour 12. You also have B boxes, and you want to put these balls in the boxes. You don’t like boxes which have balls of different colours. You call such boxes Impure. And if a box has only balls of a single colour, you call it Pure. Each box can hold at most 10 balls. Sometimes, you are not able to ll all the balls such that all the boxes are Pure. So you want to minimize the number of Impure boxes. Given B, and A[1];A[2]; : : : ;A[12], you want to and the minimum number of Impure boxes you will have in the optimal strategy. You are guaranteed that you will be able to t in all the balls into B boxes. That is, A[1] + A[2] + ::: + A[12] 10 B.
Compute the minimum number Impure boxes for the following instances.
(a) B = 11, A = [8; 22; 4; 4; 9; 18; 8; 7; 1; 5; 7; 5]
|i.e., A[1] = 8, A[2] = 22, . . . , A[12] = 5
(b) B = 13, A = [9; 14; 11; 9; 9; 6; 7; 5; 6; 7; 16; 14]
|i.e., A[1] = 9, A[2] = 14, . . . , A[12] = 14
(c) B = 13, A = [15; 9; 7; 22; 7; 21; 6; 4; 11; 8; 7; 5]
|i.e., A[1] = 15, A[2] = 9, . . . , A[12] = 5
3. You are given a list of 0’s and 1’s: B[1];B[2]; : : : ;B[N]. A sublist of this list is any contiguous segment of elements|i.e., A[i];A[i + 1]; : : : ;A[j], for some i and j. A sublist is said to be Heavy, if the number of 1’s in it is at least as much as the number of 0’s in it.
We want to partition the entire list into Heavy sublists. That is, a valid partition is a collection of Heavy sublists, such that each of the N elements is part of exactly one of the sublists. We want to and the number of ways of doing so. For example, suppose N was 3 and B = [1; 0; 1]. Then all the sublists in this are Heavy, except for the sublist which contains only the second element ([0]). The various valid partitions are as follows :
( [1; 0; 1] )
( [1; 0]; [1] )
( [1]; [0; 1] )
Since there are 3 ways to do this, the answer for this would be 3. Compute the number of ways of partitioning the given list into Heavy sublists for the following instances.
(a) N = 8, B = [0; 1; 1; 0; 0; 1; 1; 1]|i.e., B[1] = 0;B[1] = 1; : : : ;B[8] = 1
(b) N = 9, B = 1; 1; 0; 0; 1; 0; 0; 1; 1|i.e., B[1] = 1;B[1] = 1; : : : ;B[9] = 1
(c) N = 9, B = 1; 0; 1; 0; 1; 1; 0; 1; 1|i.e., B[1] = 1;B[1] = 0; : : : ;B[9] = 1
4. You are given numbers N and K. Consider the set S = f1; 2; 3; : : : ;Ng. An ordered tuple is a sequence of integers from this set. For example, (2; 4; 1) is a tuple, and it is dierent from (1; 2; 4). You need to partition the integers f1; 2; 3; : : : ;Ng into ordered tuples such that each tuple has at most K integers. That is, you need to get a set of tuples, such that each element of S is in exactly one tuple, and each tuple has at most K elements. Find the number of ways to do so.
Note that elements inside a single tuple cannot be reordered. But tuples can be reordered as a whole. For instance, if N = 3|i.e., S = f1; 2; 3g| then f (2; 3); (1) g and f (1); (2; 3) g are considered the same partitions. But f (3; 2); (1) g is a different partition.
For example, if N = 2 and K = 2, there are exactly 3 valid ways to partition S, as given below :
f (1); (2) g
f (1; 2) g
f (2; 1) g
Compute the number of ways to partition f1; 2; 3; : : : ;Ng into ordered tuples of size at most K for the following instances.
(a) N = 4, K = 3
(b) N = 5, K = 3
(c) N = 6, K = 3