UVA 11548 - Blackboard Bonanza

http://uva.onlinejudge.org/external/115/11548.html

This problem statement tried to mislead you with some weird game between two characters Alice and Bob. Let's not put to much attention in that and focus in the the real task:

Given \(n (2 \leqslant n \leqslant 70) \) strings, you need to return the length of the best vertical alignment between an arbitrary pair of strings \(S_{i}\), \(S_{j}\) where \(i \neq j\). What exactly does that mean? Let's take a look to an example to clear out some obscures points of this statement:

The following two pictures shows two possible alignments for the strings "ABCD" and "ADC", among them the second one is the best alignment which include the letters A and C for a total length of 2.

The constraints of this problem are not to high, to solve it we can simply iterate over all the possible pair of strings, and for each of them calculate all the possible alignments and keep the length of the best one.

The hardest part perhaps is the procedure to calculate the best alignment for a given pair of strings. In order to do that, we just need to take one of the string as point of reference, let's call this string \(S\) and the another string \(P\), at each step we start to compare each character of \(S\) with each character of \(P\), once we are done we repeat the process but now, beginning in the next letter of the string \(S\). During this process if one the string reach it's last letter we restart the counter of matches, and start to count again from the current position, which is equivalent to begin another alignment.

This may sound a little bit confusing let's take a look to an example:
 

The previous picture simulates the idea of the algorithm as we can see using this method we consider all the possible alignments between "ABCD" and "ADC".

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

Codeforces Round #142

A. Dragons

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

You are crazy about Massively Multiplayer Online role-playing games (MMORPG), recently you are playing one about dragons, the purpose of this game is to defeat \(n\) dragons, each of them have a strength of \(x_{i}\) units, the duel between two opponents is determined by their strength. In other words, the player with the strongest dragon wins the duel.

Every time you defeat a dragon you get a bonus strength of \(y_{i}\) units, you are given a dragon with initial strength of \(s\) units, you are able to fight with any dragon in arbitrary order,  print "YES" if is possible to defeat all the dragons, otherwise print "NO".

This is a really common greedy problem, not too long ago in the Codeforces Round #128 appear a similar problem called Photographer.

The intuition to solved this problem is the following, we want our dragon get stronger as possible in order to be able to face the big (strongest) dragons, this is why we first need him to face the weaker ones and accumulate as much bonus strength points as he can. Just like when you are playing video games you don't go to fight the last boss until you are pretty confident you are at his level...  The following picture illustrate the idea, were the green numbers represent the strength of each dragon:

To accomplish this we sort the dragons by their strength and first fight the ones with lower strength, if we are able to beat all the dragons the answer is "YES", otherwise "NO". The overall time complexity of this solution is \(O(n log n)\).

B. T-primes

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

A T-prime number is a number that has exactly tree positive divisors. For example 4 is an T-prime because its divisors are \(\{1, 2, 4\}\). Given \(n\) numbers your task is to print "YES" if the number is T-prime, "NO" otherwise.

The following website may be useful to spot the pattern Table of Divisors, with this table you just need to look at the numbers with 3 divisors and try to came up with some good conjectures.

To help the reader spot the pattern let's first list a couple of number with 3 divisors:

\(\{4, 9, 25, 49, 121, 169, \cdots\}\)

If we look carefully all this number are perfect squares...

\(\{2^{2}, 3^{2}, 5^{2}, 7^{2}, 11^{2}, 13^{2}, \cdots \}\)

At this point we may feel tempted to conjecture that all the perfect squares has three divisors, but that is totally wrong, a counter-case 4² is 16 and has 5 divisors \(\{1, 2, 4, 8, 16\}\). If we take a closer look seems that the perfect squares of prime numbers do the trick.

Let's try to proof the following statement "The squares of prime numbers has exactly three divisors":

By definition we know that the prime numbers are just divisible by 1 and itself, in other words the set of divisors of any prime number are just \({1, p}\) where \(p\) represent an arbitrary prime number.

