BSHUFFLE - Editorial

@vijju123 I was trying to do this question both in Java and Python. Because I was using random function I wasnt getting values with uniform distribution as given in the question. Which random function would give me uniform distribution in Java and Python?

Can you show your simulator code? There can be many reasons why you didnt get the pattern, eg- Number of simulations being insufficient OR N being too small that multiple answers are possible etc.

https://www.codechef.com/viewsolution/20235348

I am getting different permutations every time having min and max frequency. I intentionally submitted wrong code so that i could share my code with you.

My simulator is explained by @anaphase21 https://discuss.codechef.com/questions/135048/bshuffle-editorial/135520 . My code is an implementation of this. Will add explanation by tomorrow :stuck_out_tongue: .

We are computer programmers, not math scientists!

Guessing patterns from few first cases is neither science nor programming. This is a low quality problem.

The proof for larger numbers for the most likely permutation is given in the research paper attached in point 2. For the least likely permutation, setter’s proof is given in point 4.

That’s because for n > 17, the most likely permutation doesn’t follow the same pattern as for n \leq 17. It is the identity permutation (1,2,3, ... n) that is most likely to occur for n > 17. The least likely permutation, however, follows the same pattern even for greater values of n.

1 Like

Yup, I gave further reading for interested ones. If you can get those and explain them, you’re always welcome to grab those karma/reputation points :slight_smile:

Your level of maths is poor thats why you resort to simulation. Else derive it during contest, no one stopped you. :slight_smile:

Guessing patterns from few first cases is neither science nor programming.

Get more exposure.

I want to know how u checked for n>=10

I agree with @ygj_kurwa it’s very disappointing to see problems which can be solved without any intuition at all…these kind of problem are not gonna be help in the future in any manner…I saw people wasting hours to simulate the program and find the pattern in the answer…even it is the same case with tabgame but still it has some logic behind it’s pattern…but it’s even more disappointing to see people like @vijju123 to insult someone simply because you always defend codechef it’s policy and what not…have some sense pls…be grown up.

3 Likes

@aryanc403,
I submitted “Fooling Around” problem but it is showing wrong answer ,could you please check my code
thanks.

https://ide.geeksforgeeks.org/WRW58BPbrv

Well, I couldn’t, and didn’t need to. My limit was N = 8.
I tried N = 9 and it took me a couple of minutes, and finally a StackOverflow (which I already anticipated).
I recognized a pattern after my first 8, and generated the rest of the permutations by hand.

1 Like

Now this doesn’t make sense. Saying that guessing is neither science nor programming is not an accurate statement. Even mathematicians would sometimes resort to conjectures and guessing at the very initial stages of their works, working all the way to obtain elegant solutions. You probably aren’t aware of all the trial and error they go through. It’s not all problems that can be solved rigorously just like that. Many great mathematicians in the past have made conjectures which were latter disproved by people who were equipped with better tools. Educated guesses are a part of science.

2 Likes

Its your personal opinion when you call such problems poor, you need not disrespect things like that.

these kind of problem are not gonna be help in the future in any manner

Guess what? Same holds for that persistent segment tree problem - you aint using that in real life. Or other 80\% problems of competitive coding. I hope this makes you realize that the argument is completely invalid.

Be mature enough to understand that such ranting is uncalled for. You are welcome to give your opinion, but not at all welcome to bash your opinion and go on calling it a low quality problem.

1 Like

If you solved it without any intuition at all, good for you. But you should be educated enough to know that we are not all equal - not everyone is as bright as you, to be able to solve this with zero intuition. Pattern recognition involves intuition.

2 Likes

Try for a larger value of N, like N=8. Also, simulations should be at least 10^6 or more. You should get same result when compile and run again and again for same input.

Interesting! I think this fact is worth mentioning in the editorial. It means that observing the pattern, while the solution for the specific constraints, is not the solution for all N as it may sound.

Yes, but its always the editorialists dilemma. I felt mentioning it in editorial will make it feel contradictory, that at one hand editorialist shows a nice simulation solution and then he says its not the answer for all N XD.

@rajput1999 see below for my code that can check n=10 in a couple of minutes. However any such exhaustive approach isn’t going to get all the way to 17.