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: