TopCoder SRM 556

DIV 2 250 - ChocolateBar

http://community.topcoder.com/stat?c=problem_statement&pm=12190

You just bought a chocolate bar, each square of the chocolate bar contains a letter in the range 'a' - 'z'. You decide to give this whole chocolate bar to your friend, but he is a really picky guy... he just like chocolate bars that do not contain repeated letters. You are able to cut 0 or more bars from the beginning and the end of your chocolate bar.

You are asked to return the maximum possible length of the chocolate bar that you can share with your friend.

First we are going to explain the naive solution, because the maximum length of the chocolate bar is at most 50, we can simply iterate over all the chocolate bars beginning at index \(i\) and ending at index \(j\), where \(j \geqslant i\). For each of this chocolate bars we can store the frequency of the letters seen so far, if one of the letter frequency is greater or equal than 2, we should not consider this chocolate bar, otherwise, we  calculate the length of the chocolate bar partition which is \(j - i + 1\) and stay with the maximum length as the result. The overall time complexity of this solution is \(O(n^{3})\).

After the contest I was thinking hmmm can we do better? the answer is yes. 

The idea is the following, the new algorithm keep two pointers \(lo\) and \(hi\) the first one represent the beginning of the sequence and the later one the ending. In order to guarantee the correctness of the results, at each step we should maintain the following invariant: "the frequency of the characters between \(lo\) and \(hi\) is less or equal to 1".

Given this, at each step we try to extend our current sequence one element more if the new sequence violate the invariant, we increase the pointer \(lo\) until the invariant holds again, otherwise, continue with the next element of the sequence. Simultaneously, we keep track of the maximum length partition that maintain the invariant, we can easily calculate this with the formula \(hi - lo + 1\). The overall time complexity of this solution is \(O(n + n)\).

DIV 2 500 - XorTravelingSalesman 

http://community.topcoder.com/stat?c=problem_statement&pm=12175

You are a very particular traveling salesman, every time you move to a new city your current profit is calculate as \(P \, \mathrm{XOR}\, V_{i}\) where \(V_{i}\) is the profit cost associated with the \(i\)-th city. You are allowed to move to the same city more that one time. Return the maximal profit that you can achieve.

The main idea to solve this problem is to notice that there is not so many states to consider, we are given maximum 50 cities and each of the V_i cost  do not exceeds 1,023, which give us a total of 51,150 possible states. We can simply iterate over those states using dfs and keep the maximum profit among them. 

UVA 10227 - Forests

http://uva.onlinejudge.org/external/102/10227.html

If a tree falls in the forest, and there's nobody there to hear, does it make a sound?

A forest contains \(N\) trees and \(P\) persons. Each person has an opinion about a set of trees they heard fall. Your task is print the number of different opinions among the \(P\) persons.

Let's first try to get some intuition about the situation that we are dealing with:

As we can see in the previous image person #1 and #3 has the same opinion, they heard tress \(\{2, 3\}\) fall. In the case of person #2 he heard the trees \(\{2, 4\}\) falls, this give us a total of 2 different opinions, \(\{2,3\}\) and \(\{2,4\}\).

The key observation to solve this problem is to notice that the persons are divided into connected components according to the set of trees they heard fall. For the previous example we have two connected components:

Once again we are going to need the Disjoint Sets data structure to solve this problem. Initially each person has his own opinion, for each pair of people we check if they shared the same opinion with somebody else in the group, if they do we used the operation \(union\_set(x,y)\) to merged this two persons into a connected component, otherwise, continue with the next person. Our answer is the number of connected components after all the \(union\_set(x,y)\) operations.

Finally, something important to remember is that for this problem "having no opinion also counts as having an opinion". Which means that persons that do not heard any trees fall, they should be group together also in one group.

UVA 10178 - Count the Faces

http://uva.onlinejudge.org/external/101/10178.html

You are given a planar graph. A planar graph is one that can be drawn on a plane in such a way that there are no “edge crossings,” i.e. edges intersects only at their common vertices. Your task is to print the number of faces in that graph.

For example the following graph has 6 faces:

To solve this problem the first thing that we need to do is understand about the faces and how these are created. To simplify things let's forget about the outer face (face #6) and focus in the others. It is not hard to see that the rest of the faces are enclosed regions of 3 or more points, in other words there are cycles. This implies that the problem of counting the cycles in an undirected planar graph is analogous to the number of faces in the graph, with the only exception that we should not use an edge more than one time.

To count the cycles in an undirected planar graph we are going to use the Disjoint Sets data structure.

