Chef and Riffles RIFFLES Solution Codechef

Chef and Riffles RIFFLES Solution Codechef

by

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

Subtasks

  • 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][31];
        int j=1;
        for(int i=1;i<=n;i+=2)
             arr[i][0]=j++;
        for(int i=2;i<=n;i+=2)
             arr[i][0]=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][32];
	        for (int i = 0; i < N / 2; i++) {
	            jump[i * 2][0] = i;
	            jump[i * 2 + 1][0] = 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 = [0] * 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
   
    adfac = (len(a))//2
    for i in range(c-b-1):
        if(adfac%2==0):
            adfac = adfac//2
        else:
            adfac = (adfac+len(a))//2
    a[0] = 1
    for i in range(1,len(a)):
        new = a[i-1] + adfac
        if(new>len(a)):
            a[i] = (new%len(a))+1
        else:
            a[i] = new
    for i in a:
        print(i,end=" ")
    print()

January Long Challenge 2022 Solution

Leave a Comment

twenty − sixteen =