PROBLEM LINK:
Author: Hasan Jaddouh
Primary Tester: Amir Reza PoorAkhavan
Editorialist: Hussain Kara Fallah
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Given an array of N integers and a list of Q operations. Each operation is characterized by 2 integers L,R. Applying this operation means reversing the subarray starting at the L-th element and ending at the R-th element. For all possible orders of the given operations, you need to count how many orders (out of Q!) are valid. An order of the operations is valid if applying the operations one by one results in the same array if we apply the operations in the same order given in the input.
N,Q \leq 9
EXPLANATION:
This problem is solved by checking all possible orders of the operations and applying each one separately and checking the resulting array.
To check all possible orders of the operations, we need to permute the list of operations in all the possible ways (Q!). This can be done easily in C++ with next_permutation function provided in STL (check this link). Checking one particular order can be done by iterating over the operations one by one and applying each with a single loop.
Check the codes for better understanding, as this problem is only translating the statement into code after figuring out how to check all possible permutations. Of course, instead of using the next_permutation function we can handle the problem with some recursive manual algorithm, but next_permutation function saves a lot of code.
For outputting the final answer as an irreducible fraction. Suppose we have A orders valid out of Q!. The final answer would be \frac{A/gcd(A,Q!)}{Q!/gcd(A,Q!)}
Complexity : O(Q! * Q * N) which fits easily.
