Monthly Archives: May 2014

TopCoder / SRM 622 div1 250

SRM 622 took place 10 hours ago, but I didn't participate because it was in the middle of the night in Poland. Here's a quick post on the 250 problem.

250 Problem

You're given an integer T and a full weighted directed graph of at most N \leq 50 vertices, where w_{i,j} is the weight of the edge connecting vertex i with vertex j. The task is to count a sum of weights of overloaded edges. An edge e is overloaded if and only if there are at least T pairs of vertices (v, u) such that e lies on any shortest path between v and u. The full problem statement is here SRM 622 div1 250.

The simplest method that came to my mind is to first compute the lengths of shortest paths between all pairs of vertices. Let d_{v, u} denote the distance between v and u. During the contest, the crucial thing here is to use the Floyd-Warshall algorithm rather than for example Dijkstra, not because it's faster, but because it's significantly easier to code.

It remains to decide if an edge e = (v, u) lies on any shortest path between given vertices s and t. Of course we cannot generate all shortest paths from s to t, because the number of such paths can be \Omega(2^n). The most clever method to check it is to observe that:

e = (v, u) lies on any shortest path from s to t if and only if

d_{s, t} = d_{s, v} + w_{v, u} + d_{u, t}

This can be checked in O(1) time because we've just computed distances for all pairs of vertices.

The time complexity of my algorithm is dominated by the cost of doing the above check for the whole graph. For each pair of verices, we iterate over all edges and do a constant time work which results in O(n^4).

Here's my code:

const int MAX_N = 55;

int d[MAX_N][MAX_N];
int cnt[MAX_N][MAX_N];
class BuildingRoutes {
    public:
    int build(vector w, int T) {
        int n = w.size();
        FOR(i, n) FOR(j, n) d[i][j] = w[i][j] - '0';
        FOR(k, n)
        {
            FOR(i, n)
            {                
                FOR(j, n)
                {
                    REMIN(d[i][j], d[i][k] + d[k][j]);
                }
            }
        }
        FOR(s, n)
        {
            FOR(t, n)
            {
                FOR(i, n)
                {
                    FOR(j, n)
                    {
                        if(d[s][t] == d[s][i] + (w[i][j] - '0') + d[j][t]) 
                            cnt[i][j]++;
                    }
                }
            }
        }
        int res = 0;
        FOR(i, n)
        {
            FOR(j, n)
            {
                if(cnt[i][j] >= T) res += w[i][j] - '0';
            }
        }
        return res;
    }
};

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;
    }
};

Hackerrank Weekly / Prime Sum

Hackerrank has recently launched a very nice type of contests. The weekly contest takes place every week and lasts 7 days. Every day a new problem is posted and the difficulty of problems increases each day. The 3rd edition has begun on Monday.

While first two problems were pretty straightforward, Wednesday's problem requires some theoretic background and a little bit of analysis.

Problem


You're given N and K, both positive and less or equal 10^{12}. You have to decide if N can be written as a sum of exactly K prime numbers. In addition, one test file contains at most 5000 testcases, so you have to solve one quite fast.

The full problem statement is here: https://www.hackerrank.com/contests/w3/challenges/prime-sum. I encourage you to solve it.

Solution


The first observation is that if K = 1, then the answer is YES if and only if N is prime. In addition, if N = 1 the answer is NO.

The second observation is that for every N, the maximum valid K is \lfloor N / 2 \rfloor. If N is even, then you can write N as a sum of N / 2 twos. If N is odd, then you can write N as a sum of 3 and (N - 3) / 2 twos. You cannot take a greater K, because the smallest prime is 2.

From now, we can assume that N \geq 2 and 2 \leq K \leq \lfloor N / 2 \rfloor .

The next crucial step is to use the Goldbach's conjecture. It says that every even N > 2 can be written as a sum of exactly 2 prime numbers. While this hasn't been proven yet and remains as one of the oldest and best-known unsolved problems in number theory, it is confirmed for N \leq 4 \cdot 10^{17} by a distributed computer program.

We can use that fact to solve the problem.

If N is even, let's write it as a sum of N / 2 twos. We can take any 2 \leq m \leq N / 2 of these twos and replace them by two primes because m \cdot 2 is even and because of the conjecture, so the answer is YES.

