# Hackerrank Weekly Challenge #5 // Problem 4

The 4th problem has strictly combinatorial nature. You're given two numbers $n$ and $k$, where $1 \leq n, k \leq 2500$. You have to answer two following questions:

1. What is the number of permutations which can be created after performing exactly $k$ swaps of adjacent elements from the sequence $1, \ldots, n$
2. What is the number of permutations which can be created after performing at most $k$ swaps of any two elements from the sequence $1, \ldots, n$

I omit in that editorial the fact that you have to return these results modulo $10^9 + 7$, but remember to do that.

### First question

Let's solve the first question first. The idea that came to my mind is to use the dynamic programming concept here. Let's define

$dp[n][k] :=$ number of permutations achievable from $1, \ldots, n$ using exactly $k$ adjacent swaps, but with the restriction that we don't swap the same elements more than once.

In other words, $dp[n][k]$ is the number of permutations of $n$ elements with exactly $k$ inversions. That observation helps us to define a recursive relation. If we have already computed $dp[n - 1][j]$ for all $j$, we can get $dp[n][k]$ by inserting the $n$-th element at some place and we know that if after that insertion, there are $m$ elements after the $n$-th element, we just created exactly $m$ new inversions. It follows that the complete recursive relations is:

$dp[n][k] = \sum\limits_{j=0}^{\min(k, n - 1)} dp[n - 1][k - j]$

which can be computed faster as:

$dp[n][k] = dp[n][k - 1] + dp[n - 1][k] - dp[n - 1][k - n]$

The last term of the above equation is define only for $k \geq n$, otherwise it's 0.

The base cases are:

$dp[n][0] = 1$ for any $n$

and

$dp[1][1] = 1$.

So far, we computed the number of permutations with exactly $k$ inversions. The last observation is that if you're allowed to do exactly $k$ swaps, you can achieve any permutation with $k, k - 2, k - 4, \ldots$ inversions (the last element of that sequence is either 0 or 1 depending on the parity of $k$), because you can erase any inversion by swapping back these elements immediately after the inversion was made with exactly one additional swap. In other words, you can use exactly 2 swaps to make no swaps.

To compute the exact result, you have to sum up the values of $dp[n][m]$ for $m \in \{k, k - 2, k - 4, \ldots, \}$.

### Second question

I suspected that the answer is somehow connected to the Stirling numbers, but didn't know how exactly. I thought that I can write a brute force solutions to provide answers for small $n, k \leq 5$ and then use the OEIS (the On-Line Encyclopedia of Integer Sequences) to figure out the exact solution. Let $f[n][k]$ be the answer to our question. It turned out that a brute force can be written as a simple DFS on the graph, where permutations are nodes, and there is an edge between two permutations if and only if you can transform one to the other using exactly one exchange of elements. I managed to do that quickly and it gave me the following table:

n / k 0 1 2 3 4
1 1
2 1 2
3 1 4 6
4 1 7 18 24
5 1 11 46 96 120

You can observe that the value for $k \geq n$ is the same as when $k = n - 1$ because if you can exchange $n - 1$ elements, you can create all permutations.

If you want to identify in OEIS an sequence depending on two variables ($n$ and $k$ here), you have to put its values in the row major form i.e. print values row by row. In that case, it's 1,1,2,1,4,6,1,7,18,24,1,11,46,96,120 and it gives the sequence A109822 and the recursive relation for that is:

$f[n][k] = \sum\limits_{i=0}^{\min(k, n)} st[n][n - i]$

where $st[n][k]$ is the absolute value of the Stirling number of the first kind for $n$ and $k$. These numbers can be computed using the recurence relation and a dynamic programming concept.

### Summary

The time complexity for both questions is $O(n \cdot k)$.

You can find my solution from the contest here:

# Codechef Long Rating Update

The Codechef long rating is up to date after the last contest. I earned +1240 points and I'm currently 274th overall and 3rd in Poland http://www.codechef.com/users/pkacprzak.

Mu current goal is to get to the top 100 overall.

# Hackerrank Weekly #5 / problem 2

Tuesday problem is really easy. The full problem statement is here. You are given 3 integers $a, b, x$. You have to return the closest multiplicity of $x$ to $a^b$. It's guaranteed that $a^b \leq 10^9$ which is really good. You have to do it fast, because one test file contains up to $10^5$ testcases.

A pretty straightforward method for solving this is to first compute:

$p := a^b$

and two multiplicities of $x$:

1. The first one is the greatest number of form $x \cdot k$ which is less or equal $p$, let's call it $m_1$:

$m_1 := \lfloor p / x \rfloor \cdot x$

2. The second one is the smallest number of form $x \cdot k$ which is greater than $p$, let's call it $m_2$:

$m_2 := (\lfloor p / x \rfloor + 1) \cdot x$

It remains to return the closest one to $p$ of these two numbers. Really easy task.

# Hackerrank Weekly #5 / problem 1

A quick post on the first problem from Hackerrank Weekly #5.

After a quick analysis of the problem statement, you can reformulate it in the following way:

You're given the array $A[1..n]$.

After that, there are $q$ queries. For each query $(i, j)$ you have to print the parity of the following formula:

$pow(a_i, pow(a_{i+1}, \ldots, pow(a_j, 1) \ldots )$,

where

$pow(x, k) := x^k$

Let's take a query $(i, j)$. In order to decide the parity for that query, you have to decide what's the parity of $a_i$ raised to some power $p$.

For any $p > 0$, it's sufficient to check the parity of $a_i$, because if $a_i$ is even, then after raising to any positive $p$ it's still even and if $a_i$ is odd, then after raising to any positive $p$ it remains odd.

The only other case is when $p = 0$ (it's guaranteed that there are no two adjacent 0 in the array $A$, so $0^0$ never happens).

We can observe that $p = 0$ if and only if $a_{i + 1} = 0$. If that's the case then parity of $a_i$ doesn't matter and the result is always odd, because we raise a non negative number to $0$-th power.

The time complexity of that method is $O(n + q)$.

# Codechef Long June 2014 // results

The Codechef Long June 2014 has just ended. I'm super excited, because I finished 39th solving 9/10 problems, including a good score for the tie-breaker problem achieved in a very simple way.

I'm going to post detailed solutions to several problems from the contest soon.