# HackerRank Regular Expresso Contest

Tomorrow a new type of contest will be hosted on HackerRank. It's going to be all about regular expressions - a concept that all software engineers should be aware of.

Register for the contest

The contest duration is set to 24 hours and top 10 participants will be awarded with HackerRank T-Shirts. I created two problems there and I'm going to take care of user questions during the contest. As a hint, I can tell you that most problems are not hard if you are familiar with regular expressions already, so speed will be a big factor here.

Have fun with it and see you on leaderboard!

# Indeed Prime Codesprint by HackerRank

Yesterday, I took part in Indeed Prime Codesprint hosted by HackerRank.

The contest duration was 24 hours, but I started solving problems when 8 hours were remaining. There were just 5 problems to solve and nice prizes for top 3 competitors as well as T-shirts for top 100.

I finished 72nd out of over 1400 total contestants. It was quite funny, because I struggled a lot with the 4th problem and when I got it finally accepted, there was very little time to write any solution to the hardest problem. Then I realized, that without solving it I would finished out of top 100, so I decided to write a dynamic programming solution, without any optimizations, and definitely too slow to pass all test cases. However, it was enough to pass over 1/3 of them, which gave me the final position and hopefully at least a T-shirt.

I want to mention that two hardest problems are worth to solve, because they require concepts and ideas every competitor basically must know, so if you want to practice or even learn something new, try them definitely.

# One of the greatest contests is coming

Counter Code is one of the biggest 24 hours contests this year. I am super excited, because my problem will be used as a hard challenge there Together with Kevin (kevinsogo), who was a tester, we put a great effort to prepare it and we had a lot of fun doing it too For now, I can tell you that the problem is called Long Narrow City and it is a graph related challenge.

The contest is sponsored by 6 big companies including Asana, which I use personally. There are cool prizes to win, so we expect a great number of participants - you cannot miss it!

Right now, I am working on the editorial for the problem, which will be very detailed and I will post it after the contest on HackerRank and also here, so stay tuned.

# Knight and Queen // HackerRank Lambda Calculi

It's been a while since my last post here. I've been busy working with my team on a brand new game for Android and iOS.

Anyway, I'm back with a very interesting problem. I was asked to test some problem for HackerRank Lambda Calculi Contest. The one which I want to write about is Knight and Queen. The original problem is available here:

https://www.hackerrank.com/contests/lambda-calculi-10/challenges/knight-and-queen

## Problem statement

Two players are about to play a game on a chessboard of size n x n, where the bottom-left cell has coordinates (0, 0). There are only 2 figures on the board: the Knight and the Queen. Both figures moves like in a classic chess game, but with a restriction that they cannot move right or up, so every legal move is left, down or left and down. For example, the Knight standing on a field (5, 4) can move to (4, 2) or (3, 3) but cannot move to (6, 6). Also note that both figures can be a the same cell in the same time.

Players takes moves alternately. Player who is about to make a move can pick the Knight or the Queen and make any valid move with in. A player who is not able to make a move is declared a looser.

Your task is to decide who is a winner knowing the initial positions of both figures and the fact that both players plays optimally.

You will be given many testcases, so the best you can do is to be able to provide the answer for any given initial positions fast.

## Solution

If n is quite small, you can consider a dynamic programming solution where we have n^4 positions: n^2 possible positions of the Knight multiplied by n^2 possible positions of the Queen. For each such position, you can compute the best possible move in O(n) time, so a total time will be O(n^5), but since we have n = 50, this is way to much.

We need a faster solution.

### Game of Nim

Let's consider a simpler game called Nim first. In the Nim game, there are N distinct heaps. Each heap has a positive number of objects. Players takes moves alternately. Player who is about to make a move, can choose any non-empty heap and remove any positive number of objects from it. A player who is not able to make a move is declared a looser and a player is not able to make a move if and only if all heaps are empty.

This is a very classic game, a fundamental one in game theory. There is a famous theorem which can be used to determine who has a winning position in Nim at the beginning of the game if both players plays optimally. If you haven't heard about it yet, you should be amazed at least a little bit.

Theorem

Let a_1, a_2, ..., a_N be current sizes of heaps i.e. a_i is the number of objects in the i-th heap before the next move. Let X = a_1 xor a_2 xor ... xor a_N, where xor is a binary xor operation.

A player who is about to make a move has a winning position if and only if X != 0.

In other words, if X != 0 and you are about to make a move, you can win no matter what, and if X == 0 and you are about to make a move, no matter what will you do in that move, your opponent can always win.

Sounds great! Let's make a sketch of a proof.

Let X == 0 before the next move. There are two possibilities:

1. All heaps are empty, so the current player is a looser
2. There is at least one non-empty heap

Since the first situation is clear, let's consider the second one. The current player has to remove at least one object from a non-empty heap, so no matter what will he do, the xor of sizes of all heaps after his move will be non-zero.

On the other hand, if X != 0 before the next move, the player who is about to make a move can always choose a valid move leading to a situation that the xor of sizes of all heaps after this move will be 0.

If you want to more detailed explanation, check it here or do it on your own considering binary representation of heaps sizes.

### Our problem