If we square any prime number we have a composite number with the following standard prime factorization \(a = p^{2}\), is easy to see that the set of divisors for this new number are always in the form \(\{1, p, p^{2}\}\), which has exactly 3 divisors.

The constraints of the problem establish that the given numbers can be as big as \(10^{12}\), because the T-prime are squares of primes is enough with a list of primes not higher than \(10^{6}\) , this is because \(\sqrt{10^{12}} = 10^{6}\), this list of primes can be constructed using Sieve of Eratosthenes.

The next step, is take this list of primes and square each of them and create a list of T-primes numbers. Once we got the list of t-primes we can use binary search to query each of the numbers in the given list.

C. Shifts

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

You are given a matrix with \(n\) rows and \(m\) columns. You can perform two operations in the rows of the matrix:

(1) cyclically shift right 
Given the row "00111" if we apply the operation we get "10011".

(2) cyclically shift left
Given the row "00111" if we apply the operation we get "01110".

Using the previous operations your task is to print the minimum number of operations that takes to get some column of our matrix full of ones. If this is impossible print -1.

Let's first consider the case when it is impossible to get one of the columns with just ones, is easy to see that just in the cases when at least one row is full of zeros the answer is -1.

We are particular interesting in the minimum amount of shift operations to fill an entry \(a_{ij}\) of our matrix with a 1, to accomplish that we just need to look for the nearest 1 to the entry \(a_{ij}\) in both directions left and right.

For example consider the row #3 "0010" the element in color red belong to our target column, we want to know the minimum amount of shift operations to replace this 0 with a 1. We could make 3 right shifts to get the following row "0100" or we could make 1 left shift and get the same row "0100".

We can calculate this distance by a simple linear search, but, the constraints are too high. We need to pre-calculate a table containing the distance from any entry \(a_{ij}\) to the nearest 1 in the same row (circular distance). For example the table for the previous example look like this:

Once we have this table, the answer is just the minimum sum over all the columns in our matrix. To reduced the complexity of the code I used two distance matrix, but, this could easily merge into one. The overall time complexity of this solution is \(O(n \cdot m)\).

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. 

Counting inversions in an array using Binary Indexed Tree

Introduction

Given an array \(A\) of \(N\) integers, an inversion of the array is defined as any pair of indexes \((i,j)\) such that \(i \leqslant j\) and \(A[i] \geqslant A[j]\).
 
For example, the array \(a = \{2, 3, 1, 5, 4\}\) has three inversions: \((1,3)\), \((2,3)\), \((4,5)\), for the pairs of entries \((2,1)\), \((3,1)\), \((5,4)\).

Traditionally the problem of counting the inversions in an array is solved by using a modified version of Merge Sort. In this article we are going to explain another approach using Binary Indexed Tree (BIT, also known as Fenwick Tree). The benefit of this method is that once you understand its mechanics, can be easily extended to many other problems.

Prerequisite

This article assume that you have some basic knowledge of Binary Indexed Trees, if not please first refer to this tutorial.

Replacing the values ​​of the array with indexes

Usually when we are implementing a BIT is necessarily to map the original values of the array to a new range with values between \([1, N]\), where \(N\) is the size of the array. This is due to the following reasons:

(1) The values in one or more \(A[i]\) entry are too high or too low. 
(e.g. \(10^{12}\) or \(10^{-12}\)).

For example imagine that we are given an array of 3 integers:
\(\{1, 10^{12}, 5\}\)
This means that if we want to construct a frequency table for our BIT data structure, we are going to need at least an array of \(10^{12}\) elements. Believe me not a good idea...

(2) The values in one or more \(A[i]\) entry are negative. 
Because we are using arrays it's not possible to handle in our BIT frequency of negative values (e.g. we are not able to do \(freq[-12]\)).

A simple way to deal with this issues is to replace the original values of the target array for indexes that maintain its relative order.  

