Extremum Permutations
Extremum Permutations
+ 0 comments In order to solve this problem, first you need to know how to use dp to solve permuation problem. ex: N=3, dp[i][j], i means total numbers, j means last element. (j<=i) dp[1][1] = 1 //1 dp[2][1] = sum(dp[1]); //(1) 1 => 2 1 (replace 1 with 2) dp[2][2] = sum(dp[1]); //1 2 dp[3][1] = sum(dp[2]); //2 (1) 1 => 2 3 1 (replace 1 with 3) //(1) 2 1 => 3 2 1 (replace 1 with 3) dp[3][2] = sum(dp[2]); //(2) 1 2 => 3 1 2 (replace 2 with 3) //1 (2) 2 => 1 3 2 (replace 2 with 3) dp[3][3] = sum(dp[2]); //2 1 3 //1 2 3 total permutation is sum(dp[3]) = 6. Now we need to think about constraints a and b. We can define as following: a(i)=1 as a has ith position element b(i)=1 as b has ith position element. There are total three situations for dp[i][j]: if a(i) == 1 or b(i-1) == 1 (include only bigger sets) sum(dp[i-1][j] + dp[i-1][j+1] ... dp[i-1][i-1]) else if b(i) == 1 or a(i-1) == 1 (include only smaller sets) sum(dp[i-1][1] + dp[i-1][2] ... dp[i-1][j-1]) else sum(dp[i-1]) Ex: N = 4 a1 = 2 and b1 = 3. The 5 permutations of {1,2,3,4} that satisfy the condition are 2 1 4 3 3 2 4 1 4 2 3 1 3 1 4 2 4 1 3 2 dp[1][1] = 1 //1 -------------------------------------------------------------- a(2) = 1 dp[2][2] = 0 //j=2, no bigger sets dp[2][1] = dp[1][1] //(1) 1 => 2 1 --------------------------------------------------------------- b(3) = 1 dp[3][3] = dp[2][2] //0 + dp[2][1] //2 1 3 dp[3][2] = dp[2][1] //(2) 1 2 => 3 1 2 dp[3][1] = 0 //j=1, no smaller sets --------------------------------------------------------------- b(3) = 1 dp[4][4] = 0 //j=4, no bigger sets dp[4][3] = dp[3][3] //2 1 (3) 3 => 2 1 4 3 dp[4][2] = dp[3][3] //(2) 1 3 2 => 4 1 3 2 +dp[3][2] //3 1 (2) 2 => 3 1 4 2 dp[4][1] = dp[3][3] //2 (1) 3 1 => 2 4 3 1 => 4 2 3 1 +dp[3][2] //3 (1) 2 1 => 3 4 2 1 => 3 2 4 1 +dp[3][1] //0 You may realize we can always change order of dp[i-1], because total permutation doesn't change. ex: 2 1 3, we have relationship 2 > 1 < 3 after change to 2 4 3, we can always have same relationship 4 > 2 < 3. result sum(dp[4]) = 5
+ 1 comment The explanation for sample 0 does not make sense to me. Other than I believe that the element in position 2 should be the smaller and the element in position 3 should be the larger according to how I read the rules I am also confused when the condition was placed on position 0 that it had to be greater than positon 1. If someone can help me understand the rules this looks interesting to solve.
+ 1 comment Please some one correct me if i am wrong Test case 1 4 1 1 2 3
so adjacent side of 2 must be bigger and adjacent side of 3 must be smaller
Given Examples
2 1 4 3 --- adjacent of 3 is 4 which is bigger than 3. 3 2 4 1 --- this one okay. 4 2 3 1 --- this one also okay. 3 1 4 2 --- this one also okay. 4 1 3 2 --- this one also okay.
how about
2413 3241 4231 1423 1324 3142
6 sets
+ 4 comments Hello. Can someone review the editorial and add some details please? Because right now it is skipping some steps. I personally don't understand it.
First of all, I don't understand the expression: dp[i + 1][k][<] += dp[i][j][>] . What is k and what is j in this expression? Second of all, I don't understand how we can reduce the complexity from O(n^3) to O(n^2), but that is probably because I don't understand the first expression.
Also, the code submitted by the tester seems more elegant. Can someone explain that as well ?
Thank You !
+ 0 comments My code generates permutations in a recursive way. While a new element is being added to the current permutation, my code checks whether it complients or not to the rules. As far 4 testcases are green, the others got timeout. I don't know how could I fast up my solution. As I see I cannot share my solution here anymore. There is some regulation here.
Sort 13 Discussions, By:
Please Login in order to post a comment