Tag Archives: Sorting

Hacckerrank Weekly #4 // problems 1-3

Palindrome Index

The first problem was posted on Monday. The statement says that you're give a string s of n \leq 10^5 letters. The task is to find the index of a letter in the string such that after removing that letter s is a palindrome. It's guaranteed that such an index exists. One test file consists of at most 20 test cases.

Solution

There are two cases. The string s can be already a palindrome or not.

It's easy to check, that if s is already a palindrome, then after removing the n / 2-th letter, s remains a palindrome.

If s is not a palindrome, then there exists an index i such that s_i \neq s_{n - 1 - i}. Let k be the smallest such index.

Again, it's easy to see that we have to remove either s_{k} or s_{n - 1 - k}, because after removing any s_j for k < j < n - 1 - k, s_{k} will be compared with the same letter that it was compared in the original s and the result of that comparison is still negative. In addition, it makes no sense to remove any a_j for j < k or j > n - 1 - k because with that action we won't achieve anything positive.

Let:

a := s without s_{k}

b := s without the s_{n - 1 - k}

From the problem statement, we know that at least one of a and b is a palindrome. If a is a palindrome, then the result is k. In the other case, the result is n - 1 - k.

The time complexity of that solution is O(n).

 

Algorithmic Crush

In Tuesday problem, you're given an array c[1..n], where n \leq 10^7. Initially c_i := 0 for each i.

Next, there are m \leq 2 \cdot 10^5 queries. Each query consists of 3 integers a, b, k, and it adds k to every c_i where a \leq i \leq b. Your task is to return the maximal value in the array after performing these m operations. The full problem statement is here.

Solution

At the first sight it seems like a segment tree problem, but it would be an overkill here. The crucial thing there is that we only have to compute a maximal value once, so we can first "perform" all queries and then calculate the result. The next simple observation is that we can only consider elements c_i for which there is at least one query where a or b equals i. That observation led us to a solution based on sorting.

Let's thing of each query as of two event. Each event has it's own index and value. For the query <a, b, k> the first event is to add a value k to the index a and the second event is to subtract a value k from the index b. After that, we can sort these events. We say that event1 < event2 iff. the index of event1 is less than the index of event2 or these indices are equal and event1 is the opening event i.e. it adds a value. Next we can process all the events from left to right keeping track of the current value and the maximum value. We update the maximum value if the current value is greater than the maximum value collected so far.

The total time complexity of that method is O(m \cdot \log m) and it's worth to mention, that it doesn't depend on n at all.

Lucy and Flowers

Wednesday problem is more difficult, but not so much :) While the original problem statement has some story behind it, the real task is the following:

You're given n \leq 5000 distinct integers. The task is to count how many distinct Binary Search Trees (BST) can be created by picking any non-empty subset of these integers. Because the result can be very large, you have to compute it modulo 10^9 + 9, but in order to provide a clear solution I'll omit that. There are at most 5000 testcases in one test file.

Solution

There are two crucial observations. If you pick two different subsets, the trees created from these subsets are different. On the other hand, if you pick two subsets with the same number of elements, the number of different trees created from each subset is the same, because only ranks of elements matter, not their relative values.

Let dp[k] be the number of different BST that can be created from k integers and assume that we can compute that value.

Then using two above facts, the result can be computed as:

\sum\limits_{k = 1}^n = \binom {n} {k} \cdot dp[k]

because we can compute the number of different BST for each subset separately and that number is the same for subsets of the same size.

But how to compute dp[n] for any n?

If we have n elements, we can put any of them in the root of a tree. If we put the k-th smallest of them, k - 1 smallest elements have to be in the left subtree of the root and n - k largest elements have to be in the right subtree. The number of possible different BST as a left subtree is dp[k - 1] and it's dp[n - k] for the right subtree. This led us to the recursive formula:

dp[n] = \sum\limits_{k = 1}^{n} dp[k - 1] \cdot dp[n - k]

The base case is:

dp[0] = 1

because there is only one empty BST.

In the full solution, we precompute dp table and binomial coefficients \binom {n} {k}. These two precomputations take O(n^2) time. After that, we can compute every testcase in O(n) time which gives O(n^2 + t \cdot n) time, where t is the number of testcases.

 

TopCoder / SRM 621 Div1 250

During SRM 621 I solved only 250 problem, but after the contest I figured out the solution to 500 which I'm going to write about in the next post. Now let's focus on 250 problem.

250 Problem

You're given a N \leq 100 circles on the plane and the integer 1 \leq Z \leq 10^9. The i-th circle has a center in (x_i, y_i) and a radius r_i, where x_i, y_i \in [-10^9, 10^9] and 1 \leq r_i \leq 10^9. A special circle has to be placed with a center in (0, 0) and a radius R chosen uniformly at random from an interval [0, Z]. We say that the special circle is good when there is no other circle which intersects with the special circle, in other words all points lying within any regular circle has to be either inside or outside the special circle. Your task is to compute the probability that the special circle is good. Let's consider an example input:

 

circles1

 

A very basic but a crucial observation is that for any regular circle it doesn't matter what's the relative position of that circle. Only the radius and the distance from it's center to (0, 0) matter. So we can transform the problem from 3D to 2D which is always good.

Let d_i be the distance from the center of the i-th circle to (0, 0). Then the i-th circle corresponds to a segment [d_i - r_i, d_i + r_i] and choosing R corresponds to choosing a point from [0, Z]. The above example corresponds to the following picture:

 

circles2

 

For a given Z, we're interested in segments in R which lies in any [a, b] where 0 \leq a \leq b \leq Z and [a, b] doesn't intersect with any regular circle. For our example, the good segments are marked green in the following picture:

 

circles3

 

Now, it's easy to see that the probability we're looking for equals 1 - X / Z, where X is the length of a sum of segments corresponding to the regular circles limited to [0, Z]. We can compute X easily by sorting the segments and then process these segments one by one and count the amount of space where at least one segment is open. If you're interested, I'm putting my code below:

double dist(int x, int y)
{
    return sqrt(pow(x, 2) + pow(y, 2));
}

class RadioRange {
    public:
    double RadiusProbability(vector X, vector Y, vector R, int Z) {
        vector > v;
        FOR(i, X.size())
        {
            double d = dist(X[i], Y[i]);
            v.pb(mp(max(d - R[i], 0.0), 0));
            v.pb(mp(d + R[i], 1));
        }
        sort(ALL(v));
        int open = 0;
        double checkpoint = 0.0;
        double res = 0.0;
        FOR(i, v.size())
        {
            double d = v[i].fi;
            if(d > Z) break;
            if(v[i].se == 0)
            {
                if(open == 0)
                {
                    checkpoint = d;
                }
                open++;
            }
            else
            {
                open--;
                if(open == 0)
                {
                    res += d - checkpoint;
                }
            }
        }
        if(open > 0)
        {
            res += Z - checkpoint;
        }
        return 1 - res / Z;
    }
};