For example, given the following array:

The first step is to make a copy of the original array \(A\) let's call it \(B\). Then we proceed to sort \(B\) in non-descending order as follow:

Using binary search over the array \(B\) we are going to seek for every element in the array \(A\), and stored the resulting position indexes (1-based) in the new array \(A\).

\(binary\_search(B, 9) = 4\)      found at position 4 of the array B
\(binary\_search(B, 1) = 1\)      found at position 1 of the array B
\(binary\_search(B, 0) = 0\)      found at position 0 of the array B
\(binary\_search(B, 5) = 3\)      found at position 3 of the array B
\(binary\_search(B, 4) = 2\)      found at position 2 of the array B

The resulting array after increment each position by one is the following:

The following C++ code fragment illustrate the ideas previously explained:

Counting inversions with the accumulate frequency 

The idea to count the inversions with BIT is not to complicate, we start iterating our target array in reverse order, at each point we should ask ourselves the following question "How many numbers less than \(A[i]\) have already occurred in the array so far?" this number corresponds to the total number of inversions beginning at some given index. For example consider the following array \(\{3, 2, 1\}\) when we reach the element 3 we already seen two terms that are less than the number 3, which are 2 and 1. This means that the total number of inversions beginning at the term 3 is two.

Having this ideas in mind let's see how we can applied BIT to answer the previous question:

1. \(\mathbf{read}(idx)\) - accumulate frequency from index 1 to idx
2. \(\mathbf{update}(idx, val)\) - update the accumulate frequency at point idx and update the tree.
3. cumulative frequency array - this array represents the cumulative frequencies (e.g. \(c[3] = f[1] + f[2] + f[3])\) , as a note to the reader this array is not used for the BIT, in this article we used as a way of illustrating the inner workings of this data structure.

Step 1: Initially the cumulative frequency table is empty, we start the process with the element 3, the last one in our array.
 

how many numbers less than 3 have we seen so far

\(x = read(3 - 1)\) = 0
\(inv\_counter = inv\_counter + x\)

update the count of 3's so far 

\(update(3, +1)\)
\(inv\_counter = 0\)

Step 2: The cumulative frequency of value 3 was increased in the previous step, this is why the \(read(4 - 1)\) count the inversion \((4,3)\).

how many numbers less than 4 have we seen so far
\(x = read(4 - 1) = 1\)
\(inv\_counter = inv\_counter + x\)

update the count of 4's so far
\(update(4, +1)\)
\(inv\_counter = 1\)

Step 3: The term 1 is the lowest in our array, this is why there is no inversions beginning at 1.

how many numbers less than 1 have we seen so far
\(x = read(1 - 1) = 0\)
\(inv\_counter = inv\_counter + x\)

update the count of 1's so far
\(update(1, +1)\)
\(inv\_counter = 1\)

Step 4: Theres is only one inversion involving the value 2 and 1.

how many numbers less than 2 have we seen so far
\(x = read(2 - 1) = 1\)
\(inv\_counter = inv\_counter + x\)

update the count of 2's so far
\(update(2, +1)\)
\(inv\_counter = 2\)

Step 5: There are 4 inversions involving the term 5: \((5,2)\), \((5,1)\), \((5,4)\) and \((5,3)\).

how many numbers less than 5 have we seen so far
\(x = read(5 - 1) = 4\)
\(inv\_counter = inv\_counter + x\)

update the count of 5's so far  
\(update(5, +1)\)
\(inv\_counter = 6\)

The total number of inversion in the array is 6.

The overall time complexity of this solution is \(O(N logN)\), the following code corresponds to a complete implementation of the ideas explained in this tutorial:

Related problems

UVa 10810 Ultra-QuickSort
UVa 11495 Bubbles and Buckets
SPOJ 6256 Inversion Count
Codeforces Beta Round #57 E. Enemy is weak

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.

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})\).