You are not logged in. Please login at to post your questions!


BPS Editorial



Author: Hasan Jaddouh
Primary Tester: Amir Reza PoorAkhavan
Editorialist: Hussain Kara Fallah






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$


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 solution

TESTER's solution

Editorialist's solution

This question is marked "community wiki".

asked 25 Nov '18, 00:48

deadwing97's gravatar image

accept rate: 0%

edited 04 Dec '18, 14:14

admin's gravatar image

0★admin ♦♦

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

harrycoda's gravatar image

accept rate: 0%

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

(04 Dec '18, 17:21) vijju123 ♦♦4★

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

ssshauryaa's gravatar image

accept rate: 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

jatin_007's gravatar image

accept rate: 0%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 25 Nov '18, 00:48

question was seen: 1,103 times

last updated: 09 Feb, 02:28