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

×

[June Cook-Off 2k18] Is this a valid algorithm/approach to solve Good Permutations Problem ?

Hello, I was trying to solve the 2nd most solved problem in the June cook-off 2k18 contest, even though I believe my approach is valid however still i would like to seek your review and suggest me any better approach or flaw in my existing approach, I will not be posting entire code but just basic algorithmic idea. My code isn't getting accepted (WA) probably due to side cases, and since I urgently want to know the validity of my approach I'm posting it here.

APPROACH (for the single test case)

  1. input N, K
  2. input an array ARR of size N
  3. scan the ARR for 0s and create another array "indices" that will store index i , where ARR[i] is 0
  4. replace 0s in ARR by unused numbers ( for example [2,0,0] becomes [2,1,3] ) (I'm not going into detail of how this is done)
  5. Permute the array "ARR" for only those indices where 0 was replaced by another value using the call to the method given below

https://ideone.com/s9eeax

here, in the first ever call to permute, beg = 0 and end = ind.size()-1 where k is mentioned in the problem statement of the question. Time complexity of the permute method is O(N^2 * fact(N))

If in case anyone is interested to check out entire code for further detail, please check this out https://www.codechef.com/viewsolution/18947214

If the algorithm is not clear please do let me know so I can write it more clearly.

asked 19 Jun, 17:16

keshav2010's gravatar image

2★keshav2010
12
accept rate: 0%

edited 19 Jun, 17:25

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:

×473
×294
×178
×100

question asked: 19 Jun, 17:16

question was seen: 92 times

last updated: 19 Jun, 17:25