BSHUFFLE - Editorial

general
, , , , ,
21

@vijju123 can you please provide a list of contests in which you have been the editorialist? I really like your editorials.

1 Like
22

I think I served as an editorialist for April and Sept long. I think I did June LTIME and July Cookoff as well apart from that. Thats it pretty much XD

1 Like
23

Related Problem -
2018 Asia Singapore Preliminary Contest - Fooling Around

24

Can you explain your simulator ?

25

The setter has it, but its very complicated and hence its discussion isnt covered by the editorial.

26

Ok. Thanks @vijju123 .

27

Ouch! And to think that 3 people beta reading will surely catch all the typos XD. Thanks dear!

28

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.

29

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.

30

My simulator is explained by @anaphase21 BSHUFFLE - Editorial - #5 by anaphase21 - general - CodeChef Discuss . My code is an implementation of this. Will add explanation by tomorrow :stuck_out_tongue: .

31

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.

32

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
33

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:

34

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.

35

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

36

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
37

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
38

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.

3 Likes
39

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
40

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