PROBLEM LINK:
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.
Click to view
while(times--)
{
for(i=0;i<n;i++)arr[i]=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[i],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
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.
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]=i+1;//As shown in editorial.
for(i=0;i<n;i++)
{
j=mt()%n;
swap(arr[i],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]=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]=i+2;
else if(i==n/2-(n%2==0))
p1[i]=1;
else if(i!=n-1)
p1[i]=i+2;
else
p1[i]=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
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[i]=p2[i]=i+1;//Initialize permutations.
for(int i=1;i<n;i++)//Set p2
p2[i]=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]=i+2;
else if(i==n/2-(n%2==0))
p1[i]=1;
else if(i!=n-1)
p1[i]=i+2;
else
p1[i]=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[i]<<" ";cout<<endl;
for(int i=0;i<n;i++)
cout<<p2[i]<<" ";cout<<endl;
return 0;
}
Time Complexity=O(N)
Space Complexity=O(N)
CHEF VIJJU’S CORNER 
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.
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]=i+1;
for(i=0;i<n;i++)
{
j=rng()%n;
swap(arr[i],arr[j]);
}
s="";
for(i=0;i<n;i++)
s+=arr[i];//String will be made of ASCII characters whose value is represented by
//arr[i]. Eg, if arr[i] is 5 and in ASCII table 5 is number of char '^', then '^' is added to string.
//Note, DO NOT use s=s+arr[i]. 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-
- Roman Digits - Make a brute force and finding pattern is key to AC!!
- Fooling Around