Monthly Archives: October 2014

Order exercises // My problem in Functional Programming Contest - October'14

You can find the problem here: https://www.hackerrank.com/contests/lambda-calculi-oct14/challenges/order-exercises

Problem statement

You are given an array of n integers, a = \{a_1, a_2,\ldots, a_n\} along with the following definitions:

- a subarray is a contiguous segment of an array. For example a[l, r] = \{a_l, a_{l+1},\ldots, a_r\} is a subarray, where 1 \le l \le r \le n

- We say that a sum of a subarray is a sum of elements in this subarray

- We say that subarray X = \{a_{i}, a_{i+1},\ldots,a_{j}\} is greater than subarray Y = \{a_{k}, a_{k+1},\ldots,a_{l}\} if and only if one of the following statements is true:
- X has a greater sum than Y
- X and Y has the same sum and X begins earlier
- X and Y has the same sum, they start in the same place and the length of X is smaller than the length of Y

It is guaranteed that there is no 0 in the array a.

You are given also an integer k. The task is to print as many as possible, but not more than k, subarrays with a positive sum in the following order.

- The first subarray is the greatest subarray in the array according to above definition.

- The i^{th} subarray is the greatest subarray disjoint to any of the j^{th} subarray, where j < i (disjoint means that they have no common elements).

Solution

If you are familiar with the Maximum subarray problem you may notice that our problem is a natural extension of it.

Simple, but not enough solution

Probably the first solution which comes to mind is to run Kadane algorithm or similar to get the value of the greatest subarray, then assign - \infty to every element of that subarray, find the second greatest subarray and so on. We iterate that process while there exists a subarray with a positive sum.

The time complexity of this method is O(n \cdot k) which gives you some points, but it is too slow to pass all testcases even if it is hardly optimized.

Faster solution

The general pattern of above solution is good, but we have to find the next subarray faster. A segment tree can help us here.

The first thing here is to implement a segment tree which supports the following query in O(\log n) time:

query(i, j) returns the greatest subarray in \{a_i, a_{i+1},\ldots, a_j\}

Let T_v be a subtree represented by a node v and a_v be an array corresponding to elements covered by T_v. We can implement that query maintaining in every node v several values:

- sum of the greatest subarray in a_v
- greatest prefix sum of a_v
- greatest suffix sum of a_v
- sum of values of elements in a_v

You can compute these values of any v based on values in its children. Values for leaves are obvious. After that, if you are familiar with segment trees, you can implement the query(i, j) easily.

In order to do the next step we need a priority queue, let's call it Q. We store in the queue triplets \langle R, V, P\rangle where:

- R is a range in which we search for subarrays
- V is the value of the greatest subarray in R
- P represents indices of the greatest subarray in R

Ordering of elements in Q is determined by values V and P.

First we compute the value and indices of the greatest subarray in the whole array. We do it using query(1, n). Let's assume that it is a[i, j] and has a sum V. We put into the queue a triplet \langle (1, n), V, (i, j)\rangle.

While Q is not empty and we have found less than k subarrays so far, we select the greatest triplet from the queue and remove it from there. Let's assume that the triplet is \langle (k, l), V, (i, j)\rangle. We print V as a result and if a range (k, i - 1) is not empty, we compute query(k, i - 1) and if it returns a subarray with a positive sum S with indices (c, d), we put into the queue a triplet \langle (k, i - 1), S, (c, d)\rangle. We do the same thing with a range (j + 1, l).

Time complexity

Time needed to construct the tree is O(n \cdot \log n) and we do at most O(k) queries, so the total complexity is O(n \cdot \log n), because k \leq n.

Sequence full of colors // My problem in Functional Programming Contest - October'14

Problem statement

You are given a sequence of N balls in 4 colors: red, green, yellow and blue. The sequence is full of colors if and only if all of the following conditions are true:

  1. There are as many red balls as green balls.
  2. There are as many yellow balls as blue balls.
  3. Difference between the number of red balls and green balls in every prefix of the sequence is at most 1.
  4. Difference between the number of yellow balls and blue balls in every prefix of the sequence is at most 1.

