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.

Codeforces Beta Round #4 - virtual participation

A. Watermelon

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

You and a friend want to divide a Watermelon with \(N\) kilos in two pieces. Because you and your buddy are crazy about even numbers, the division should be made in such way that the weighs of each part of the fruit have a  even number of kilos. Your task is to print "YES" if the division is possible, otherwise "NO".

The solution of this problem is pretty straightforward let's first consider the case where the given number \(N\) is odd. This means that \(N\) can be expressed in the form \(2x + 1\) for some integer \(x\). Is not hard to see that is not possible to split the number in two even parts when \(N\) is odd, because, the remainder of one is going to end up changing one of the Watermelon half weighs into an odd amount. 

We can conjecture then that this split is possible only when \(N\) is even, but hold on a second, how about the case \(N = 2\), is clearly not possible and is an even number... Is this the only exception out there? the answer is yes. Any other even integer greater than 2 can be expressed in the form \(2x + 2y\) where \(x\) and \(y\) are integers greater or equal than one. Knowing this we can conclude that our answer are all the even numbers greater or equal to 4. The overall time complexity of this solution is \(O(1)\).

B. Before an Exam

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

You are are planning on taking a Biology exam. Your parents knows that you hate the subject so they made you study for \(d\) days not less than \(minTime_{i}\) and not more than \(maxTime_{i}\) hours per each \(i\)-th day. Your parents now are asking you the time table of your study sessions, unfortunately, you just wrote down the total sum of time let's called it \(sumTime\). Your task is to print the time table according to your parents constraints, in addition, the total sum of time in each day should be equal to \(sumTime\). If is impossible to build such schedule print "NO".

The strategy to solve this problem is greedy. The first thing to notice is that at each day we should have a least  \(minTime_{i}\) hours, otherwise, our parents constraints will not be satisfied. Once we assign  \(minTime_{i}\) to each day, if the remaining \(sumTime\) is less than zero means that there is not enough time for the given constraints so the answer is "NO". 

The next step is to assign the remaining \(sumTime\) to each \(i\)-th day, taking care that the \(i\)-th day cannot have more than \(maxTime_{i}\) hours. After all of the assignments if the remaining \(sumTime\)  is greater than zero means that there is to much time to be fitted on the current schedule so the answer in this case is also "NO".

Finally, if any of the previous conditions does not hold means we got a solution. We just print any valid schedule. The overall time complexity of this solution is \(O(d)\).

C. Registration system

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

The administrator of some random website ask for your help to implement a prototype of a new registration system. The system work as follow, when a user register if the username does not exist in the database the system prints "OK", otherwise the system prints usernamei in the following way (username1, username2, ... ) for each registration repetition  using the same username.

This problem shows the importance of a good data-structure in algorithm design. The idea here is to have a map<string,int> which maintains a counter for each name in the database. Every time a name is repeated we just print the name with the current value of our counter. The overall time complexity of this solution is \(O(N logN)\) assuming that each query to our map takes \(logN\) time.

D. Mysterious Present

http://www.codeforces.com/contest/4/problem/D

You want to send a letter to a good friend. Because you are the mysterious type of person you decide to make a chain of envelopes and put the card into them. This chains of envelopes should hold the following condition the width and the height of the \(i\)-th envelope is strictly higher than the width and the height of the \((i-1)\)-th envelope. Given the width and height of the letter and all the envelopes print the maximum chain size of envelopes you can form.

The strategy to solve this problem is Dynamic Programming. To simplify our solution we first discard all the envelopes which our letter can not fit in. Is easy to see that those one would not contribute to the final solution

The DP state of the solution consist in maintain the maximum length of the chain that ends in the index \(i\)-th. We also keep record of the parent of each member of the chain, in that way at the end we can reconstruct the optimal solution. The overall time complexity of this solution is \(O(n^{2})\).

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.

UVA 12416 - Excessive Space Remover

http://uva.onlinejudge.org/external/124/12416.html