If N is odd, let's write it as a sum of 3 and (N - 3) / 2 twos. We can take any 2 \leq m \leq (N - 3) / 2 twos and replace them by two primes using the same rule as above. It follows that the answer is YES for 3 \leq K \leq N / 2. But what if K = 2 ? We know then, that one of the primes has to be 2 because we cannot have two odd primes, so the answer is YES if and only if N - 2 is prime.

The last remaining thing is how to decide fast if N is prime. Since N \leq 10^{12} a standard sieve or trying to divide N by numbers less or equal \sqrt N is too slow. We can use Miller–Rabin primality test.

It is a randomized algorithm in general, but since N \leq 10^{12} we can make it deterministic.

I really like that problem.

First Post / Top Coder Open 2014 Round 2A

Hi everyone! First things first, a short introduction.

I challenged myself to become RED on topcoder and to have a high rating on codeforces, codechef and maybe more. I'm going to post solutions to problems and I want to improve my skills everyday.

TCO 2014 Round 2A


Couple weeks ago I advanced to TCO 2014 Round 2. Match A from that round took place on May 17th. Only top 50 from each of 3 matches in Round 2 advances to the next Round.

I finished 431th, solving 250 problem in 30 minutes (should've done that much faster) and earned 124 rating points, which is quite surprising. 

250 Problem


The 250 Problem Statement is pretty clear.

You have a 4x4 grid consisting of 16 1x1 spots and 16 three dimensional blocks each of size 1 x 1 x h[i], where h[i] is the height of i-th block.

You have to assign an unique spot for each block in a way which maximize a visible surface formed by the blocks - we don't take the bottom sides of the blocks into account, because the grid lays on the table. The task is to return this maximum visible surface.

Since there are only 16 blocks, I thought that something like a brute force would work and the first idea that came to my mind is the following:

  1. Sort blocks by height in non-decreasing order.
  2. Put 8 blocks with greatest heights in spots marked red in the drawing below. We can do that, because within these blocks, there is no block which covers any part of any other top 8 bricks.
  3. Since there are only 8 blocks remaining to put, we can try every permutation of these, because 8! = 40320
  4. For each such permutation, we have to compute the visible surface and check if it's greater that maximum computed so far.


The total complexity of that method is less than 10^7 so we can afford that.


My solution from the contest is so messed up that I decided to write a better structured version:

int di[] = {-1, 0, 1, 0};
int dj[] = {0, 1, 0, -1};
int order1[] = {1, 3, 4, 6, 9, 11, 12, 14}; 
int order2[] = {0, 2, 5, 7, 8, 10, 13, 15}; 

class SixteenBricks {
public:
    int sol[16];
    vector<int> h;
    int init;
    int res;
    bool visited[8];

    void solve(int cnt)
    {
        if(cnt == 8)
        {            
            int ans = init;
            FOR(i, 4)
            {
                FOR(j, 4)
                {
                    FOR(z, 4)
                    {
                        int ni = i + di[z];
                        int nj = j + dj[z];
                        if(ni >= 0 && ni < 4 && nj >= 0 && nj < 4)
                        {
                            int l = 4 * ni + nj;
                            ans -= min(sol[4 * i + j], sol[l]);
                        }
                    }
                }
            }
            REMAX(res, ans);
        } 
        else
        {
            FOR(i, 8)
            {
                if(!visited[i])
                {
                    visited[i] = 1;
                    sol[order2[cnt]] = h[i];
                    solve(cnt + 1);
                    visited[i] = 0;
                }
            }
        }
    }
    int maximumSurface(vector<int> height) {
        h = height;
        sort(ALL(h));
        FOR(i, 8)
        {
            sol[order1[i]] = h[8 + i];
        }
        FOR(i, 16)
        {
            init += 4 * h[i] + 1;
        }
        FOR(i, 8)
        {
            visited[i] = 1;
            sol[order2[0]] = h[i];
            solve(1);
            visited[i] = 0;
        }
        return res;
    }
};


During the challenge phase, I saw that there are a way clearer solutions, I'll try to think about it later.


500 Problem


I had enough time for 500 problem, but I couldn't come up with any efficient solution.