** 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:

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.

Sir can you please post the code for the above problem

Can u please provide a code to the above problem.