This is a discussion of an Olympiad problem from Kubica and Radozewski: 

Problem statement: 

You are given coins with the values being powers of two. 1,2,4,8,16,32,… and you have exactly one coin of each value. Then you could pay any (positive integer) amount of money using these coins(for example, 45 = 1 + 4 + 8 + 32) 

What is the smallest amount of money, which cannot be paid using the following set of coins: 

1. 6, 3, 2, 10, 21, 46, 1, 48? 

2. 12, 7, 3, 2, 31, 27, 28, 1? 

3. 27, 56, 1, 13, 60, 4, 7, 2? 

4. 44, 39, 5, 1, 9, 1, 18, 2? 

5. 62, 3, 26, 12, 53, 2, 1, 7? 

You have exactly one coin of each kind. 

Solution: 

The first step is to sort the sequence of coins in a non-decreasing order, for the sequence in the first subtask we have: 

1. 1,2,3,6,10,21,46,48 

Using the first two coins we can pay any integer amount from [1,3]. With the first three, we can pay any amount from [1,6] With the first four, we can pay any amount from [1,12] Note that for any amount 1-6 we do not have to use the last coin in the current sequence and for amount higher than that we have to use the last coin. 

In general, if the range of amounts that can be paid using the first k coins is from 0 to r, and the following coin has value x, then either: 

• x <= r+1 and it is possible to pay any amount from 0 to r +x using the first k +1 coins, or 

• x > r + 1 and it is not possible to pay the amount of r + 1, since x and all the following coins have greater values. 

Using this observation, we obtain the following sequence of included coins and ranges of amounts that can be paid: 

Coins                        1    2    3    6    10    21    46    48     

Maximum amount 1   3    6    12  22    43     

The amount 44 cannot be paid. 

The approach here is also dynamic programming although the strategy above uses greedy choice We generate all the subsequences of a given non-empty prefix and divide it into two groups: those containing the last element of the prefix and those not containing it. 

MaxSumUnPaid(Coins, I, j) 

If len(Coins) == 1 

   Return Coins[0]  

m[i,j] = 0  

For k = 0 to j-I-1 

     if (jth coin <= MaxSumUnPaid(Coins Choose K, I,j-1)  

           q =   MaxSumUnPaid(Coins Choose K, I,j-1) + MaxSumUnPaid(Coins with jth coin only, j,j) 

     If q > m[I,j]  

             M[I,j] = q  

  return m[I,j]

This is a discussion of another Olympiad problem on Informatics:

Question:

We are given 11 line segments of the following lengths:

(a)    1, 49, 11, 3, 338, 128, 30, 78, 17, 208, 6

(b)   103, 1, 15, 8, 167, 271, 5, 3, 64, 25, 38

(c)    94, 154, 5, 8, 248, 35, 2, 1, 58, 23, 13

(d)   87, 3, 20, 12, 141, 4, 228, 52, 1, 33, 8

(e)   108, 25, 178, 15, 3, 42, 9, 68, 1, 4, 286

Is it possible to pick three different line segments from the set and use them to obtain a triangle with positive area? If so, which three segments to choose?

Solution: A triangle is formed when we choose segments such that the longest segment is strictly shorter than the total length of the smaller two. Say a + b > c

In each of the above we can pick three segments that suit this condition and can be used to form a triangle and these solutions are:

(a)    30, 49, 78

(b)   15,25,38

(c)    13,23,35

(d)   20,33,52

(e)   42,68,108

Notice if we arrange the lengths of the segments in sorted order, we only have to progress until we meet the criteria above. For example,

(a)    1,3, 6, 11, 17, 30, 49, 78, . . .

We progress picking consecutive three until we pick 30, 49 and 78.

In other words the algorithm for this task involves a greedy strategy. The greedy choice property is justified with the following: we start with three segments in sorted order and show that by increasing the lengths of the smaller two (without exceeding the lengths of the longer one) we limit the available choices and raise the odds of obtaining a solution.

Hence we can write the solution as:

PickThree(Segments, I,j)

SortSegments(Segments)

for k =  I+2 to j

   if Segments[k-1] + Segments[k-2] > Segments[k]

        return Segments[k-2], Segments[k-1], Segments[k]

return null

 

This is a discussion of an Olympiad problem on palindromes in Informatics. 

The problem is stated this way: Some words can be divided into even length palindromes. The word  

aabbaaabbaaa can be divided into 3 even length palindromes.  

aabbaaabbaaa   = aabbaa | abba | aa 

What is the smallest number of even length palindromes in a division of the word: 

(a) aabbaabaabaabbbb? 

(b) aaaaabbaaabbabbabbbb? 

(c) baabbbbaabaabaabbbbb? 

(d) aabbaabaabaabbbbbbbb? 

(e) aaaabbaaabbabbaabbbb? 

Below are the optimal divisions of the words from all subtasks: 

(a) aabbaabaabaabbbb = aa|bbaabaabaabb|bb 

(b) aaaaabbaaabbabbabbbb = aa|aaabbaaa|bbabbabb|bb 

(c) baabbbbaabaabaabbbbb = baab|bbbaabaabaabbb|bb 

(d) aabbaabaabaabbbbbbbb = aa|bbaabaabaabb|bbbbbb 

(e) aaaabbaaabbabbaabbbb = aa|aabbaa|abba|bbaabb|bb 

The given words have the following property: 

If we are looking for prefixes in the given word that are the longest even length palindrome to select as a division, it does not yield the optimal choice 

If we are looking for suffixes in the given word that are the longest even length palindrome to select as a division, it does not yield the optimal choice 

Therefore we cannot apply the greedy strategy. 

Instead we can apply the dynamic programming technique. 

To solve this problem, we apply dynamic programming by following the four-step sequence: 

1.     Characterize the structure of an optimal solution 

2.     Recursively define the value of an optimal solution 

3.     Compute the value of an optimal solution 

4.     Construct an optimal solution from computed information 

In this case we say the optimal structure is as follows: 

The optimal solution for the sequence in the word W (W1,W2,… Wn) is the same as finding the optimal solution of two sub-problems obtained by splitting the range into two involving A1…Ak and Ak+1 .. An and then combining these optimal subproblems. 

In this case we test each partition for the following when combining: 

• Is the left and right division containing only even length palindromes 

The termination condition is when  

• There is a no division and the count at this stage is 0 
• The given word is already an even length palindrome  and the count at this stage is 1 

The progress condition is when palindrome 

• One of the divisions has an even length palindrome 

The optimal solution can be described in a top down recursive strategy as follows: 

Recursive-Even-Length-Palindrome(W, I, j) 

If I == j 

   Return 0 

If IsEvenLengthPalindrome(W,I,j)  

   Return 1 

m[i,j] = infinity 

For k = I to j-1
     leftcost, leftvalid = Recursive-Even-Length-Palindrome(W,I,k)
     rightcost, rightvalid = Recursive-Even-Length-Palindrome(W, k+1, j) 

     q =  leftcost+rightcost 

     If q < m[I,j] 

             M[I,j] = q 

  return m[I,j], leftvalid && rightvalid 

ISEvenLengthPalindrome(W,I,j) = IsPalindrome(W,I,j) && (j-i+1) %2 == 0 

Also the iterations could be optimized by using incrementing k by 2 to j-2 from i since we only consider even lengths. It will require adjusting the termination conditions.