# Lambda Calculi - March 2016 on HackerRank

Hello everyone,

I'd like to invite all of you to the Lambda Calculi - March 2016 contest hosted by HackerRank. The contest is a functional programming competition. It starts Mar 25 2016, 06:30 am CET and lasts for 3 days. The purpose of the contest is to test your functional programming skills starting from some basic concepts to harder algorithmic problems.

The top 10 participants will be awarded with HackerRank T-shirts.

I'm the author of two harder problems in the contest, so I want to give you some clues about them. The first problem is purely about implementing a data structure (an extension a very well-known one), while the second one is going to test your ability to present some standard concepts used in imperative programming in a functional programming domain.

# Code Monk (Number Theory II) for HackerEarth

I am happy to announce the upcoming Code Monk (Number Theory II) contest on HackerEarth. I am the author of one problem there and the editorialist for the whole problem set.

The contest is scheduled for September 23rd. You can expect great problems covering combinatorics and probabilities - very useful topics in competitive programming.

# My contest // Codemonk Revision for HackerEarth

I am very happy to announce my first contest prepared for HackerEarth. It is a part of Codemonk series, which is very popular recently.

The contest is available here: Codemonk Revision

So far, each contest from that series has covered some particular category of algorithms and data structures, not only with problems, but also with an educative article which helped to solve the problems. We have seen graph algorithms, number theory and many more.

My contest is the revision of all Codemonks prepared so far, so you can expect a variety of different problems with cool stories

I also want to thank Bohdan Pryshchenko (lebronI_love_Tanya_Romanova) for testing the problems in extreme conditions

Cheers and see you on leaderboards.

# 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.

# Almost Equal Strings // My problem in Code.cpp contest

I created the most difficult problem for May edition of Code.cpp on HackerRank. The full problem is available here. The problem got great attention, because many contestants were surprised how it is possible to "compare" two strings that fast.

The statement is quite straightforward:

We define two strings $S$ and $W$ as almost equal if and only if they have the same length and they differ on at most one position.

You are given a string $S$ of length $N$ and an integer $Q$. You have to perform $Q$ queries on $S$. Each query consists of four integers, $i$, $j$, $k$, and $l$. For each such query, your task is to decide if the substrings $S[i, j]$ and $S[k, l]$ are almost equal.

While the problem is formulated very simple, the solution is not obvious, especially because there are many queries to handle - up to $10^5$ and the input string can have at most $10^6$ letters. I will sketch two completely different approaches here.

## LCP Method

First of all, we construct suffix array for string $S$. While $O(n \cdot \log n)$ algorithm is fine here, we can use a simple and famous linear one by Kärkkäinen and Sanders known as Skew algorithm

After that, we compute longest common prefix array abbreviated as $LCP$ array, where $LCP[i]$ is the longest common prefix of suffixes $i$ and $i-1$ in the suffix array.

Using our $LCP$ array and some range queries, we are able to compute the length of the longest common prefix for arbitrary suffixes of $S$, the sketch of this method is available here.

Being able to do that, let's consider any query $i, j, k, l$ and two substrings $S[i, j]$ and $S[k, l]$. Let assume that they have equal length $K$, because the other case is trivial. In order to answer, if these substrings are almost equal, first we compute the length of $LCP$ of suffixes of $S$ starting in $i$ and $k$. Let this length to be $L$. If $L \geq K$, then we know that our two substrings are exactly equal. In the other case, we know that they differ on position $L + 1$, so we compute the length of the $LCP$ of suffixes starting just after this different character and the answer to the query is positive if these suffixes have equal at least $K - L - 1$ characters, otherwise it is negative.

### Time Complexity

If we use Skew algorithm and the fastest method of computing $LCP$ of arbitrary strings, we can achieve $O(n + q)$, but any algorithm running in $O(n \cdot \log n + q \cdot \log q)$ is also fine.

## Hashing method

The idea is to provide a method for deciding if $S[i, j] = S[k, l]$ in constant time for any $i \leq j$ and $k \leq l$

For now, let's assume that we can do that.

Then in order to decide if $S[i, j]$ is almost equal to $S[k, l]$, first we check if they have equal length. If they have, then we check if $S[i, j] = S[k, l]$ if it is, they are exact the same strings. If not, we find the first letter on which they are different. We can do this using binary search and our method for equality of substrings on prefixes of both strings. After we find this first letter, let say it has index $x$ inside these strings, we just need to compare $S[i + x + 1, j]$ with $S[k + x + 1, l]$ and we assumed that we can do this in $O(1)$ time.

In order to do our magic comparison in constant time, first we define

$H[i] = s[0] \cdot P^{i - 1} + s[1] \cdot P^{i - 2} + ... + s[i - 1] \cdot P^1 + s[i]$

which is called polynomial hash of a string and we can compute $H[i]$ for all $0 \leq i \leq n - 1$ in $O(n)$ using Horner's method i.e:

$H[0] = s[0]$

$H[i] = P \cdot H[i - 1] + s[i]$ for $i > 0$

All these computations can be done modulo some big prime, but it is faster to use unsigned long long type here, especially for c++ which is nice in this contest, and we can avoid modulo computation.

The next step is to be able to check if $S[i, j] = S[k, l]$ and we can do this by multiplications and subtractions of some values from $H$ table, which can be done in constant time.

Of course this method is a probabilistic one and it can return false results, but we can either assume that it works for one $H$ function, or compute more than one hashing function to increase its probability. It is worth to mention that using two functions rather that one squares the probability of an error. An example of using two functions can be computing both as $H$ function given above, but for each one computing it modulo a different big prime number.

### Time Complexity

Computing $H$ table takes $O(n)$ and binary search for one query takes $O(\log n)$, so the overall complexity is $O(n + q \cdot \log n)$.