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:
- 6, 3, 2, 10, 21, 46, 1, 48?
- 12, 7, 3, 2, 31, 27, 28, 1?
- 27, 56, 1, 13, 60, 4, 7, 2?
- 44, 39, 5, 1, 9, 1, 18, 2?
- 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,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
No comments:
Post a Comment