In order to better illustrate this ideas let's take a look to an example:

 


Imagined that we are using the operation \(union\_set(x,y)\) for all the edges in the previous graph. Let's assume that we connect the edges in the following order \((A, B)\) - \((B, D)\) - \((D, C)\) - \((C, A)\) - \((C, E)\) - \((E, G)\) - \((G, A)\). A green edge represent a connection between two nodes were each of the nodes belong to a different connected component. In those cases we do not have a cycle. A red edge or cycle appear just in the cases were we connect two nodes that already belongs to the same component. In those cases we should increment the faces counter. Note that this idea also works where you have more than one connected component in the graph.

Once we are done with all the edges our answer is the number of cycles founded in the graph plus one. Discussing this problem with my friend cjoa2 he told me that the mathematician Leonhard Euler discover a formula to calculate the number of faces in a planar graph.
$$\\ v - e + f = 2 \\ f = 2 + e - v$$ Were v and e represent the total count of vertices and edges in the graph. For example given the previous graph we have the following:
$$\\ v = 8 ,\;\; e = 12 \\ f = 2 + 12 - 8 \\ f = 6$$ There is just a little issue in the case that we have different connected components if we applied the formula for each component we are going to end up over counting the number of outer faces. Let's see an example that illustrate this problem:

If we calculate formula for each component and add up the results we get that the total number of faces in the those planar graphs is 4, which is clearly incorrect... the correct answer should be 3:

To be able to solve this issue we are going to calculate the number of faces in each component with the following formula:
$$\\ f = 1 + e - v$$ Once we sum the result of each component, we add one to our final answer, corresponding to the outer face of all the connected components.

Finally, To implement this idea we use a depth first search method that give us the total amount of vertices and edges in each connected component and used the previous explained formula.

Codeforces Round #133 - upsolving

A. Tiling with Hexagons

http://www.codeforces.com/contest/216/problem/A

You are given three positive integers \(a\), \(b\) and \(c\) \((2 \leq a, b, c \leq 1000)\). The integers \(a\), \(b\), \(c\), \(a\), \(b\) and \(c\) form a six side hexagonal shape. The hexagonal shape is tiled with hexagonal tiles. Your task is to print the total number of tiles in the hexagonal shape.
 

Let's first consider the case where \(a = 2\), \(b = 3\) and \(c = 4\). Because this kind of "weird" hexagonal figures are counter-intuitive we are going to transform the previous figure into better known one, a rectangle:

Given this example is pretty easy to guess an answer, we just multiply the base x height and subtract the total amount of red hexagonal tiles and we are done. But hold on a second, there are two things we are missing... first, what is the length of the base and the height, and also how to calculate the total amount of red hexagonal tiles.

Let's analyze two more examples to see if we can spot the pattern, now consider the case when \(a = 3\), \(b = 3\), \(c = 4\) and \(a = 4\), \(b = 3\), \(c = 4\):

Now we are getting somewhere... if you look carefully the base of the new rectangle is equal to the expression \(c + a - 1\) and the height is equal to the expression \(b + a - 1\). The red tiles as we can see are triangular numbers, to be precise the \(T_{a-1}\) where \(T_{i}\) denotes the \(i\)-th triangular number, and because we have two of those we subtract \(2 * T_{a-1}\) to get the answer. So let's denote \(h(a,b,c)\) as the total amount of hexagonal tiles, we got the following expression:

$$\\ h(a,b,c) = (c + a - 1)(b + a - 1) - 2T_{a-1} \\ \\ h(a,b,c) = (c + a - 1)(b + a - 1) - 2(\frac{a(a-1)}{2}) \\ \\ h(a,b,c) = (c + a - 1)(b + a - 1) - a(a-1)$$

B. Forming Teams

http://www.codeforces.com/contest/216/problem/B

You are given \(N\) people and their relationship, you want to form two teams with equal number of members. Unfortunately some people are archenemies, because you don't want bad chemistry in any of the teams you decided not to form a team which has  archenemies on it. To be able to accomplish this task you may have to left out some people. Your task is to print the minimum amount of people that you have to left out to form a team in the described manner.

Well something that as a mathematician, programmer or whatever you consider yourself should always remember is "you do not need to do exactly what the problem is telling you to solve it", This may sound pretty obvious but sometimes is pretty hard to know when to follow this principle. In this case, we do not need to form the teams to know how many people are left out. Instead we are going to tried to came with the solution by spotting the archenemies relationship in a graph.

Let's imagine that the color blue represent the first team and red the second one.  The following graph shows a possible team distribution of four people:

