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

×

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

This question is marked "community wiki".

asked 25 Nov '18, 00:48

deadwing97's gravatar image

3★deadwing97
108830
accept rate: 0%

edited 04 Dec '18, 14:14

admin's gravatar image

0★admin ♦♦
19.8k350498541


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 :(

link

answered 25 Nov '18, 19:44

harrycoda's gravatar image

5★harrycoda
36519
accept rate: 0%

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

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

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.

link

answered 04 Dec '18, 17:12

ssshauryaa's gravatar image

2★ssshauryaa
1
accept rate: 0%

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

link

answered 09 Feb, 02:28

jatin_007's gravatar image

3★jatin_007
0
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×3,746
×56

question asked: 25 Nov '18, 00:48

question was seen: 1,103 times

last updated: 09 Feb, 02:28