Let's think of our problem as of a special game of Nim where we have only two heaps, the first one for the Knight and the second one for the Queen and let's consider these two heaps separately. For each of these two heaps, we will assign a single number to any position of the figure corresponding on the board. This number will correspond to the number of objects in a game of Nim on a single heap.

Knight's heap

Let's consider any position of the Knight such that there is no valid move with this figure. Any such position is equivalent to an empty heap, so we will assign 0 to any such position. Next let's consider any other position P, and let M be a set of numbers assigned to all positions reachable from P. We will assign the smallest non-negative integer which is not in M to the position P.

Queen's heap

We will do the same as above with respect to Queen's valid moves.

After making these two above computations, we have assigned numbers to any valid position of each figure on a board. We can think of these numbers as of the number of objects in the corresponding heap in a Nim game - just note that in Nim if you have k objects on a heap before your move, you can reduce the number of objects in this heap to any non-negative number less than k. The same is true in our game. If you decided to move the Queen in your turn, and it is currently in a cell with number k assigned to it, you can move it to a different cell with any assigned non-negative number less than k.

So in order to solve our problem, just assign the numbers as described above to both Knight's and Queen's positions. Let X be the xor of assigned numbers corresponding to the initial position of both figures. The player who starts the game has a winning strategy if and only if X != 0.

### Time complexity

For a board of size n x n, you have to compute two tables of size n x n and computing a single position in any of these tables takes at most O(n) time, so the total complexity is O(n^3) if you use memoization or dynamic programming and here we have n = 50, so it will be very fast.

## Related problems

One interesting thing is that many simple games can be reduced to Nim. I encourage you to read about that here.

# My problem for Hackerrank Weekly Challenge #12 // Favorite sequence

You can find and solve the problem here: https://www.hackerrank.com/contests/w12/challenges/favourite-sequence

## Problem statement

In this problem you are given $N$ sequences of distinct numbers. The task is to construct the shortest sequence S, such that all $N$ sequences are (not necessarily continuous) subsequences of $S$. If there are many such sequences, then you have to construct the lexicographically smallest one. It is guaranteed that such a sequence exists.

Sequence $A[1\ldots n]$ is lexicographically less than sequence $B[1\ldots n]$ if and only if there exists $1 \le i \le n$ such that for all $1 \le j < i, A[j] = B[j] \ \ and\ \ A[i] < B[i]$.

## Solution

Let's consider the following example first, there are 3 sequences:

1 3
2 3 4
6 5

From the first one, you know that in the resulting sequence 1 has to be before 3, while from the second one you know that 2 has to be before 3 and 3 has to be before 4 and. From the third one you know that 6 has to be before 5.

Based on these facts we can construct a graph of precedence. Let's call this graph G. Numbers presented in sequences are vertices in G and there is a directed edge $(u, v)$ if and only if there is a sequence where $v$ is a direct successor o $u$.

Out example graph G looks like this:

1

34

2

65

It is easy to see that the shortest valid sequence will be a topological sorting of vertices of G. A topological order is a linear ordering of vertices such that for every directed edge $(u, v)$, $u$ comes before $v$ in the ordering. The reason for this is that any topological order forms a valid sequence, because it preserves all precedence relations from all input sequences and it is the shortest one, because any number is presented only once. We reduced the problem to finding the lexicographically smallest one topological order of G. If you want to read more about topological order, you can check this article.

A graph can have many topological orders, for example any of below orders is a valid topological order of our graph G, but there are even more valid ones:

2 1 3 4 6 5
1 2 3 4 6 5
6 1 2 5 3 4

The problem statement says that we have to return the lexicographically smallest one and in our case it is: 1 2 3 4 6 5.

While there are several methods of finding a topological order of a graph, we will use the following, because it is easy to modify it to construct the lexicographically smallest one.

Since there exists a topological order of vertices, there exists a vertex with in-degree 0. It is easy to see that if any vertex has in-degree greater than 0, topological order does not exist because is a directed cycle in the graph. We construct the desire order in a main loop:

While there exists a vertex in the graph:
select a vertex v with in-degree 0, add it to the resulting order and remove it with all outgoing edges from the graph


You can prove that the above method returns a topological order. If we want the lexicographically smallest one, inside the loop we have to pick a vertex represented by a smallest number from vertices with in-degree 0.

In order to implement the above method, we can use a priority queue where vertices are ordered by in-degree and if two vertices have the same in-degree, then a number on these vertices decides (a vertex with smallest number on it has higher priority). While we are in the main loop, we pick the first vertex $u$ from the queue, delete it from it, put in into the resulting order and decrease in-degree of every vertex $v$ such that there is an edge $(u, v)$ in a graph.

## Time complexity and implementation details

The time complexity of the above method depends on the queue implementation. We can achieve $O((V + E) \cdot \log V)$ where $v$ is the number of vertices in the graph and $E$ is the number of edges in it, if we implement the queue as a heap with pointers or a balanced binary tree. This is because we $V$ times select the minimum from the queue and $E$ times we decrease in-degrees of vertices in the queue which has at most $V$ elements in it and each of these operations takes logarithmic time on a heap with pointers (you have to have pointers to elements in order to achieve this performance for a decrease operation, because you have to be able to find any element quickly) or a balanced binary tree. We can notice that $V$ and $E$ are at most $N \cdot K$.