Because person #1 and person #2 are archenemies the best that we can do is to assigned them to different teams, in a similar manner the same applies for the pairs \((2, 3)\) and \((3, 4)\).

Problems arise when we attempt to join members that form a chain (cycle):

No matter how we assigned the people in the two teams we need to left out one person (in this case the person #3 marked in grey) to make thinks workout. At this point we may feel tempted to conjecture that the same applied for all the cycles. Unfortunately that is wrong, an easy counter-example is the following case:

Looking carefully to the previous graphs is easy to spot the pattern, every time we find an odd cycle at least one person should be left out. In case that you still doubt the previous statements let's also include a five people cycle example:

Let's recall that the problem statement establish that one person can not have more than two archenemies. So we are going to have graphs like the previous discussed.

To get our answer we should count the total number of odd cycles, let's call it \(C\), if \(N - C\) is odd we should left out another person, this is because the number of persons in each team should be strictly equal, in other words divisible by two.

Finally, to implement the solution I used the Disjoint Set data structure. The idea is the following, We first iterate over all the edges of archenemies, for each of them we tried to connected them, if we fail means that there were previously merged, which means we found a cycle, and we should increment the number of left out persons, otherwise, add another node to some connected component and continue the same process.

ABBYY Cup 2.0 - Easy - virtual participation

A2. Good Matrix Elements

http://www.codeforces.com/contest/177/problem/A2

You are given a \(N\) x \(N\) matrix, where \(N\) is an odd number. A good element of the matrix is defined as follow:

(1) Element of the main diagonal.
(2) Element of the secondary diagonal.
(3) Element of the "middle" row (\(\frac{n}{2}\) row).
(4) Element of the "middle" column (\(\frac{n}{2}\) column).

Your task is to count the number of good elements in the matrix.

The solution of this problem is pretty straightforward, we just need to add up the elements which has one or more of the following properties:

B2. Rectangular Game

http://www.codeforces.com/contest/177/problem/B2

You are playing the following game, initially you have \(n\) pebbles, at each step you arranges them in such way that each row has the same amount of pebbles. Once you have arranges the pebbles, you take back any of the resulting rows (that is, b pebbles) and discards all other pebbles. Keep playing until you end up with exactly one pebble. Your task is to print the maximum possible result of the game.

The first thing to note here is that if you want to distribute certain number \(n\) into \(a\) rows with \(b\) pebbles each, then necessarily \(a | n\) and \(b | n\). Clearly, we going to be dealing with divisors of \(n\) in this problem.

Based on the previous claim the main idea of this problem is keep dividing the number of \(n\) until we reach some point we cannot do it anymore. This reasoning lead us to the question of how to divide in order to maximize the final result.

Le'ts look an example with the number 6, the asterisk represent the pebbles :

The divisors of the number 6 are \(\{1, 2, 3, 6\}\), we can distribute the pebble in four possible ways:

(1) one row of six pebbles  

\(6 / 1 = 6\)

******

(2) two rows of three pebbles  

\(6 / 2 = 3\)

***

*** 

(3) three row of two pebbles  

\(6 / 3 = 2 \)

**

**

**

(4) six rows of one pebble

\(6 / 6 = 1\)

*

*

*

*

*

* 

Looking at this example it seems obvious that we should take the lowest available divisor greater than one at each step. 

To implement this idea we simply iterate over all the factors of \(n\), and for each one of them add up \(\frac{n}{d}\) to the solution. The overall time complexity of this solution is \(O(\sqrt{n})\).

C2. Party

http://www.codeforces.com/contest/177/problem/C2

You are organizing a party, from all of your acquaintances some of them are friends and some of them dislike each other. To make the party a success you came up with the idea of only inviting people that share a friendship relationship. Given the relationship between the acquaintances, your task is to return the maximum number of people that you can invite to the party.

This is a typical graph connectivity problem, it can be solved with DFS, BFS or Disjoint Sets. I solved using Disjoint Set data structure.

The Disjoint Set data structure helps us to divide each of the acquaintances in groups according to their direct or indirect friendship relationship. Initially every person belongs to its own group, using the \(union\_set(u, v)\) operation we unite the people who share a relationship of mutual friendship in a common group. We keep track of the number of people in each of the groups. 

The final step is to check which of those groups has people that dislike each other. Having the Disjoint Set this is a straightforward task, for each pair of people that dislike each other let's called it \((u,v)\) we check if \(find\_set(u) = find\_set(v)\). This means that, if the pair \((u,v)\) belongs to the same group we can not invite any of the people in that group.