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.