RIFFLES - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

Setter: Aryan Agarwala
Tester: Tejas Pandey, Venkata Nikhil Medam
Editorialist: Kanhaiya Mohan

DIFFICULTY:

Easy

PREREQUISITES:

Permutation Cycles

PROBLEM:

For a permutation f of length N (given N is even), a riffle is defined as the permutation g = (f(1), f(3), …, f(N-1), f(2), f(4), …, f(N)).

Given two numbers N and K, find the resultant permutation, when you riffle the identity permutation of length N, K times.

The identity permutation of length N is (1, 2, 3, …, N).

QUICK EXPLANATION:

  • Define the riffle permutation g, such that after one riffle, f(i) \rightarrow f(g(i)).
  • Decompose the identity permutation into disjoint cycles.
  • For any cycle, an edge a \rightarrow b implies that the element at position a moves to position b in one riffle.
  • For a cycle, if an element is present at position cycle[i] initially, then, after K riffles, its position would be cycle[(i + K) \% (cycle\_len)].

EXPLANATION:

Observation

Let us look at some smaller values of N and apply riffles to the corresponding identity permutations.

N = 4

(1, 2, 3, 4) \rightarrow (1, 3, 2, 4) \rightarrow (1, 2, 3, 4)

We get after the identity permutation after 2 riffles.

N = 6

(1, 2, 3, 4, 5, 6) \rightarrow (1, 3, 5, 2, 4, 6) \rightarrow (1, 5, 4, 3, 2, 6) \rightarrow (1, 4, 2, 5, 3, 6) \rightarrow (1, 2, 3, 4, 5, 6)

We get after the identity permutation after 4 riffles.

After a certain number of riffles, we reach the identity permutation again.

Let us look at the journey of a particular element. After each riffle, we can determine its next position based on its current position. After a certain amount of riffles, the element reaches its initial position. Thus, each element moves in a cycle.

Defining the riffle permutation: We know that the riffle permutation is defined as g = (f(1), f(3), …, f(N-1), f(2), f(4), …, f(N)). By observation, we can define this formally as:

  • If i is odd (1 \leq i \leq N), g( (i+1)/2 ) = i.
  • If i is even (1 \leq i \leq N), g( i/2 + N/2) = i.

We decompose the permutation into disjoint cycles and calculate the final position of each element in a particular cycle. An interesting thing to note is that, the number of riffles required to reach back to the identity permutation is nothing but the lcm of all the cycle lengths.

Decomposing the permutation: Iterate over all the elements, if the current element is not visited, we start a cycle from this element. Store all the elements of the current cycle, simultaneously marking them visited.

Let us assume a cycle of length m, as, a_0 \rightarrow a_1 \rightarrow a_2 \rightarrow … \rightarrow a_{m-1} \rightarrow a_0
Suppose, we want to find the final position of the element currently at position a_i (0 \leq i < m) after K riffles. Since the cycle has length m, the element at position i moves to position a_{(i + K) \% m}.

Example

Let us take an example of the identity permutation of length 8, i.e., (1, 2, 3, 4, 5, 6, 7, 8). The riffle for this permutation would be (1, 3, 5, 7, 2, 4, 6, 8).

The disjoint cycles would be:

  • 1 \rightarrow 1
  • 2 \rightarrow 3 \rightarrow 5 \rightarrow 2
  • 4 \rightarrow 7 \rightarrow 6 \rightarrow 4
  • 8 \rightarrow 8

Now suppose an element is initially at position 2 (which is present at index 0 of second cycle). After 10 riffles, the element moves to (0+10) \% 3 = 1, the first index. Here, it refers to the third position.

Alternate solution using Binary Exponentiation
  • Consider the permutation U = (1, 3, 5, …, N-1, 2, 4, …, N).
  • Applying a riffle to permutation f is just f composed with U.
  • Therefore, applying K riffles is f composed with U^K.
  • In this case, f is the identity permutation. Thus, we just want U^K.
  • We can compose permutations in O(N) trivially.
  • Permutation composition is associative, so we can use the binary exponentiation algorithm to find U^K in O(Nlog(N)).

See setter’s solution for implementation details.

TIME COMPLEXITY:

The time complexity is O(N) per test case.

