Codeforces Beta Round #6 - virtual participation

A. Triangle

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

You are given four sticks with their respective lengths. Your task is to print "TRIANGLE" if it is possible to from a triangle, print "SEGMENT" if it is possible to form a degenerate triangle, otherwise print "IMPOSSIBLE" if it is not possible to form any triangle. Note, you are not allow to break the sticks.

To be able to solve this problem we should be familiar with the triangle inequality. This inequality states that for any given triangle the sums of the lengths of any two sides must be greater or equal to the length of the remaining side. In the case where the length of two sides is equal to the length of the remaining side we have a degenerate triangle. The following image extracting from Wikipedia shows clearly the ideas exposed below:

Once you know this concepts, the implementation of this problem is pretty straightforward, we just need to check from all the possible arrangements of triangles lengths if the triangle inequality holds, otherwise the answer is "IMPOSSIBLE".

B. President's Office

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

You are the president of some company. One day you decided to make an assembly with all the deputies of the company. Unfortunately you don't remember the exact amount of your deputies. But, you still remember that the desk of your deputies are adjacent (share a common side) to your desk. 

Your office room can be view as matrix with \(n\) rows and \(n\) columns. Each desk (including the president desk) is represented by a sequence of unique uppercase letters. Your task is to print the amount of president deputies in the office.

For example, given that \(R\) is the president desk, the deputies are \(B\) and \(T\), the answer is two:

G.B.

.RR.

TTT.

This is a implementation problem, we just need to iterate over the whole matrix looking for the cells which has parts of the president desk, for each one them we check the adjacent cells in the directions {north, west, south, east}, at the same time we keep record of the different letters (deputies desk) seen so far. We should be careful and avoid consider the presidents cells as one of the deputies. The overall time complexity of this solution is \(O(N \cdot M)\).

C. Alice, Bob and Chocolate

http://www.codeforces.com/contest/6/problem/C

Your friends Alice and Bob are playing the following game. They put \(n\) chocolates in a line. Alice starts to eat chocolate bars from left to right, and Bob from right to left. Each chocolate bar takes \(t_{i}\) time to be consumed. Because Bob is a true gentleman if both players start to eat the \(i\)-th bar of chocolate at the same time Bob leave it to Alice. Your task is to return the number of chocolate bars that each player will consume.

A good way to attack a problem is making it simpler than the original problem, imagine that Alice and Bob are playing the game by themselves, how much time they will need to finish the \(i\)-th chocolate?

Let's consider an example with 5 chocolates as follow \(\{2, 9, 8, 2 7\}\):

The following table means that Alice will need 2 seconds to consume the first chocolate, 11 seconds to consume the second one and so on.  

In a similar manner Bob will need 28 seconds to consume the first chocolate, 26 seconds to consume the second one and so on.

From the previous table is pretty easy to spot the pattern Alice is going to be able to consume the \(i\)-th chocolate just in the cases where \(A_{i} \leq B_{i}\), otherwise Bob is going to consumed that chocolate:

Following this steps we can implement a solution with overall time complexity of \(O(n)\).

E. Exposition 

http://www.codeforces.com/contest/6/problem/E

You are organizing an exposition for a famous Berland's writer Berlbury. You are given \(n\) books arranged in chronological order. The \(i\)-th book has a height of \(h_{i}\) millimeters. As organizerd you understand that the difference between the lowest and the highest books in the exposition should be not more than \(k\) millimeters. Your task is to return the following:

1) \(a\) is the maximum amount of books the organizers can include into the exposition.

2) \(b\) the amount of the time periods.

3) \(b\) with the indexes of the first and the last volumes from each of the required time periods of Berlbury's creative work.

The statement of this problem is quite of confusing... All this text can be translated to what is the length of the maximum consecutive sequence of books such that:
$$\\ \underset{i}{\operatorname{arg\,max}} \, (h_{i}) - \underset{i}{\operatorname{arg\,min}} \, (h_{i}) \leqslant k \\ \\ a \leqslant i \leqslant b \\ $$ In other words, we need to find an interval \([a, b]\) that maximize the expression \(b - a + 1\) without violating the constraints that \(argmax(h_{i}) - argmin(h_{i})\) should be less or equal than k millimeters.

To complicate things a even further this problem also ask you to print all the intervals where the previous establish conditions holds.

The solution consist of a combination of the two pointers technique and the STL multiset data structure. Making use of the pointer \(hi\) we tried to extend the sequence one element at a time. With the help of the STL multiset we verified if the minimum and maximum value of the current sequence still holds the condition, if not we remove the element pointed by \(lo\) and keep repeating the process.

Finally, we saved all the the consecutive sequences beginning at the lower pointer \(lo\) which have maximum length and do not violate the constraints.