Chef and Riffles RIFFLES Solution Codechef

Codechef Chef and Riffles RIFFLES Solution

Let ff be a permutation of length NN, where NN is even. The riffle of ff is defined to be the permutationg=(f(1),f(3),…,f(N−1),f(2),f(4),…,f(N))g=(f(1),f(3),…,f(N−1),f(2),f(4),…,f(N))

You are given two integers NN and KK. Output the resultant permutation when you riffle the identity permutation of length NN, KK times.

The identity permutation of length NN is σN=(1,2,…,N)σN=(1,2,…,N)

Input Format

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

Output Format

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

Constraints

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

Subtasks

  • Subtask 1 (30 points): NN is a power of 22
  • 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 11: Performing the riffle on σ6=(1,2,3,4,5,6)σ6=(1,2,3,4,5,6) once results in (1,3,5,2,4,6)(1,3,5,2,4,6), by definition.

Test case 22: The process goes as follows:

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

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

December Long Challenge 2021 Solution

Leave a Comment