**Editorialist:**Swetanjal Dutta

**PREREQUISITES:**

- Basic Counting Principles
- What is a valid bracket sequence?
- (Optional)A basic idea of recursion.

**PROBLEM LINK:**

**LEARNING OUTCOMES:**

- Dynamic Programming problem solving paradigm

**SOLUTION:**

Let us redefine our problem a bit so that it is easier to proceed with the solution.

When the yard manager says **“Enter”**, let us denote it by ‘(‘. Similarly, when the yard manager says “Leave”, let us denote it by ‘)’.

So what will the following instruction sequence look like? Enter,Leave,Enter, Leave.

*Answer: ()()*

Similarly, what will the following instruction sequence look like? Enter, Enter, Leave, Leave.

*Answer: (())*

**Observation #1:**

Each unique instruction sequence will produce a unique arrangement of the trains on the outgoing track.

**Observation #2:**

Observe that an instruction sequence is valid iff it is a valid bracket sequence and between a pair of *‘(‘* and *‘)’* there should not be more than K brackets.

After making the above observations, our problem essentially reduces to count the number of valid bracket sequences of size 2*N such that between no pair of *‘(‘* and *‘)’,* there are more than K brackets.

Looks neat!

Let us first solve part (b) and then part (c). I will leave part (a) as an exercise for the reader.

**Defining the function F:**

Let us denote F[i] as the number of valid bracket sequences of size i.

Our answer will be F[2*N].

**Observation #3:**

F[i]= 0 for all i, i % 2=1

This is because all odd length bracket sequences are invalid.

Figuring out the base cases:

For what values of i can you intuitively tell me the answer of F[i]?

i) What is F[0]?

ii) What is F[2]?

iii) What is F[some negative number]?

F[0] = 1

F[2] = 1

F[some negative number]=0

These are our base cases i.e value (s) of i for which we can trivially/intuitively work out the answers for F[i].

**Figuring out the recursive case:**

This is the most important segment of the whole editorial. If you are exhausted reading this much, go take a 2 minute break and come back fresh!

How to calculate F[i] for any value of i apart from the ones mentioned in the base case?

A crucial observation:

Between a *‘(‘* and *‘)’,* there can be 4 brackets and this 4 bracket sequence must be a valid bracket sequence.

Between a *‘(‘* and *‘)’,* there can also be 2 brackets and this 2 bracket sequence must be a valid bracket sequence.

Between a *‘(‘* and *‘)’,* there can can also be 0 brackets and this 0 bracket sequence must be a valid bracket sequence.

You can clearly understand that between a *‘(‘* and *‘)’,* there can never be odd number of brackets as this odd number bracket sequence can never be valid.

Similarly, between a *‘(‘* and *‘)’,* there cannot be 6 brackets as this would mean more than K(=4) instructions in between a pair of *‘(‘* and *‘)’.*

**Calculating F[i]:**

Let us put a *‘(‘* and *‘)’.*

*( )*

Now, if we put a 4 bracket sequence in between *(* and *)*, how many brackets remain to be put?

*Answer: i-2-4*

Therefore, number of sequences is = F[4] * F[i-2-4]

Now, if we put a 2 bracket sequence in between *(* and *)*, how many brackets remain to be put?

*Answer: i-2-2*

Therefore, number of sequences is = F[2] * F[i-2-2]

Now, if we put a 0 bracket sequence in between *(* and *),* how many brackets remain to be put?

*Answer: i-2-0*

Therefore, number of sequences is = F[0]* F[i-2-0]

So, for any i,

F[i] = (F[0]* F[i-2-0])+ (F[2] * F[i-2-2]) + (F[4] * F[i-2-4])

Great, we have a formula.

**CREATING A TABLE:**

Only job is to create a table holding the values of F[i].

Start filling with F[0], F[1], F[2]...... F[2*N].

We know F[0], F[1], F[2] and F[some negative number].

Other F[i]s can be calculated using the above formula.

CODING IT UP **(Optional):**

Link: https://ideone.com/Pt541w

**ANSWERS:**