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.