Your task is to write a program, which for a given sequence prints `True` if it is full of colors, otherwise it prints `False`.

The original problem statement can be found here https://www.hackerrank.com/contests/lambda-calculi-oct14/challenges/sequence-full-of-colors

Solution

While you can solve it processing the sequence from left to right counting the number of balls for each color, the purpose of this problem is encourage you to write an automata based solution which uses O(1) memory and reads the input sequence only once. You can read more about automatas here.

Let's define our automata A. It has 9 states corresponding to all combinations of valid differences between number of colors:

Let's define:

d_1 := number of red balls minus number of green balls
d_2 := number of yellow balls minus number of blue balls

All valid values for d_1 and d_2 are \{-1, 0, 1\}, so we define states of the automata as:

s_1 := (d_1 = -1, d_2 = -1)
s_2 := (d_1 = -1, d_2 = 0)
s_3 := (d_1 = -1, d_2 = 1)
s_4 := (d_1 = 0, d_2 = -1)
s_5 := (d_1 = 0, d_2 = 0)
s_6 := (d_1 = 0, d_2 = 1)
s_7 := (d_1 = 1, d_2 = -1)
s_8 := (d_1 = 1, d_2 = 0)
s_9 := (d_1 = 1, d_2 = 1)

We begin processing the input sequence in s_5, because initially d_1 = 0 and d_2 = 0. After reading a character, we have to change the current state. For example, if we are in s_5 and we see a red bal, we change the current state to s_8, because now d_1 = 1. All other transitions are easy to define, so I left that as an exercise.

If during the computation d_1 or d_2 becomes invalid, then we return 'False'. If there is no invalid value during the computation, we return 'True' if the end state equals d_5 and 'False' otherwise. The reason for this is that we have to satisfy conditions 1 and 2 from the problem statement.

Complexity

Time complexity of that method is O(n) while space complexity is only O(1). It's worth to mention that a solution which uses counter, theoretically doesn't have O(1) space complexity.

The most beautiful city // My problem for Finals of CodeSprint India 2014

This problem worked perfectly as the easiest one in the problem set. Everyone managed to solve it which was the purpose here. The story in the statement is quite long, but the solution is really simple and moreover it can be coded very quickly as I will show you.

Problem statement

The full problem is available here.

Long story short, you are given a multiset S of k numbers in a range [1, n]. The task is to print these ones which have an odd number of divisors and for each such number, you have to print also the number of times that it is presented in S.

The crucial thing here is to decide if a number a has an odd number of divisors. The most clever way of doing that is to check if a is a square number, because only square numbers have an odd number of divisors - every divisor besides a square root of a has an unique paired divisor.

I included my code below because it is very short and self-explanatory. The time complexity of this method is O(k + n), but more important it is very quickly to code.


#define FOR(i,n) for(int (i)=0;(i)<(n);++(i))
#define MAX_N 1000010

using namespace std;

int res[MAX_N];

int main()
{
   int n, k;
   scanf("%d", &n);    
   scanf("%d", &k);
          
   FOR(i, k)
   {
      int city;
      scanf("%d", &city);
      int sq = (int) sqrt(city);
      if(sq * sq == city)          
         res[city - 1]++;
   }
   FOR(i, n)
   {
      if(res[i] > 0)
      {
         printf("%d %d\n", i + 1, res[i]);
      }
   }
   return 0;   
}

My problems in Functional Programming Contest - October'14

order_exercises

I am the author of two problems in HackerRank Functional Programming Contest - October'14 and strongly encourage everyone to take part in it.

The first problem is quite easy while the second one is way more challenging, check them out:

Sequence full of colors

Order exercises

I am going to publish editorials to both problems after the contest. Stay tuned.