B. Petr and Permutations is really very very nice problem xD.
1 Like
I have also implemented the same logic in the contest, but i don’t know about the next_permutation(), so i have got a implementation and used it in my code, i am pretty sure that it works, but the problem is i don’t know for which test-cases my code is failing. Can someone please help!
My code is: CodeChef: Practical coding for everyone
Hello everyone, please help me. I am at my wit’s end trying to figure out which test case is failing. I tried both the next_permutation as well as the Heap’s algorithm to generate the permutation and have used the check function as per the editorial. The function is checkArray. If anyone can point out the issue, I’ll be very grateful. I have tried every possible test case I can think of.
Didn’t know about that STL function. So I wrote Full Heap Algorithm! Well, nice to know a function like that exists in C++ STL.
Thanks @vijju123
1 Like
My Approach -
P.S. (xD) - Yesterday I was reading CP 3 by Steven & Felix Ch 3 And Question was 8 Queens Chess Problem and was going through the techniques of generating all 8! permutations in 1 sec.
Spoiler Alert - Bitwise Operations Are much much faster.
My approach - (Similar to Tester but didn’t used DP). My Sol 18925778 .
I used recursion to generate. And *** (val & ( 1 < < j))==0 *** To check if no j is present in Current Array.
val is Bitwise OR of 2^no of all characters present in array except zeros. And during generating all permutations only I have checked all conditions. And returned count of answers. I also stopped generating all next permutations if filling further places result in no soln.
P.P.S. - I yesterday learnt that next_permutation fn exist in STL but I didn’t strike me during contest xD.
1 Like
why appling next_permutation on whole set of no just do it for no which are missing .
check my sol here CodeChef: Practical coding for everyone
5 Likes
Use next permutation in a do- while loop and try.
@vijju123, thanks for the response. Yes I understood, that the first permutation was being excluded. But after correcting that I found something strange. The author’s code is giving a different output than expected.
For TC -
2 1
1 2
The output should be 0, author’s code is giving 1.
For TC -
2 1
2 1
I feel the output should be 1, author’s code is giving 0.
Please help me understand if I am misinterpreting the question somewhere.
Here’s my revised submission.
2 1 1 2 is an Invalid input. Because 1<=2<=n does not hold.
2 1 2 1 output 0 is correct. There does not exist any i in range 1<i<=n.
1 Like
Yes, I will. Thing is, none of the links are there working when I write them (as problems arent moved to contest page) so I have to “guess” them xD.
Lot to do today. Add TC in test case bank, fix tags. fix links xD
1 Like
Well xD. Because completely mechanic brute force has less chances of wrong logic.
Your logic cant be wrong if its just doing what the question says *insert meme here*
Great! But yes, make sure you know STL as quicker submissions are heavily rewarded at codechef.
1 Like
I am glad it helped you 
I think you misinterpretted the question @ruddradev. Try checking the comments at question page for clarifications.
To everybody having trouble debugging, the test cases are added in test case bank. Please have a look and try to debug now!
Thanks again. It was really silly of me. :). I finally was able to make a correct submission.
1 Like