We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Extremum Permutations
  5. Discussions

Extremum Permutations

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 13 Discussions, By:

votes

Please Login in order to post a comment

  • tycyd
    3 years ago+ 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
    
    3|
    Permalink
  • jalex_schmitz
    5 years ago+ 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.

    3|
    Permalink
  • er_ayashkanta
    4 years ago+ 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

    1|
    Permalink
  • serban300
    8 years ago+ 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 !

    1|
    Permalink
    View more Comments..
  • auxijanos
    2 years ago+ 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.

    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature