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

×

BSHUFFLE - Editorial

6
2

PROBLEM LINK:

Div1
Div2
Practice

Setter- Bogdan Ciobanu
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Observation, Simulation, Probability, Implementation and Data Structures - namely vectors and unordered maps/HashMaps/Hash tables, Hashing, Logic and Knack of Programming.

PROBLEM:

Given a value $N$ and an algorithm in the statement, find the most and least probable permutation of $N$ which the given algorithm can generate.

QUICK-EXPLANATION:

Key to AC- Simulating the algorithm for small $N$ huge number of times, and observing pattern for different values of $N$ led to an easy AC

This type of question must be specially handled. Write a brute force program which would simulate the algorithm given in the question a large number $(\approx 2*10^6)$ times. Observe the pattern for various values of $N$. You'd observe the following pattern-

Maximum Possible Permutation- $[2,3,4,\dots ,\lceil \frac{N}{2} \rceil,1,\lceil \frac{N}{2} \rceil+1,\lceil \frac{N}{2} \rceil+2, \dots, N$

Here $\lceil \frac{N}{2} \rceil$ represents $\frac{N}{2}$ rounded up to nearest integer (if decimal).

Least Possible Permutation- $[N,1,2,3,\dots,N-1]$

EXPLANATION:

I had been eternally waiting for such type of a question to come on codechef :) . The beauty of such a problem is, that you HAVE to think out of the box. The typical way of "making a program which would do all computations and simulations quickly with Time limit of the question and get AC" doesnt work, and this causes lot of contestants to go puzzled on what to do.

Lets first discuss about these questions in general and then use the conclusion to solve this problem. Editorial is divided into $3$ parts, the beginning one is a just a short note on how and why we came to use the given approach, second tells details about how to make simulator, and third is final answer.

Editorialist's Solution-

1. Why Simulation?-

Lets begin it by discussing about first subtask. $N \le 7$, which seems strange to contestants. Too large to make cases by hand and see/print the handwritten result, and still too "small" for some reason, (perhaps too small to make a dp table to find the answer).

Turns out, there is a method for which this value is "just-fine" :). That method is Simulation!

Usually, for these type of questions, the math required is too high. We are computer programmers, not math scientists! (No offence intended for anyone who is a computer programmer AND math scientist). The first principle of computer programming is, "Let the Machine do things for you :)". But anyways, I have attached a research paper which might help you guys get an insight on the question, the link is in my bonus corner as usual :)

Honestly though, after trying and brainstorming for a few attempts, we cannot come at any link/conclusion which would help us decipher this mathematical mystery. While its easy to see how many possibilities are there, its not intuitive to count how probable they are, except from the few which are impossible (if any). Also, we are to answer it with respect to the algorithm given in the question. Usually, it does good to first study and observe the behavior of the algorithm.

So, lets first discuss how to write the simulator :)

2. Writing Simulator-

A knowledge of Data Structures is needed. Go through links in pre-requisites if you dont know about vectors (dynamic arrays) and unordered_map (Hashmap/Hashtable).

The first thing to do is, to decide how many times we must simulate. This value is derived experimentally. Ideally, the value should be such that-

  • Its small enough so that simulation finishes within reasonable time.
  • Its large enough to give a stable answer. Meaning, irrespective of number of times I compile the same code again with same inputs, the answer permutation must be in the output, with no wrong permutation.

Once that is done, all we have to do is to copy the algorithm given in the question. A C++ implementation is given below, its simply converting the pseudocode given in question to your language.

View Content

Now, comes the tricky part. After doing above, we got a permutation, but how do we count a permutation's frequency?!

There are multiple ways to get over it :). Some of them are-

  • Use vector and maps. map can be used to even count frequency of vectors! Just use map< vector<int>,int> in declaration to suggest that you want to count frequency of vector (i.e. dynamic array or permutation)!
  • Use lexicographically ordering as index. Eg, assign 1 to lexicographically smallest permutation, then 2 to next largest, and so on. But this method is really not recommended.
  • Use hashing! Hash the permutation to some integer and count its frequency. But make sure there are absolutely no collisions!! Or..find a way to handle them!

Once we get that, simply print the permutations appearing maximum and minimal number of times. A sample code is shown below. I used vectors and maps, the easy way out XD. However, my original/alternate simulation used unordered map and string, which is given in bonus corner :). You can also find some tips in my bonus corner for simulator :)

Remember that, the simulation in the program must go for sufficiently large number of times, and you must run simulator to check even same value of $N$ multiple times. If the answer is stable, then number of simulations is sufficiently good for that value of $N$ (note that more simulations are needed to get an accurate result as $N$ increases), else try increasing it more. :)

