# 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 $u$at 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); } };

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