BPS Editorial

PROBLEM LINK:

Practice
Contest

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.

AUTHOR’S AND TESTER’S SOLUTIONS:

AUTHOR’s solution

TESTER’s solution

Editorialist’s solution

Useful addition, the right way to use next_permutation was by making an array with numbers 1…N and then doing it. Using next_permutation directly on the operations array ended up causing problems if the same operation was written 2*X times where X is some integer. Lost about an hour on this bug.

It’s really disappointing that Div1 gets such problems though. I agree I learnt something new but the problem required 0 observations, 0 thinking just coding and hoping for no bugs. Idk about others but I do CP for the love of problem solving, and this contest failed to give that at least for the first 3 problems. Almost seems like it was a very hurried and hence poorly thought out problem set. Don’t mean to criticize and sorry if this was rude, just hoping for higher prob quality :frowning:

4 Likes

I’m trying this solution for a long time.Im not getting why its showing wrong answer.
Any help will be appriciated.

how to solve this question in python because everybody who tried to solve it in python is getting tle.

Yup, I had to sort the operations before applying next permutation.