BSHUFFLE - Editorial

data-structures
hashing
implementation
probability
sept18
simulation

#1

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

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

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.

Click to view
    while(times--)
	{
	    for(i=0;i<n;i++)arr*=i+1;//Initialize arr={1,2,3,...,N}
	    for(i=0;i<n;i++)
	    {
	        j=rand()%n;//Generate a random index from [0,N-1]. 
            //Note that array uses 0-based indexing.
	        swap(arr*,arr[j]);//Swap them. We used std::swap here.
	    }
	    
	}

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

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

Click to view
/*
 *
 ********************************************************************************************
 * AUTHOR : Vijju123                                                                        *
 * Language: C++14                                                                          *
 * Purpose: -                                                                               *
 * IDE used: Codechef IDE.                                                                  *
 ********************************************************************************************
 *
 Comments will be included in practice problems if it helps ^^
 */
 
 
 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

 
int main() {
	// your code goes here
	#ifdef JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	srand(time(NULL));
	auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
    std::mt19937 mt(seed);//random number generator.
	int n;
	cin>>n;
	int times=2000000;//We repeat it 2*10^6 times.
	map<vector<int>,int> mp;//map to count frequency of vector.
	vector<int>arr(n);
	int i,j;
	while(times--)
	{
	    for(i=0;i<n;i++)arr*=i+1;//As shown in editorial.
	    for(i=0;i<n;i++)
	    {
	        j=mt()%n;
	        swap(arr*,arr[j]);
	    }
	    mp[arr]++;
	}
	vector<int> maxi,mini;
	int maxans=0000000,minans=10000000;
	for(auto i:mp)//Find max and min permutations.
	{
	    if(i.second>maxans)
	    {
	        maxans=i.second;
	        maxi=i.first;
	    }
	    if(i.second<minans)
	    {
	        minans=i.second;
	        mini=i.first;
	    }
	}
	for(int i:maxi)cout<<i<<" ";cout<<endl;//print the permutations.
	for(int i:mini)cout<<i<<" ";cout<<endl;
	return 0;
}

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-

Click to view
for(int i=1;i<n;i++)//Set p2
    	p2*=i;
    p2[0]=n;//p2 Done.
	for(int i=0;i<n;i++)//Now find p1
	{
	    if(i<n/2-(n%2==0))
	    	p1*=i+2;
	    else if(i==n/2-(n%2==0))
	    	p1*=1;
	    else if(i!=n-1)
	    	p1*=i+2;
	    else 
	    	p1*=n/2+2-(n%2==0);//You can come up with your own custom implementation
	    	//to find p1. 
	}

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

Setter

Tester

Editorialist

Click to view
/*
 *
 ********************************************************************************************
 * AUTHOR : Vijju123                                                                        *
 * Language: C++14                                                                          *
 * Purpose: -                                                                               *
 * IDE used: Codechef IDE.                                                                  *
 ********************************************************************************************
 *
 Comments will be included in practice problems if it helps ^^
 */
 
 
 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
 
 
int main() {
	// your code goes here
	#ifdef JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	srand(time(NULL));
	int n;
	cin>>n;
	int p1[n],p2[n];
	for(int i=0;i<n;i++)
		p1*=p2*=i+1;//Initialize permutations.
    for(int i=1;i<n;i++)//Set p2
    	p2*=i;
    p2[0]=n;//p2 Done.
	for(int i=0;i<n;i++)//Now find p1
	{
	    if(i<n/2-(n%2==0))
	    	p1*=i+2;
	    else if(i==n/2-(n%2==0))
	    	p1*=1;
	    else if(i!=n-1)
	    	p1*=i+2;
	    else 
	    	p1*=n/2+2-(n%2==0);//You can come up with your own custom implementation
	    	//to find p1. 
	}
	for(int i=0;i<n;i++)
		cout<<p1*<<" ";cout<<endl;
	for(int i=0;i<n;i++)
		cout<<p2*<<" ";cout<<endl;
	return 0;
}  

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