View Content

3. Concluding notes and final answer-

Now once you find a set of candidate permutations, try to find a pattern on how to generate them. The permutations which I found were of patter as shown in quick explanation-

Maximum Possible Permutation- $[2,3,4,\dots ,\lceil \frac{N}{2} \rceil,1,\lceil \frac{N}{2} \rceil+1,\lceil \frac{N}{2} \rceil+2, \dots, N$

Here $\lceil \frac{N}{2} \rceil$ represents $\frac{N}{2}$ rounded up to nearest integer (if decimal).

Least Possible Permutation- $[N,1,2,3,\dots,N-1]$

You can refer to my code on how to generate it, although this type of implementation is trivial :).

My code for generation-

View Content

SOLUTION

The solutions are given in tab below in case the links dont work. This is done as to avoid any delay in solutions being accessbile to you guys. Copy them to your favorite editor and give a read :)

Setter

Tester

Editorialist

View Content

$Time$ $Complexity=O(N)$
$Space$ $Complexity=O(N)$

CHEF VIJJU'S CORNER :D

1. Some tips on simulator-

  • Unordered map in C++ doesnt by default support vector! You need to make your own function for that. An easy fix is, convert the permutation into a string of characters, (the characters need not be necessary '0'-'9', eg - we can represent '0' by '/' in string, 10 by 'p' etc. Any character of your choice). Since all permutations are unique, the strings they map to are also unique, and hence can be used with unordered map :). We can count frequency of strings, cant we?
  • Unordered map, with proper allocation (reserve and fill size reconfiguration as told here ) works in $O(1)$ while map works in $O(LogN)$. But map directly supports vectors, while unordered map does not :(
  • Avoid any memory declaration inside simulation loop. This can potentially speed up your code a HUGE fraction, because constantly allocating small memory numerous times is very expensive. My runtime went from $8$ to $3.57$ seconds after this :)

2. Research paper link - https://arxiv.org/pdf/math/0010066.pdf

3. Unordered map +Strings simulator.

View Content

4. Setter's proof on least-likelihood permutation-

View Content

5. Related Problems-
- Roman Digits - Make a brute force and finding pattern is key to AC!!
- Fooling Around

asked 08 Sep '18, 19:35

vijju123's gravatar image

5★vijju123 ♦♦
15.5k12066
accept rate: 18%

edited 17 Feb, 20:33

to find the permutation p2, one can just do left cyclic shift of original array p and then swap(p[n/2],p[n]) and you are done!!. here is the link..https://www.codechef.com/viewsolution/20106025

