In this HackerRank Swap Permutation problem solution we have given an array A = [1, 2, 3, ..., n]:
- How many sequences (S1) can you get after exact k adjacent swaps on A?
- How many sequences (S2) can you get after at most k swaps on A?
An adjacent swap can be made between two elements of the Array A, A[i] and A[i+1] or A[i] and A[i-1]. A swap otherwise can be between any two elements of the array A[i] and A[j] ∀ 1 ≤ i, j ≤ N, I ≠ j.
Problem solution in Python.
#!/bin/python3
import os
import sys
#
# Complete the swapPermutation function below.
#
def swapPermutation(n, k):
#
# Write your code here.
#
mod = 1000000007
s = [1] + [0] * k
t = [1] + [0] * k
for i in range(1, n):
temp = sum(s[max(k - i, 0):k]) % mod
for j in range(k, 0, -1):
s[j] = (s[j] + temp) % mod
if j > i:
temp = (temp + s[j - i - 1] - s[j - 1]) % mod
else:
temp = (temp - s[j - 1]) % mod
for j in range(k, 0, -1):
t[j] = (t[j] + i * t[j - 1]) % mod
return sum(s[k % 2::2]) % mod, sum(t) % mod
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
nk = input().split()
n = int(nk[0])
k = int(nk[1])
result = swapPermutation(n, k)
fptr.write(' '.join(map(str, result)))
fptr.write('\n')
fptr.close()
Problem solution in Java.
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;
class Result {
public static List<Integer> swapPermutation(int n, int k) {
// Write your code here
long [][] dp0 = new long[n + 1][k + 1];
long [][] sum0 = new long[n + 1][k + 2];
int mod = 1000000007;
for(int i = 0; i < n + 1; i++) dp0[i][0] = 1L;
for(int i = 1; i < k + 2; i++) sum0[1][i] = sum0[1][i - 1] + dp0[1][i - 1];
for(int i = 1; i < n + 1; i++) sum0[i][1] = 1L;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= k; j++){
int head = Math.max(0, j - i + 1);
dp0[i][j] = sum0[i - 1][j + 1] - sum0[i - 1][head];
sum0[i][j + 1] = (sum0[i][j] + dp0[i][j]) % mod;
}
}
long ans1 = 0L;
for(int i = k; i >= 0; i -= 2) ans1 = (ans1 + dp0[n][i]) % mod;
long [][] dp1 = new long[n + 1][k + 1];
for(int i = 0; i <= n; i++) dp1[i][0] = 1L;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= k; j++){
dp1[i][j] = (dp1[i - 1][j] + ((i - 1) * dp1[i - 1][j - 1]) % mod) % mod;
}
}
long ans2 = 0L;
for(int i = 0; i <= k; i++) ans2 = (ans2 + dp1[n][i]) % mod;
List<Integer> ans = new ArrayList<>();
ans.add((int)ans1);
ans.add((int)ans2);
return ans;
}
}
public class Solution {
public static void main(String[] args) throws IOException {
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
String[] firstMultipleInput = bufferedReader.readLine().replaceAll("\\s+$", "").split(" ");
int n = Integer.parseInt(firstMultipleInput[0]);
int k = Integer.parseInt(firstMultipleInput[1]);
List<Integer> result = Result.swapPermutation(n, k);
bufferedWriter.write(
result.stream()
.map(Object::toString)
.collect(joining(" "))
+ "\n"
);
bufferedReader.close();
bufferedWriter.close();
}
}
Problem solution in C++.
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
uint64_t mod = 1000000007;
uint64_t **dyn_adjswap;
uint64_t **dyn_anyswap;
int nsz = 2550;
int ksz = 2550;
void generate_adjswap()
{
dyn_adjswap = new uint64_t*[nsz];
for(int n=2; n<nsz; n++)
{
dyn_adjswap[n]=new uint64_t[ksz];
if(n==2){
for(int k=-1; k<ksz-1;k++) dyn_adjswap[n][k+1]=1;
continue;
}
dyn_adjswap[n][0] = 0;
for(int k=0; k<ksz-1; k++)
{
dyn_adjswap[n][k+1] = dyn_adjswap[n-1][k+1] + dyn_adjswap[n][k-1+1];
if(k>=n) dyn_adjswap[n][k+1] += mod - dyn_adjswap[n-1][k-n+1];
dyn_adjswap[n][k+1] %= mod;
}
}
}
void generate_anyswap()
{
dyn_anyswap = new uint64_t*[nsz];
for(int n=2; n<nsz; n++)
{
dyn_anyswap[n]=new uint64_t[ksz];
if(n==2){
for(int k=0; k<ksz;k++) dyn_anyswap[n][k]=1;
continue;
}
dyn_anyswap[n][0] = 1;
for(int k=1; k<ksz; k++)
{
dyn_anyswap[n][k] = dyn_anyswap[n-1][k] + (n-1)*dyn_anyswap[n-1][k-1];
dyn_anyswap[n][k] %= mod;
}
}
}
uint64_t adjswap(int n, int k)
{
return dyn_adjswap[n][k+1];
}
uint64_t anyswap_atmost(int n, int k)
{
return (dyn_anyswap[n][k]+dyn_anyswap[n][k-1]) % mod;
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
generate_adjswap();
generate_anyswap();
int n, k;
cin >> n >> k;
cout << adjswap(n,k) << " " << anyswap_atmost(n,k) << endl;
}
Problem solution in C.
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(X,Y) (X>Y)?Y:X
#define f(i,a,b) for(int i = (a); i <= (b); i++)
typedef long long ll;
const ll MOD = 1000000007;
int N, K;
ll A[2505][2505], T[2505], B[2505][2505];
void update1(int x, ll v)
{
while(x <= 2501)
{
T[x] = (T[x]+v) % MOD;
x += x&-x;
}
}
void update2(int l, int r, ll v)
{
l++, r++;
update1(l,v), update1(r+1,-v);
}
ll query(int x)
{
x++;
ll ret = 0;
while(x>0)
{
ret = (ret+T[x]) % MOD;
x -= x&-x;
}
return ret;
}
int main()
{
A[1][0] = 1;
f(i,1,2499)
{
f(j,0,2500) update2(j,min(j+i,2500),A[i][j]);
f(j,0,2500) A[i+1][j] = query(j);
f(j,0,2501) T[j] = 0;
}
B[1][1] = 1;
f(i,1,2499) f(j,1,i)
{
B[i+1][j+1] = (B[i+1][j+1] + B[i][j]) % MOD;
B[i+1][j] = (B[i+1][j] + B[i][j]*i) % MOD;
}
int N;
int K;
scanf("%d",&N);
scanf("%d",&K);
ll ans = 0, ans2 = 0;
for(int j = K; j >= 0; j -= 2) ans += A[N][j];
f(i,0,min(K,N-1)) ans2 += B[N][N-i];
ll a1 = ans%MOD;
ll a2 = ans2%MOD;
printf("%lld %lld\n",a1,a2);
}
0 Comments