Zonal Computing Olympiad 2018 Solutions-I

 Here is the part 1 of solutions of Zonal Computing Olympiad 2018 of International Informatics Olympiad  held in Tsukuba, Japan.

Problem 1: BIRTHDAY-CAKES

Before going to the solution/hints, it's always good if you re-read ( assuming you've already encountered the problem ) the problem statement once. And if you aren't aware of the problem statement, then it's only logical that you read it.
In any case, if you need to see the statement of the problem, you can find it here:

Zonal Computing Olympiad 2018 Questions.

Now, let us deal with the cases that constitute the problem. They are precisely k=0 and k=1

Case-I (k=0)
This case is pretty trivial. It can be solved with a bit of thought.
The algorithm we follow for this is:

Take each pair [a,b] denoting the permissible ranges of the cakes which a child can enjoy.
If a!=b, we append elements in range (a,b) { both inclusive } to an empty array declared beforehand.
If a==b, we append only a to the array.
Then we check if the array has any duplicate elements or not.
If it does, we print "BAD" , else we print "GOOD".

Case-II (k=1)
This case can be a lot simplified, the moment we realize the fact that INTERSECTIONS of the permissible ranges in which a child enjoys  cakes can occur only in TWO ways.
ONE way being when the destination ( last element ) of a permissible range, is equal to the source ( first element ) of another permissible range.
{ In terms of interpretation in code, we will have a function dupli_1(arr)  that returns 1 if any two consecutive elements in an array are equal. We will check if we have dupli_1(arr) = 1 for the array that contains all pairs (a,b) appended to it. }
ANOTHER way we can have fights is when an entire permissible range of cakes for some child is CONTAINED in the permissible range of cakes for another child, that is, for eg, the string "6" is 'entirely contained' in the array "567". ( In other words "6" is a substring of "567" ).

{ We use the contiguous substring concept here, and have a function dupli_2(array) that returns 1 if a string in the array is a contiguous substring of any other string in the same array.}
Now if both of the aforementioned functions return 1, we break and output "BAD" immediately, because the question gives us the liberty to move at max one child.
If anyone of those functions return 1, we act accordingly.
If dupli_1(arr)==1, we find out the particular element ; and take the minimum of the lengths of the two strings it occurs in, Assume this length to be g. Let w be the no. of elements, which are IN [1,..9] but NOT IN arr. ( These checks take linear time ).
If w >=g : we print "GOOD" , else we print "BAD"
Alternatively, if dupli_2(array)==1, we take g to be the length of the substring. And the deciding factor stays the same.

Hence, done.

Another approach to k=1:

We find any pair which intersects and let's think them to be i and i+1 and check if we can place i+1 in vacant places without overlaps via brute-force.