SOLUTION:

Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#include <sys/resource.h>
#define int long long
#define initrand mt19937 mt_rand(time(0));
#define rand mt_rand()
#define MOD 1000000007
#define INF 1000000000
#define mid(l, u) ((l+u)/2)
#define rchild(i) (i*2 + 2)
#define lchild(i) (i*2 + 1)
#define lz lazup(l, u, i);
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
int n;
vector<int> unit;
vector<int> ans;
void riffle(vector<int> a, vector<int> &b){
    vector<int> x;
    for(int i = 0;i<n;i++){
        x.push_back(a[b[i]]);
    }
    b.clear();
    for(int i: x){
        b.push_back(i);
    }
}
void exp(int p){
    if(p==0) return;
    exp(p/2);
    riffle(ans, ans);
    if(p%2){
        riffle(unit, ans);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    cin>>t;
    int sumn = 0;
    assert(1<=t && t<=100);
    while(t--){
        int k;
        cin>>n>>k;
        sumn += n;
        assert(1<=n && n<=3e5);
        assert(1<=sumn && sumn<=3e5);
        assert(1<=k && k<=1e9);
        assert(n%2 == 0);
        
        unit.clear();
        ans.clear();
        for(int i = 0;i<n/2;i++) unit.push_back(i*2);
        for(int i = n/2;i<n;i++) unit.push_back(1 + (i-n/2)*2);
        for(int i =0 ;i<n;i++) ans.push_back(i);
        exp(k);
        for(int i =0 ;i<n;i++) cout<<(ans[i]+1)<<" ";
        cout<<endl;
    }
}
Tester's Solution
#include<bits/stdc++.h>
#pragma GCC optimize ("-O3")
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define double long double
const int N = 3e5 + 5;
int t, n, k, a[N];
int32_t main()
{
    IOS;
    cin >> t;
    while (t--) {
        cin >> n >> k;
        map<int, int> nxt;
        map<int, bool> vis;
        for (int i = 1; i <= n; i++) {
            if (i % 2) {
                nxt[i] = (i + 1) / 2;
            }
            else {
                nxt[i] = (i + n) / 2;
            }
        }
        for (int i = 1; i <= n; i++) {
            if (vis[i]) {
                continue;
            }
            vector<int> cycle;
            int cur = i;
            while (nxt[cur] != i) {
                vis[cur] = true;
                cycle.push_back(cur);
                cur = nxt[cur];
            }
            vis[cur] = true;
            cycle.push_back(cur);
            int cycle_size = cycle.size();
            int rem = k % cycle_size;
            for (int j = 0; j < cycle_size; j++) {
                int val = cycle[j];
                int idx = cycle[(j + rem) % cycle_size];
                a[idx] = val;
            }
        }
        for (int i = 1; i <= n; i++) {
            cout << a[i] << " ";
        }
        cout << endl;
    }
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

#define sync {ios_base ::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define rep(n) for(int i = 0;i<n;i++)
#define rep1(a,b) for(int i = a;i<b;i++)
#define int long long int
#define mod 1000000007

int n, k;

void solve()
{
    cin>>n>>k;
    vector<int> next(n+1, 0);
    vector<int> ans(n+1, 0);
    vector<bool> vis(n+1, false);

    for (int i = 1; i <= n; i++) {
        if(i%2){
            next[i/2 + 1] = i;
        }
        else{
            next[i/2 + n/2] = i;
        }
    }

    for(int i = 1; i<=n; i++){
        if(!vis[i]){
            vector<int> cycle;
            int curr = i;
            vis[curr] = true;
            cycle.push_back(curr);
            while(next[curr] != i){
                curr = next[curr];
                vis[curr] = true;
                cycle.push_back(curr);
            }
            int cycle_len = cycle.size();
            for(int j = 0; j<cycle_len; j++){
                ans[cycle[j]] = cycle[(j+k)%cycle_len];
            }
        }
    }

    for(int i = 1; i<=n; i++){
        cout<<ans[i]<<' ';
    }
}

int32_t main()
{

    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
    
    sync;
    int t = 1;
    cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
    return 0;
}
5 Likes

A Really Nice Problem on Using The Concept Of Cycles in Permutations . We can even generalize the problem with a starting permutation [eg. in this problem it was given [1 , 3 , 5 ,…N] to something else like [1 , N , 2 , N - 1 ,… so on] and a nice property about these permutations is we can find the next element for each element in its respective cycle by just doing a single operation on starting permutation .
Here is my submission : Solution: 55976327 | CodeChef
Also this concept can be utilized to solve another problem which recently appeared in a codeforces round : Problem - C - Codeforces

7 Likes

I struggled a lot while solving the question and also I don’t know if it is the right place to ask the question but if someone could help me figure out what’s wrong with my solution, it would be very helpful.

Consider the test input:

1
38 31
1 Like

I see now, thanks for the help.

1 Like

I used an algorithm with O(n*L) where L is order of cycle and calculated new k with k mod L
thus then using this k to calculate the position of number after k riffles. Link to Solution
This is giving tle because of time being almost square so.
But the concept was very interesting

PS I enjoyed the problem, But the above program is valid for odd one’s too if we can initialize

second = (n/2 + 1) when n is odd
Thus finding the cycle

Also note the longest cycle will be of 2 and always be the order of the permutation as per given constraints

1 Like

I did not read through the editorials in details, but at a high level, looks like my solution was simpler.

I noticed a pattern (independent of cycle size) after creating few examples on paper:

a1 a2 a3 a4 a5 a6 // add 1
a1 a3 a5 a2 a4 a6 // add 2
a1 a5 a4 a3 a2 a6 // add 4
a1 a4 a2 a5 a3 a6 // add 8
a1 a2 a3 a4 a5 a6 // add 16

Notice that, on every row the starting element is always a1 (which is always ‘1’). Now notice that on each row, the next element can be found easily by adding the commented out constant against that row.

The commented out constant is 2^row_num, where row_num starts at 0.

And finally, the sum is actually modulo sum:

next_element = (current_element + (2^row_num) ) % N-1

With above insight, one can easily calculate all elements of Kth riffle - or (K+1)th row :slight_smile:

4 Likes

I had exactly the same thought. it was (Element) + index*(2^n -1) for the i’th element.
The problem is, it wasn’t fast/efficient enough for higher values and went out of range for N=2k and above :frowning:

If someone needs binary exponentiation solution code, you can refer to this and understand the implementation:
My Solution

With more research on permutations and little help from wolfram Mathematica, I found the permutation matrix of the sequence

In above figure bounce or step is exactly 2. This is mathematically beautiful
Mapping with arrows, Now this is for

=> 1 3 5 7 9 2 4 6 8 10

Similarly for power of this sequence or What we call next sequence

=> 1 5 9 4 8 3 7 2 6 10

Bounce is % 9 and notice The steps of next element got bigger i.e. exactly 4 (In figure 4 steps to next element ).

How to 2 is mapped to 8 ( count back 4 elements 1,10,9,8)

Please help me expand this solution

I tried a lot to reduce my time complexity. I even got idea of the solution but it would still get TLE for the last case. Can someone tell me what’s wrong with my solution.

The idea is to use the modulo property even for exponentiation :slight_smile:

In my opinion it was a very nice problem. I had a little different approach I would like to share.

Let’s define our own operation, say reverse_riffle, which goes as follows:
(1,2,3,....,n-1,n) (1,n/2+1,2,n/2+2,....,n/2,n)

Note that this operation is just reverse of original riffle operation so, the length of cycle of riffle operation will be equal to that of reverse_riffle operation.

Let, the length of cycle of original riffle operation be cycle. Which means we effectively only need to apply (K%cycle) riffle operations or in other words, (cycle-K%cycle) reverse_riffle operations.

Ex:
Let, N=6,K=15.
Length of cycle for N=6 is 4. (How to find this is explained further).
For riffle operation, only 15%4 = 3 operations are required:
(1,2,3,4,5,6) (1,3,5,2,4,6)(1,5,4,3,2,6)(1,4,2,5,3,6)
For reverse_riffle operation only 4-15%4=1 operation is required:
(1,2,3,4,5,6) (1,4,2,5,3,6)

It is not hard to see that when we apply reverse_riffle operation once, for every 0 \leq i<n-1
(0-based indexing), i becomes (2*i)%(n-1).
In general, after applying x reverse_riffle operations, i becomes (2^x*i)%(n-1).

Now, all that’s left is to find the length of cycle.

We know that,
(2^{cycle}*i)%(n-1)=i
which implies,
(2^{cycle})%(n-1)=1

Also note that since we are taking modulo (n-1) there can be at most n-1 places for an index to be after some operations. So, 0<cycle<n.
So, we can easily find cycle in O(n).

After that our effective K(K_{e}) will be (cycle-K%cycle) and for every 0 \leq i<n-1,
i(2^{K_{e}}*i)%(n-1)
Finally, a_{n-1} = n.

Overall time complexity: O(n)

Here’s my solution: Code

1 Like

// This is my code it is showing WA on subtask 2 can please someone explain
#include <bits/stdc++.h>

using namespace std;

int main()

{

int t;

cin >> t;

while (t--)

{

    long long int n, k, start = 2, iter = 0, ptr = 2, count = 0, index = 1;

    cin >> n >> k;

    long long int arr[n + 1];

    arr[0] = 0;

    for (int i = 1; i <= n; i += 2)

    {

        arr[i] = index;

        index++;

    }

    for (int i = 2; i <= n; i += 2)

    {

        arr[i] = index;

        index++;

    }

    while (iter != start)

    {

        iter = arr[ptr];

        count++;

        ptr = iter;

    }

    k = k % count;

    cout << 1 << " ";

    long long int ans = 1;

    for (int i = 2; i <= n - 1; i++)

    {

        ans = ans + pow(2, k);

        if (ans > (n - 1))

        {

            if (ans%(n - 1)==0)

            {

                cout << n-1 << " ";

                ans = ans % (n - 1);

            }

            else

            {

                ans = ans % (n - 1);

                cout << ans << " ";

            }

        }

        else

        {

            cout << ans << " ";

        }

    }

    cout << n;

    cout << "\n";

}

}

Consider the test input:

1
60 53