IARCS Zonal Computing Olympiad ZIO Question Paper : Indian Association for Research in Science
Name of the Organisation : IARCS | Indian Association for Research in Computing Science
Name of the Paper : Zonal Computing Olympiad
Year : 2016,2017,2015
Website : https://www.iarcs.org.in/inoi/2016/
Download Sample Question Paper :
2016 : https://www.pdfquestion.in/uploads/22915-zco2016.pdf
2015 MS: https://www.pdfquestion.in/uploads/22915-zco2015morning.pdf
2015 AS : https://www.pdfquestion.in/uploads/22915-zco2015afternoon.pdf
IARCS Zonal Computing Olympiad Question Paper
**The Zonal Computing Olympiad, 2015 (ZCO-2015) was held on Saturday, 6 December, 2014. About 280 students wrote ZCO-2015. 67 students have qualified for the Indian National Olympiad in Informatics, 2015 (INOI-2015).
Related : IARCS Zonal Informatics Olympiad Question Paper ZIO 2018 : www.pdfquestion.in/22908.html
Instructions to Candidates
1. Each problem has a time limit of 1 second.
2. The test data against which your code is evaluated during the contest is not nal. Your code will be tested against additional larger inputs in the nal evaluation, after the contest. Even if your program correctly solves all inputs during the exam, there is no guarantee that your program will pass all the testcases in the nal evaluation.
3. There are 2 problems: Bookshelves and Bamboo Art. Each problem has 2 Subtasks, so there are 4 Subtasks in all. These four Subtasks are displayed on the top bar in your contest page, as 4 Sections. Each Section/Subtask has 2 Questions, displayed on the right “Question Palette”. The
First Question is for C and the second for C++. Take care to submit your code in the Question corresponding to the language you are working in. You will not get extra marks for solving the same Subtask in 2 dierent languages.
For each problem, a program that works for Subtask 2 generally also works for Subtask 1. But, even if you have solved Subtask 2, you must remember to submit the same code for Subtask 1 and get it accepted.
4. You will nd a separate window called “Debugger Control”. Click on “Start Debugger” to open Dev-C++. You can develop your code using DevC++, and then copy-paste your program into the code-area. Minimize Dev-C++ to get back to the contest console. To get back again to Dev-C++, click the “Show Debugger” button in the “Debugger Control” window.
5. You must compile your code before submitting it.
6. If your code passes all the inputs, you will get the message “Execution Successful.” Note that this DOES NOT guarantee that you will get it right in the nal evaluation. If your code outputs a value that is not the expected answer for some testcase, you will get a message “Your code does not pass all the test cases.” If your code takes too long on some testcase, you will get a message “Time Limit exceeded for the current code.” If you have some run time errors, you will get pop-ups saying “XYZ.exe has stopped working”. You will have to click the “Close the program” button multiple times to get back to the contest console.
7. Note that a Green icon in the “Question Palette” does not mean that you got it right. It just means that you have answered it.
8. For each Subtask, your BEST submission will count, not just your LAST submission. If you have submitted code in both C and C++ for any Problem, the best among them will be considered.
9. At the beginning of each program, include a comment with your name, roll number and the problem number. For instance, if your name is Sachin Tendulkar, your roll number is 13001 and the problem you are writing a C/C++ program for is Bookshelves, add a comment of the form /* Sachin Tendulkar, 13001, Bookshelves */ at the top of your file.
Questions
Problem 1 : Bookshelves
Uncle Shiva is an avid collector of books. In his study he has two long shelves with N books in each of them. He has invited the artist Lavanya to decorate his study. Lavanya feels that the arrangement of books in the two shelves is not aesthetic. She has come up with a measure for the elegance of the two shelves called Skew. The Skew of the two bookshelves is dened to be the sum of the heights of the tallest books in each of the two shelves. Lavanya recommends rearranging the books between the two shelves so that the Skew is as small as possible.
On the other hand, Uncle Shiva prides himself as a balanced personality and always wants the two shelves to have an equal number of books, N in each. Lavanya is an artist, she merely recommends what needs to be done, leaving the actual rear- ranging to Uncle Shiva. Uncle Shiva on the other hand is lazy and would like to do very little work. As a compromise, Uncle Shiva is willing to exchange books between the two shelves K times and would like to do these exchanges cleverly so as to make the Skew as small as possible (via K swaps).
For example, suppose each shelf contained 5 books, where the heights of the books on the rst shelf are 3; 5; 2; 7 and 1, and the heights of the books on the second shelf are 14; 2; 3; 10 and
4. The Skew of this arrangement is 7+14 = 21. If K = 1, i.e., Uncle Shiva is willing to exchange only one book between the two, he can swap the book with height 2 in shelf 1 with the book with height 14 in shelf 2 and this will increase the Skew to 24! On the other hand if he swaps the book with height 7 in the rst shelf with the book with height 3 in the second shelf then the resulting arrangement has a Skew of 5 + 14 = 19. You can verify that if K = 1 then this is the smallest Skew that can be achieved. So for this case the answer is 19. Your task is to write a program that takes as input, N – the number of books in each shelf, K- the number of swaps that Uncle Shiva is willing to do, and the heights of the books on the two shelves, and computes the smallest Skew value that can be achieved through at most K swaps of books between the two shelves.
Input format :
** There is only one line, which contains ((2 N) + 2) space separated integers.
** The rst two integers are N and K.
** The next N integers, give the heights of the N books in the rst book shelf.
** The last N integers, give the heights of the N books in the second book shelf.
Output format :
**A single line with a single integer giving the minimum Skew that can be achieved via at most K swaps between the two bookshelves.
Test data :
**You may assume that the height of all the books like in the range between 0 and 108, both inclusive and that 1 N 105. Note that there may be more than one book with the same height on a ookshelf.
Subtask 1 (30 Marks):
**You may assume that K = 1.
Subtask 2 (70 Marks) :
**0 K N.
Sample input :
**5 1 3 5 2 7 1 14 2 3 10 4
Sample output :
**19
Explanation :
N = 5;K = 1
**The rst book shelf contains books with heights f3; 5; 2; 7; 1g.
**The second book shelf contains books with heights f14; 2; 3; 10; 4g
**This is same as the example explained above, and so the answer is 19.
Limits : Time limit : 1s
Problem 2 : Bamboo Art
Lavanya is installing a piece of bamboo art for the Siruseri Biennale. Her installation will consist of a sequence of bamboo shoots of increasing lengths, abstractly representing the ascent of culture in the world. She also wants to arrange the bamboo shoots so that the dierence in length betweenadjacent bamboo shoots remains the same, to maintain symmetry. She has with her a set of bamboo shoots. She will only use the bamboo shoots as they are, because cutting bamboo goes against her principles. Your task is to determine the maximum number of bamboo shoots she can use from this set as part of her installation. Suppose she had a collection of 7 bamboo shoots of lengths 15; 8; 10; 20; 17; 13; 5.
From these, she could pick bamboo shoots of lengths 13; 15 and 17 to form an installation of size 3. Alternatively, she could pick bamboo shoots of lengths 5; 10; 15 and 20 to form an installation of size 4. You can check that she cannot form an installation of size 5 or higher using this collection. In this task, you will be given a number N, describing the number of bamboo shoots in Lavanya’s collection and the lengths of the N bamboo shoots. You may assume that no two bamboo shoots in the collection have the same length. Your task is to output the size of the largest installation that Lavanya can create out of these bamboo shoots.
Input format :
There is only one line, which contains N + 1 space separated integers.
The rst integer is N, giving the number of bamboo shoots.
That is followed by N distinct, non-negative integers, giving the lengths of the N bamboo shoots.
Output format :
**One line containing a single integer giving the size of the largest installation that Lavanya can create.
Test data :
**You may assume that the lengths of the bamboo shoots lie in the range 0 to 105, both inclusive.
**You may also assume that all bamboo shoots have distinct lengths.
Subtask 1 (40 Marks) :
**You may assume that 1 N 400, where N is the number of bamboo shoots.
Subtask 2 (60 Marks) :
**You may assume that 1 N 2500, where N is the number of bamboo shoots.
Sample input :
**7 15 8 10 20 17 13 5
Sample output :
**4
Explanation :
**N = 7, and the bamboo shoots have lengths f15; 8; 10; 20; 17; 13; 5g. This is the same example explained above. So the answer is 4.
Limits : Time limit : 1s