CHEF VIJJU’S CORNER :smiley:

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 :frowning:
  • 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 :slight_smile:

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

3. Unordered map +Strings simulator.

Click to view
/*
 *
 ********************************************************************************************
 * AUTHOR : Vijju123                                                                        *
 * Language: C++14                                                                          *
 * Purpose: -                                                                               *
 * IDE used: Codechef IDE.                                                                  *
 ********************************************************************************************
 *
 Comments will be included in practice problems if it helps ^^
 */
 
 
 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

 
int main() {
	// your code goes here
	#ifdef JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());//random number generator
	//with high precision clock :)
	int n=7;
	cin>>n;
	int arr[n];
	int times=700000;//Simulate 7*10^5 times
	unordered_map<string,int>mp;
	mp.reserve(1024);
    mp.max_load_factor(0.125);
    int i,j;
    string s;
	while(times--)
	{
	    for(i=0;i<n;i++)arr*=i+1;
	    for(i=0;i<n;i++)
	    {
    	    j=rng()%n;
    	    swap(arr*,arr[j]);
	    }
	    s="";
	    for(i=0;i<n;i++)
	        s+=arr*;//String will be made of ASCII characters whose value is represented by
	    //arr*. Eg, if arr* is 5 and in ASCII table 5 is number of char '^', then '^' is added to string.
	    //Note, DO NOT use s=s+arr*. Google out why :)
	    mp[s]++;
	}
	//vector<pair<int,string>>ans;
	string maxians,minians;
	int maxi=0,mini=100000000;
	for(auto i:mp)
	{
	    if(i.second>maxi)
	    {
	        maxi=i.second;
	        maxians=i.first;
	    }
	    if(i.second<mini)
	    {
	        mini=i.second;
	        minians=i.first;
	    }
	}
	for(auto i:maxians)cout<<(int)i<<" ";cout<<endl;
	for(auto i:minians)cout<<(int)i<<" ";cout<<endl;
	
	return 0;
}

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

Click to view

P(M): "M, 1, 2, 3, …, M - 1 is the least likely permutation and occurs 2^{M-1} times out of M^M cases."

We can prove it by induction.

Base case P(5): we’ve used the simulation and found out that {5, 1, 2, 3, 4} occurs 2^4 times out of 5^5 :))

Inductive step: Suppose P(N-1) is true, we’ll prove P(N) (N > 5)

The only configurations which work are the ones in which N is placed on the first position during the N-th swap or the ones in which 1 is placed on the N-th position during the first swap.

To see why this is, let’s say this doesn’t happen. Then suppose that at some point in time i (2 \le i \le N - 1) we’ll swap 1 with i. Now the only way to get 1 to the N-th position is if we swap N with i, but that won’t bring N to the first position. The same applies for the other case.

For the first case, we’ll reduce the configurations to the former step by cutting N from the tail of the permutation. Now apply the induction hypothesis, find out that N - 1, 1, 2, \dots, N - 2 is the least likely, append N to the end and perform the swap between N and 1. These are 2^{N - 2} configurations.

For the second case, we’ll perform the swap and end up with the permutation [N, 2, 3, ..., N - 1, 1]. Cut N from the head of the list and apply the induction hypothesis on [2, 3, ..., N-1, 1]. This is a list of N - 1 elements and we’ll compute its composition with [N - 1, 1, 2, 3, ..., N - 2] and get [1, 2, 3, ..., N - 1]. Now push N back to the head of the list. These are also 2^{N - 2} configurations.

In total we have 2^{N - 1} configurations so P(N) is true.

5. Related Problems-


#2

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.


#3

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…


#4

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


#5

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.


#6

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


#7

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=9 produces a result in ten seconds or so. n=10 is a couple of minutes.


#8

https://ideone.com/nDMZqR


#9

@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


#10

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


#11

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


#12

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


#13

We are computer programmers, not math scientists!

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


#14

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

https://ide.geeksforgeeks.org/WRW58BPbrv


#15

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


#16

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


#17

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


#18

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


#19

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


#20

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