(18 Sep '18, 13:59) ankit00384★

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

(18 Sep '18, 16:45) the_extractor4★
2

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

(18 Sep '18, 18:59) vijju123 ♦♦5★

Related Problem -
2018 Asia Singapore Preliminary Contest - Fooling Around

(18 Sep '18, 19:40) aryanc4035★

Knuth Fisher-Yates Algorithm is worth mentioning.

(22 Sep '18, 00:15) vjvjain05★

(N.B. I'm assuming that the original task (wrongly) assumed that the pattern continued indefinitely based on initial observations. The editorial seems to suggest that the pattern would continue, and the setter's solution isn't correct for $n>17$ either. If so, vijju123 links to a nice paper proving the initial task wrong.)

I have to say, I'm not too impressed how this problem made it into a competition without having any guarantees for correctness. From what I understand the original motivation was an appeal to pattern recognition that actually turned out to be wrong.

This whole thing actually highlights a very important takeaway: pattern recognition by itself is not a proof! For contrast TABGAME has a similar theme of pattern recognition, but in that case the pattern can be easily be shown to be general.

If the task would had been to print only the least likely configuration (which you have a proof for) that would have been perfectly fine, and actually quite a nice task.

link

answered 20 Sep '18, 04:10

algmyr's gravatar image

7★algmyr
1.2k13
accept rate: 37%

How can we say that the proof by setter is correct? It just proves that the number of permutations for the least likely is ${2}^{N-1}$ but there is no proof that it would be the least number?

(22 Sep '18, 19:13) error_503_4042★

The proof states that it proves "... is the least likely permutation and occurs $2^{M−1}$ times" however I think it only shows the later. Still you could do a similar induction proof to show that all permutations occur $\ge 2^{M-1}$.

(23 Sep '18, 04:24) gorre_morre7★

You can also "simulate" the problem without random number generation. How I simulated this was by recursively swaping each number by the rest of the n-1 numbers. I did this up to N = 8, then observed the pattern by printing first five permutations, and last five permutations.

Example: 1 2 3

  1. First swap 1 and 1 => 1 2 3
  2. Secondly swap 1 and 2 => 2 1 3
  3. Thirdly swap 1 and 3 => 3 2 1

The next number will produce N^2 permutations; the third will produce N^3. Thus, by the end of the recursion, you have N^N permutations distributed among N! distinct permutations. Now each of the first three permutations will apply the above steps by using the next number to swap with the others until we get to last number. The least probable permutation looked very obvious. But for the most probable, when I looked at the pattern for the most probable permutations, I wasn't sure if my observation was right, so I manually hard-coded my most probable permutations up to N = 17 to see if my solution would pass. Indeed, it did pass, unfortunately I decided to move to next problem without modifying my code. I feel my solution (hardcoding) was a terrible one.

link

answered 18 Sep '18, 17:17

anaphase21's gravatar image

3★anaphase21
513
accept rate: 100%

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

(19 Sep '18, 19:23) rajput19995★
1

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.

(19 Sep '18, 19:54) anaphase213★

@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.

(19 Sep '18, 21:28) joffan5★

thx joffan for your answer

and yeah I also got till N = 8 and then recognized the pattern

however I was curious whether we can go till N = 17 or above

(20 Sep '18, 17:28) rajput19995★

For N up to 7 I found the answer by brute force of all possible combinations.

For higher numbers, I spotted the pattern and guessed that it would continue.

The way that submissions are marked, there is no requirement for a proof that the answer is correct, and no penalty for a wrong answer. So it is reasonable to make a guess and submit it. It may not be good programming, but it earns the points.

You can see my solution here at https://www.codechef.com/viewsolution/20130095

link

answered 25 Sep '18, 08:09

david_s's gravatar image

4★david_s
1111
accept rate: 10%

If your google search game was strong, you could have found the hint here :)

link

answered 18 Sep '18, 18:39

udayan14's gravatar image

3★udayan14
864
accept rate: 0%

@vijju123 you have mistaken in Maximum Possible Permutation- $2,3,4,…,⌈\frac N 2⌉,1,⌈\frac N 2⌉+1,⌈\frac N 2⌉+2,…,N$
it should be $2,3,4,…,⌈\frac N 2⌉,1,⌈\frac N 2⌉+2,…,N,⌈\frac N 2⌉+1$
Seems like typo but it's misleading.

link
This answer is marked "community wiki".

answered 19 Sep '18, 02:42

vichitr's gravatar image

5★vichitr
2655
accept rate: 11%

wikified 22 Oct '18, 16:38

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

(19 Sep '18, 09:51) vijju123 ♦♦5★

My simulator. It is probability independent. Maybe using the keyword simulator is a bad idea. It goes through all $n^n$ permutations and then finds min and max.

link

answered 18 Sep '18, 14:31

aryanc403's gravatar image

5★aryanc403
2.7k1618
accept rate: 10%

edited 18 Sep '18, 14:32

Can you explain your simulator ?

(18 Sep '18, 21:07) tihorsharma1232★

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 :P .

(19 Sep '18, 11:48) aryanc4035★

Does using rand() function in C++ to generate random integers make any difference here? Because I was using it and I was storing frequencies of permutations as string in STL unordered_map but couldn't find a particular pattern...

link

answered 18 Sep '18, 14:57

pant0000's gravatar image

4★pant0000
1114
accept rate: 10%

You need to initialize seed in srand so that numbers are different everytime, else same sequence is generated. Also, make sure number of simulations are sufficient for that value of $N$

(18 Sep '18, 15:03) vijju123 ♦♦5★

Nice proof by the setter for the least likely permutation. Thanks @bciobanu for this wonderful problem.

link

answered 18 Sep '18, 16:40

the_extractor's gravatar image

4★the_extractor
1627
accept rate: 10%

It's fairly easy in Python, at least, to produce the entire distribution up to n=8 - $8!$ is not so large. This only requires that you count the permutations from the previous swaps rather than modifying them one by one. Code for this investigation:

# https://www.codechef.com/SEPT18A/problems/BSHUFFLE investigation
from operator import itemgetter
from collections import defaultdict

lim = int(input())
pdic =  {tuple(i+1 for i in range(lim)):1}
for spos in range(lim): # swap pos
    tdic = defaultdict(int)
    for pm,qy in pdic.items():
        ad = list(pm)
        for tpos in range(lim): # to pos
            ad[tpos], ad[spos] = ad[spos], ad[tpos]
            tdic[tuple(ad)] += qy
            ad[tpos], ad[spos] = ad[spos], ad[tpos]
    pdic = tdic

plist = sorted(pdic.items(), key=itemgetter(1))

print(*plist[:3], *plist[-3:], sep = '\n')

n=9 produces a result in ten seconds or so. n=10 is a couple of minutes.

link

answered 18 Sep '18, 19:07

joffan's gravatar image

5★joffan
9488
accept rate: 13%

edited 18 Sep '18, 20:21

link

answered 18 Sep '18, 22:56

mr_dot_convict's gravatar image

3★mr_dot_convict
1
accept rate: 0%

@bciobanu Hey did you created this question just by checking this solution for smaller numbers? I mean do you have proof for the larger number? Thank you

link

answered 19 Sep '18, 00:24

nik_84's gravatar image

5★nik_84
537
accept rate: 0%

edited 19 Sep '18, 00:30

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

(19 Sep '18, 01:23) vijju123 ♦♦5★

Ok. Thanks @vijju123 .

(19 Sep '18, 05:14) nik_845★

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.

(19 Sep '18, 15:21) the_extractor4★

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 :)

(19 Sep '18, 15:54) vijju123 ♦♦5★

Just curious, why the upper bound was lowered from 100 to 17?

link

answered 19 Sep '18, 02:20

shoom's gravatar image

6★shoom
3534
accept rate: 30%

1

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$.

(19 Sep '18, 15:35) the_extractor4★

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.

(19 Sep '18, 20:53) shoom6★

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.

(19 Sep '18, 21:16) vijju123 ♦♦5★

@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?

link

answered 19 Sep '18, 10:20

kunal12's gravatar image

3★kunal12
445
accept rate: 0%

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.

(19 Sep '18, 10:34) vijju123 ♦♦5★

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.

(19 Sep '18, 10:58) kunal123★

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.

(19 Sep '18, 20:50) vijju123 ♦♦5★

We are computer programmers, not math scientists!

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

link

answered 19 Sep '18, 14:53

ygj_kurwa's gravatar image

2★ygj_kurwa
1
accept rate: 0%

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

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

Get more exposure.

(19 Sep '18, 16:00) vijju123 ♦♦5★
3

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.

(19 Sep '18, 19:46) byomkeshbakshy5★
2

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.

(19 Sep '18, 20:31) anaphase213★
1

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.

(19 Sep '18, 20:33) vijju123 ♦♦5★
2

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.

(19 Sep '18, 20:41) anaphase213★

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

https://ide.geeksforgeeks.org/WRW58BPbrv

link

answered 19 Sep '18, 19:54

san__123's gravatar image

4★san__123
11
accept rate: 0%

Try these test cases - 1 17 and then 2 11 17

You will be able to figure out how your soln is test cases dependent which should not be the case.

View Content

And do comment if you need more help. :)

(20 Sep '18, 08:09) aryanc4035★

Thanks,I corrected it ,

But with this approach it is showing TLE (time limit exceeded).

https://ide.geeksforgeeks.org/NmdZX8dmYp

help me please .

(20 Sep '18, 18:24) san__1234★

I found the sequence to be 3,8,11,32,35,56,59,64,67,118,121,208,211,216,219,622,625...... here difference betwween two elements is 3 alternatively but difference between other elements is varying . I am unable to figure it out ,please help me

(20 Sep '18, 20:54) san__1234★

I knew that you would get TLE. That is why I wrote comment again xD.
Your approach is correct. Now you will have to optimize it.
Pre Req - Sieve1, Sieve2, Bitset

View Content
(20 Sep '18, 22:17) aryanc4035★

Hi! I used a different pattern but I'm not sure how to prove it's correct or not. I got AC tho.

P1 - N,1,2,3,....,N-1 P2 - swap(all consecutive numbers in the first half) + swap(all consecutive numbers in the second half) https://www.codechef.com/viewsolution/20172571

link

answered 22 Sep '18, 23:11

vss96's gravatar image

2★vss96
11
accept rate: 0%

There are 2 possible permutations for odd n. And one possible permutation for even n.

(22 Sep '18, 23:19) aryanc4035★

The maximum probability permutation in the Editorial is wrong. I didn't get that even for 1 million tests.

link

answered 30 Sep '18, 21:12

manishjoshi394's gravatar image

3★manishjoshi394
1
accept rate: 0%

You can just try go through all possible $n^n$ possible sets of swaps and count the results (up to something like 8 or 9). I can guarantee it's correct up to $n=8$, although it should be noted that for odd $n$ there are two equally likely permutations.

(30 Sep '18, 21:29) algmyr7★
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:

×850
×344
×252
×241
×172
×27

question asked: 08 Sep '18, 19:35

question was seen: 4,904 times

last updated: 17 Feb, 20:33