# Chef and Riffles RIFFLES Solution Codechef

## Chef and Riffles RIFFLES Solution

Let f be a permutation of length N, where N is even. The riffle of f is defined to be the permutation g=(f(1),f(3),…,f(N−1),f(2),f(4),…,f(N)). You are given two integers N and K. Output the resultant permutation when you riffle the identity permutation of length N, K times. The identity permutation of length N is σN=(1,2,…,N)

Input Format

• The first line of input contains a single integer T, denoting the number of test cases. The description of T test cases follows.
• Each test case consists of a single line of input, containing two space-separated integers N and K.

Output Format

For each test case, output the answer permutation as N space-separated integers in a new line.

Constraints

• 1≤T≤100
• 1≤N≤3⋅105
• 1≤K≤109
• N is even
• The sum of N across test cases does not exceed 3⋅105

• Subtask 1 (30 points): N is a power of 2
• Subtask 2 (70 points): Original constraints

Sample Input 1

``````3
6 1
8 2
14 452``````

Sample Output 1

``````1 3 5 2 4 6
1 5 2 6 3 7 4 8
1 10 6 2 11 7 3 12 8 4 13 9 5 14``````

Explanation

Test case 1: Performing the riffle on σ6=(1,2,3,4,5,6) once results in (1,3,5,2,4,6), by definition.

Test case 2: The process goes as follows:

• Performing the riffle on (1,2,3,4,5,6,7,8) results in (1,3,5,7,2,4,6,8)
• Performing the riffle on (1,3,5,7,2,4,6,8) results in (1,5,2,6,3,7,4,8)

### SOLUTION

Program: Chef and Riffles RIFFLES Solution in C++

``````#include <iostream>
#include<vector>
using namespace std;
int main()
{
int t;
cin>>t;
while(t--)
{
int n,k;
cin>>n>>k;
vector<int>v(n+1);
int arr[n+1];
int j=1;
for(int i=1;i<=n;i+=2)
arr[i]=j++;
for(int i=2;i<=n;i+=2)
arr[i]=j++;
for(int j=1;j<=30;j++)
{
for(int i=1;i<=n;i++)
arr[i][j]=arr[arr[i][j-1]][j-1];
}
vector<int>a(n+1);
for(int j=1;j<=n;j++)
{
int temp=k;
int p=j;
for(int i=0;i<=30;i++)
{
if(1<<i&temp)
p=arr[p][i];
}
a[p]=j;
}
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
cout<<'\n';
}
}``````

Program: Chef and Riffles RIFFLES Solution in Java

``````import java.util.*;
import java.lang.*;
import java.io.*;
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner in = new Scanner(System.in);
int T = in.nextInt();
for (int t = 0; t < T; t++) {
int N = in.nextInt(), K = in.nextInt();
int[][] jump = new int[N];
for (int i = 0; i < N / 2; i++) {
jump[i * 2] = i;
jump[i * 2 + 1] = N / 2 + i;
}
for (int j = 1; j < 32; j++) {
for (int i = 0; i < N; i++) {
jump[i][j] = jump[jump[i][j - 1]][j - 1];
}
}
int[] res = new int[N];
for (int i = 0; i < N; i++) {
int current = i;
int n = K, j = 0;
while (n > 0) {
if (n % 2 == 1) {
current = jump[current][j];
}
n >>= 1;
j++;
}
res[current] = i;
}
for (int i = 0; i < N; i++) {
System.out.print((res[i] + 1) + (i == N - 1 ? "\n" : " "));
}
}
}
}``````

Program: Chef and Riffles RIFFLES Solution in Python

``````for _ in range(int(input())):
a,b = map(int,input().split())
a =  * a
c = 1
no=(len(a)//2)+1
while(no!=2):
if(no%2==1):
no = (no//2)+1
else:
no = (no+len(a))/2
c+=1
b = b%c

for i in range(c-b-1):
else: