These are the Questions from Zonal Computing Olympiad 2018 Exam of International Infromatics Olympiad held in Tsukuba, Japan.
Problem 1 : BIRTHDAY-CAKES
In a birthday party, there are C cakes and N children. There is also an integer k, given.
But since eating too much of cakes can give you toothache, each of the children have been prescribed by doctors to eat cakes that fall only within a specific interval (a,b) both inclusive.
If k = 0, you have answer if any of the students’ ranges clash or not.
That is print “GOOD” ( without quotes ) if ranges do not clash and “BAD” ( without quotes ) if they will fight over their share of cakes.
If k=1, then you have a chance to stop them to stop them from fighting. You are allowed to move at max 1 child from his place and allot him a different range, PROVIDED THAT HE IS STILL ABLE TO HAVE THE SAME NUMBER OF CAKES AS HE WOULD HAVE HAD IN HIS PREVIOUS RANGE.
If you can prevent all the fights among the children, by ‘moving’ only one child , print “GOOD” ( without quotes ) , else print “BAD” ( without quotes ).
A single line containing an integer t, denoting the number of test cases.
For each test case, input 3 space separated integers denoting N, C and k
For each test cases, C lines follow, denoting the ranges within which the children can enjoy cakes.
Each line containing either “GOOD” or “BAD” , as applicable.
5 2 0
5 2 1
5 2 1
In the second test case, the child at [2,2] can be moved to [1,1] so that there are no fights anymore. Also, note that the child can still enjoy 1 cake as he would have done, had his position not been ‘moved’.
Problem 2: IMPORTANT STRINGS
After having cakes at the birthday, you’ve got to study some English.
You may feel strings are a random collection of characters, but no they are important, and this is how.
Suppose you have a string S of length N consisting of X, Y, and Z .
A string is ‘good’ if it starts with a ‘X‘ , ends with a ‘Z‘ and has a length divisible by 3. ( That is permissible lengths are 3, 6, 9….and so on )
The importance of a string is the number of good string it intersects with.
Given the string S and a length k, find a string of length exactly k and minimize it’s importance.
Your job is to print the minimum importance.
The first line contains a single integer t, denoting the number of test cases.
Each test case contains two lines.
The first line of each test case contains two space separated integers denoting N and k.
The second line of each test case contains the string S.
Each line contains a single integer denoting the required minimum importance.
X Y Z Z Y X X Y Z
Y X Y Z
In the first testcase, the good strings are in the ranges [0,2] [0,8] and [6,8]. ( 0-based indexing has been used )
Now consider the string at [5,8]. It is of length k=3. It intersects with only one good string [0,8] ; ( the entire one ).
That’s the best we can do. So it has importance 1, and that’s our desired output.
You may visit this link to see the solutions:- https://www.cheenta.com/zonal-computing-olympiad-2018-solutions-i/