You are editing a text in a simple editor like notepad, you start to wondering how to remove all the consecutive spaces from your document. After a while, you came with the idea of repeatedly "replace all" two consecutive spaces with one space (let's call this an action). Facing this issues makes you thing even further, now you want to know the number of actions required to remove all the consecutive spaces from your document.

The first observation to solve this problem is that for all the regions with consecutive spaces we just care about the one with higher number of consecutive spaces. The following example shows a string were the highest number of  consecutive spaces is 4:

A*very**big****joke.

Is not hard to see that the other regions need less or equal number of actions to complete (because the the actions are parallel in each region). Which means we just need to focus in the amount of spaces of the region with more consecutive spaces.

Now let's get our hands dirty with an example, let's call \(N\) the maximum number of consecutive spaces in certain region of our document.

Note that the number of actions increase every time we exceed a power of 2. Once we know this code the solution is straightforward, first we iterate the whole string and get the value of the region with more consecutive spaces, let's called it \(b\), after that, we increment a variable \(i\) until \(2^{i} < b\) holds.

UVA 10943 - How do you add?

http://uva.onlinejudge.org/external/109/10943.html

You and a friend Ryan are stuck in a deserted island. Ryan suggested the following problem, given a number \(N\), how many ways can \(K\) numbers less or equal than \(N\) add up to \(N\)?

For example for \(N = 5\) and \(K = 2\), there are 6 ways:

\(5 + 0\)

\(4 + 1\)

\(3 + 2\)

\(2 + 3\)

\(1 + 4\)

\(0 + 5\)

This problem has the same solution that UVA 10910 - Marks Distribution. The only difference is that in Marks Distribution the author tried to make the problem a little bit more complicated by adding constraints.

We can solve this problem using Dynamic Programming. A good way to look at this problem is imagined that for each \(K\) we have an empty box to be filled. to fill each one of the boxes we have \(N\) objects, based on this analogy, we can further extend our ideas to the state of the solution.

The DP state is the following:

\(n\) - number of objects

\(k\) - current box

\(rec(n, k)\) = number of ways of adding up \(K\) numbers and get \(N\) as the result. Finally, using this state we recursively calculate all the possible ways of filling the boxes in the following way, where \(0 \leq i \leq n\) we have that \(rec(n - i, k - 1)\). This means, take \(i\) objects of the remaining \(n\) objects and after that go to the next box \((k - 1)\).

The overall time complexity of this solution is \(O(N \cdot K)\).

Bottom-up dynamic programming solution:

UVA 11420 - Chest of Drawers

http://uva.onlinejudge.org/external/114/11420.html

You are given a chest of drawers as shown in the picture below:

Let \(N\) be defined as the total number of drawers in the wardrobe , your job is to count in how many ways you can secured exactly \(S\) drawers, a drawer is secured if the \(i\) and the \(i - 1\) are locked.

Once again we are facing a situation were a naive algorithm is going to timeout. Don't panic, Dynamic Programming to the rescue... 

The state of the DP solution is the following:

\(n\) -  current drawer

\(s\) -  count of secured drawers

\(p\) - previous drawer state (locked or unlocked)

\(rec(n, s, p)\) = total number of configurations with exactly S drawers secured

The recursion part of the solution has only two possible choices at each step, we locked the current drawer or not, depending if the previous one was locked we add one to the count of secured drawers (\(s\)) otherwise the count remain the same. 

Finally, the base case just consider the cases where the count of secured drawers is equal to \(S\).

UVA 11654 - Arithmetic Subsequence

http://uva.onlinejudge.org/external/116/11654.html

You are given a set of given a set of integers, determine how many proper subsets of this set form an arithmetic sequence. 

For those that forgot what is an arithmetic sequence (or arithmetic progression), is a sequence such that the difference between successive elements is constant. For example, \(\{2, 4, 8, 10\}\) is an arithmetic sequence where the constant different of each element is two.

It is always a good idea to verify if the brute force solution (if any) runs under the time limit. The idea behind the brute force approach is to generated all possible subsequence of the given set, and check whether or not is an arithmetic sequence. Is not hard to see, that the constraints are way to high for this solution, \(N\) can reach up to 250, which means that we can have \(2^{250}\) subsets, in other words not possible under the 5 seconds time constraint.  

To solve this problem we need to do reduced from exponential time complexity to linear, this is when Dynamic Programming comes into play. 

First let's make some observations about the arithmetic sequences. It is always possible to create all the size one and two subsequences for any given set. This means, the answer is always at least \(\frac{N + N(N-1)}{2}\). Knowing this, the idea behind the DP solution is to first pick some sequence of two elements which ends points are the index \(i\) and \(j\). After we do this, we tried to extend this subsequence checking if there is any subsequence ending at index \(k\) that we can connect with our current one. In order to be able to connect a subsequence with another one the difference between their successive elements must be equal, as the definition of arithmetic sequence establish.

The overall time complexity of this solution is \(O(N^{3})\).

UVA 11000 - Bee

http://uva.onlinejudge.org/external/110/11000.html

You are given one a very special African female bee. This bees has really interesting reproduction system. The female bees can give birth to a male bee. The male bees can give birth to one male bee and one female bee. Assuming that the bees are immortal, return the number of male bees and the overall total of bees after \(N\) years.

Is hard to think in something different from Fibonacci numbers when you heard something related with populations and growth. Let's get our hand dirty and make a diagram of what is happening:

Looking at this graph is easy to conjecture a recursion for both the males bees and the females bees. Where \(f(n)\) represent the numbers of females bees in the \(n\)-th year and \(m(n)\) represent the number of male bees in the \(n\)-th year:

$$\\ f(n) = f(n-1) + f(n-2) \\ m(n) = m(n-1) + m(n-2) + 1$$

In order to be able to answer the query's in \(O(1)\) time, we first pre-calculate all the values of both functions in two arrays.

UVA 10910 - Marks Distribution

http://uva.onlinejudge.org/external/109/10910.html

You are a student that has taken a total of N subjects. In order to pass a certain subject, you need a least \(P\) marks of grade. You got a total of \(T\) marks among all your examinations. Your task is to print how many different ways you can distributed those marks among the N subjects in such way you pass all of them.

This problem can be solve with Dynamic Programming. The first thing to note is that we don't need to bother with distributions of grades were one or more grades are less than \(P\). In other words, we can assume that all the subjects start with \(P\) marks. Knowing this we just need to care in how to distributed the remaining \(T - N \cdot P\) marks left. To calculate this we are going to use top-down Dynamic Programming also known as memoization. 

The state of the DP state is simple: (current subject, remaining marks) = total number of configurations. For each subject  recursively we tried all the possible assignments of marks. Because we are counting different configurations the base case return the number 1. We use the variable res to add up all the valid configurations founded by the recursion function.

Codeforces Round #128 - fun match

This match was quite easy compared with the previous one, I particularly found problem C the easiest problem in the match, problem A had a tricky case that cause a lot of re-submits. Problem B was not impossible but need some insight about how to represent the data.

A. Two Problems

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

A friend of yours told you that he got x points in a programming contest. Because you do not believe him you decide to verify his score. 

The contest time is of t minutes. There are only two problems in the contest from which your friend can solve any of them. The first problem had an intial cost of \(a\) points and every minute the cost reduced \(d_{a}\) points. In the same way, the second problem had a initial cost of \(b\) points and every minute the cost reduced \(d_{b}\) points.

Print "YES" if your friend could have earned \(x\) points in the contest otherwise print "NO".

The solution to this problem is brute force. There are four possibles cases we need to consider:

(1) Our friend did not solve any problem.

In the case were \(x = 0\) the answer is "YES". Is always possible that our friend was not able to solve any of the problems in the contest. A lot of people (including myself) miss this case during the competition.

(2) Our friend solved the first problem.

Iterate over all the possible penalty times between \(0 \leq t_{i} < t\) if \(x = a - t_{i} \cdot d_{a}\) print "YES".

(3)  Our friend solved the second problem.

Analogous to the previous case, iterate over all the possible penalty times between \(0 \leq t_{i} < t\) if \(x = b - t_{i} \cdot d_{b}\) print "YES".

(4) Our friend solved both problems.Iterate over all possible combinations of \(t_{i}\) and \(t_{j}\). Where \(0 \leq t_{i} < t\) and \(0 \leq t_{j} < t\), if \(x = a + b - t_{i} \cdot d_{a} - t_{j} \cdot d_{b}\) print "YES"

The overall time complexity of this solution is \(O(t^{2})\).

B. Game on Paper

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

You are given a \(n\) x \(n\) board. Initially all the cells of the square are white. In each turn you paint a cell black. You task is to return the minimum amount of turns that you need to have a 3 x 3 black square. If no such move exists, print -1.

Because \(n\) is at most 1000, we can easily construct a \(n\) x \(n\) matrix within the memory limits. This matrix is going to keep record of the turn when certain cell was paint for the first time. For convenience unmarked cells are going to be marked as +\(\infty\). Let's consider the first sample case, the propose data-structure should look like this:

Once we have this, the next step is to check all possible 3 x 3 squares. For each value \(A[i][j]\) of the square, we keep record of the highest turn. 

Why? because this is the last cell painted in that black square. There is one detail left to cover, how about if we check a square that did not have all the cells painted in black. Because we initialized everything to +\(\infty\) that square will end up having infinity as the highest turn and is not going to be consider as a solution. The last step is iterate over all the maximum turns founded in each square and keep the one with lower value of the turn. If the value is +\(\infty\) the answer become -1.

C. Photographer

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

You are a professional photographer (or something like that... :P).  Your clients usually request one or more photos in two of the following types: low quality and high quality. Low quality photos takes \(a\) megabytes of data. High quality photos takes \(b\) megabytes of data. Your camera can only store \(d\) megabytes of data. Your task is to pleased at most clients as you can; to please a client you need to store in your memory all the photos this client is requesting.

The solution of the problem is greedy, the key idea is to forget about that we have two types photos. We just need to focus in the total amount of megabytes to pleased the \(i\)-th client. We can calculate this with the following formula:

$$w = x_{i} * a + y_{i} * b$$

We sort all the clients in non-decreasing order of \(w\), and using this order we served each client until there is no space left.

UVA 10892 - LCM Cardinality

http://uva.onlinejudge.org/external/108/10892.html

You are given a integer \(N\). Your task is to return the number of different integer pairs with lcm equal to \(N\).

A good start is to first think how to get \(N\) as the \(lcm(a,b)\). In order to do that we first need to identify the different values that \(a\) and \(b\) can take. 

After get your hands dirty with couple of sample cases is not hard to see that \(a\) and \(b\) should be taken from the set of divisors of \(N\). The reason behind this is that the \(lcm(a,b)\) takes the maximum exponent from each prime factor of \(a\) and \(b\). The divisors of a number serves as a building block of the number that they divide. In other words contains fragments of the prime factorization of the given number \(N\). Tried another number that is not a divisor of \(N\) is not going to lead us to the correct result.

Let's clarify this thoughts with an example, the pairs that works for \(N = 12\) are the following:

1. \(lcm(1, 12) = 12\)
2. \(lcm(2, 12) = 12\)
3. \(lcm(3, 12) = 12\)
4. \(lcm(4, 12) = 12\)
5. \(lcm(6, 12) = 12\)
6. \(lcm(12, 12) = 12\)
7. \(lcm(3, 4) = 12\)
8. \(lcm(4,6) = 12\)

All this numbers belongs to the set of divisors of 12 that are the following: \(\{1, 2, 3, 4, 6, 12\}\). Note, that in total there are 21 pairs \(( \frac{6 \cdot 5}{2} + 6 \)  but not for all of them we get 12 as lcm. For example \(lcm(3, 6)\) is not 12.

The solution to this problem is to first calculate all the divisors of a given number \(N\) and stored them in the data structure of your preference. For each different pair of divisors we count the ones that \(lcm(d1, d2) = N\).