×

# BPS Editorial

Primary Tester: Amir Reza PoorAkhavan
Editorialist: Hussain Kara Fallah

Easy

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:

TESTER's solution

Editorialist's solution

This question is marked "community wiki".

108830
accept rate: 0%

19.8k350498541

 4 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 :( answered 25 Nov '18, 19:44 365●1●9 accept rate: 0% Yup, I had to sort the operations before applying next permutation. (04 Dec '18, 17:21)
 0 https://ideone.com/9srYgW I'm trying this solution for a long time.Im not getting why its showing wrong answer. Any help will be appriciated. answered 04 Dec '18, 17:12 1 accept rate: 0%
 0 how to solve this question in python because everybody who tried to solve it in python is getting tle. answered 09 Feb, 02:28 0 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×3,746
×56

question asked: 25 Nov '18, 00:48

question was seen: 1,103 times

last updated: 09 Feb, 02:28