Monthly Archives: November 2014

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.

My Editorial to TopCoder SRM 638 Div 2

SRM 638 took place in the middle of the night in my time zone, so I didn't participate.

While I haven't read problems from my division (Div 1) yet, I decided to write an editorial for a whole Div 2 problem set.

One interesting thing is that first two problems can be solve very very fast in python, so having an ability to code in python can be a great advantage during live contest.

1000 problem was solved only by 3 users during the contest so I will give you a really simple method to implement it.

250 Problem // NamingConvention

Problem statement

This is really simple. You are given a string consisting of lowercase letters a-z and underscores '_', where underscores divide consecutive words and there is at least one letter between two underscores. The task is to convert the given string into camel case notation, i.e. first word is written in lower case and every other word starts with a capital letter while other letters are lower case.

The full problem statement is available here: http://community.topcoder.com/stat?c=problem_statement&pm=13521&rd=16081

Solution

You can split the string by underscores and capitalize the first letter of each word starting from the second one. Print resulting words one by one. In python this is so simple:

class NamingConvention:
    def toCamelCase(self, variableName):
        s = variableName.split('_')
        return "".join([s[0]] + map(lambda x: x.title(), s[1:]))

The title() method of the class string class is very useful here. The solution has of course linear time complexity.

500 Problem // NarrowPassage2Easy

Problem statement

You are given an array A of size at most 6, where every element is a positive integer not greater than 1000. You are also given a positive integer K not greater than 1000.

The task is to count the number of different orders of A (like permutations, but two elements with same value are considered different) for which there are no elements a_i, a_j such that a_i + a_j > +K and a_j was before a_i in the original array.

The full problem statement is available here: http://community.topcoder.com/stat?c=problem_statement&pm=13295&rd=16081

Solution

Since the array has at most 6 elements, we can consider every possible ordering and for each one check if there is a pair of elements, for which the condition from the problem statement is invalid. If there is no such pair, then we count this ordering as a valid and at the end we return the number of valid orderings. Again python makes it so easy to implement:

class NarrowPassage2Easy:
    def count(self, A, K):
        from itertools import permutations
        cnt = 0
        n = len(A)
        for p in permutations(enumerate(A)):
            fail = 0
            for i in range(n):
                for j in range(i + 1, n):
                    if p[i][0] &gt; p[j][0] and p[i][1] + p[j][1] &gt; K:
                        fail = 1
            if not fail:
                cnt += 1                    
        return cnt

If you haven't heard about enumerate() function this is the time to read about it. Time complexity of this method is O(n^2 \cdot n!) where n is the size of the input array and since n \leq 6 it is enough here.

1000 Problem // CandleTimerEasy

Problem statement

You are given a tree consisting of n nodes. Each edge in the tree has a positive length of at most 1000 units.

You can ignite any subset of leaves in the tree. When a node v is ignited, all edges adjacent to it starts burning, and if the fire meets another node u, it becomes ignited and the process continues. The whole process lasts until all edges are burned.

Edges burn at a uniform rate. This means that if you ignite an edge of length L at one end, it will burn in L units of time, but if you place fire at its both ends, it will burn quicker (for example, if you place it in the same time, it will burn after L/2 units of time).

The tree is burned if all its edges are burned.

The task is count the number of different times in which the tree can be burned completely. These times may differ if you ignite different subsets of leaves at the beginning.

The full problem statement is available here: http://community.topcoder.com/stat?c=problem_statement&pm=13519&rd=16081

Solution

Since n is at most 20 here, we can try to ignite all subsets of leaves and for each one count the time in which the tree will burn completely.

At first I thought about simulating the process of burning, but it can be quite complex to implement, so I developed a solution very easy to code.

Let d[v][u] be the time in which v is ignited when you ignite only uat the beginning. In other words, d[v][u] is a distance between v and u where u is a leaf in the tree. You can compute d table using dfs for example.

Next we iterate over all subset of ignited leaves. I will show how to count the burning time for a given subset S of size k.

Let f[v] be the time when a node v is ignited. We ignite at the beginning all leaves from S. You can thing of this process as of k different fire flames spreading on the tree. Node v will be ignited by one of these flames. Which one? The one which comes to v first and since we have our d table computed, we can compute f[v] = \min\limits_{u \in S} d[v][u].

Now we know f[v] for any node in the tree. Since the tree is burned when all its edges are burned, we iterate over all edges and for each edge (v, u) we find the time after it becomes completely burned based on values f[v] and f[u].

Time complexity of this method is O(2^L \cdot L \cdot n) where L is the number of leaves in the tree and n is the number of all nodes in it.

I attached my C++ code below:

const int MAX_N = 20;
vi g[MAX_N];
int w[MAX_N][MAX_N];
vi leaves;
int fire1[MAX_N];
int fire2[MAX_N][MAX_N];
void dfs(int v, int p, int len, int root)
{
    fire2[v][root] = len;
    FOR(i, SZ(g[v]))
    {
        int u = g[v][i];
        if(u == p) continue;
        dfs(u, v, len + w[v][u], root);
    }
}
class CandleTimerEasy {
    public:
    int differentTime(vector A, vector B, vector len) {
        int n = SZ(A) + 1;
        FOR(i, n) g[i].clear();
        leaves.clear();
        FOR(i, n - 1)
        {
            g[A[i]].pb(B[i]);
            g[B[i]].pb(A[i]);
            w[B[i]][A[i]] = len[i];
            w[A[i]][B[i]] = len[i];
        }
        FOR(i, n) if(SZ(g[i]) == 1) leaves.pb(i);
        set ans;
        FOR(i, n) dfs(i, i, 0, i);
        for(int b = 1; b &lt; (1 &lt;&lt; SZ(leaves)); ++b)
        {
            int k = b;
            int c = 0;            
            vector vs;
            while(k &gt; 0)
            {
                int v = leaves[c];
                if(k &amp; 1) vs.pb(v);
                k /= 2;
                ++c;
            }
            FOR(i, n) fire1[i] = INF;
            FOR(v, n)
            {
                FOR(i, SZ(vs))
                {
                    int r = vs[i];                    
                    REMIN(fire1[v], fire2[v][r]);
                }
            }
            double res = 0;
            FOR(v, n)
            {
                FOR(i, SZ(g[v]))
                {
                    int u = g[v][i];
                    double burned = min(fire1[v], fire1[u]) + w[v][u];
                    int dif = abs(fire1[v] - fire1[u]);
                    REMIN(burned, min(fire1[v], fire1[u]) + dif + (w[v][u] - dif) / 2.0);
                    REMAX(res, burned);
                }
            }
            ans.insert(res); 
        }
        return SZ(ans);
    }
};