Sunday, October 5, 2014

ThePriceIsRight

Problem:

TopCoder Problem Statement - ThePriceIsRight

Overview:

Find the maximum length of an increasing sequence in a series of numbers. Also determine the number of sequences of that length.

Java Source:
01: public class ThePriceIsRight {
02: 
03:     public int[] howManyReveals(int[] prices) {
04: 
05:         // Holds the longes sequence that ends at this prices.
06:         int[] maxLength = new int[prices.length];
07: 
08:         // Holds the nubmer of ways to reach that max length
09:         int[] waysToReachMaxLength = new int[prices.length];
10: 
11:         // out[0] = maxLength, out[1] = number of ways to do it.
12:         int[] out = new int[2];
13: 
14:         for (int i = 0; i < prices.length; i++) {
15: 
16:             int longest = 0;
17: 
18:             /*
19:             * Look for the longest sequence to the left that ends on a price
20:             * that is less than the current price.
21:             */
22:             for (int j = 0; j < i; j++) {
23:                 if (prices[j] < prices[i]) {
24:                     longest = Math.max(longest, maxLength[j]);
25:                 }
26:             }
27: 
28: 
29:             /*
30:             * Look to the left for the nubmer of ways to reach the longest
31:             * sequence.  If the length equals the current length, and
32:             * it's prices is less than the current price, then count it as
33:             * a way to reach the current sequence.
34:             */
35:             for (int k = 0; k < i; k++) {
36:                 if ((maxLength[k] == longest) && (prices[k] < prices[i])) {
37:                     waysToReachMaxLength[i] += waysToReachMaxLength[k];
38:                 }
39:             }
40: 
41:             // There's always at least 1 one to reach the max length.
42:             if (waysToReachMaxLength[i] == 0) waysToReachMaxLength[i] = 1;
43: 
44:             /*
45:             * We've found the longest by looking at the previous soutions.  Now
46:             * add on the current index.
47:             */
48:             maxLength[i] = 1 + longest;
49: 
50:             // Update the max length found if necessary.
51:             out[0] = Math.max(out[0], maxLength[i]);
52:         }
53: 
54:         /*
55:         * Add up all the ways to reach the maximum length.
56:         */
57:         for (int i = 0; i < prices.length; i++) {
58:             if (maxLength[i] == out[0]) {
59:                 out[1] += waysToReachMaxLength[i];
60:             }
61:         }
62: 
63:         return out;
64:     }
65: }
Notes:

This solution is based on the pseudo-code provided in the topcoder community forums. Found here

We're looking for the longest sequence of increasing numbers. The numbers need not be contiguous. One of the tests gives the prices [39, 88, 67, 5, 69, 87, 82, 64, 58, 61]. Here there are two increasing sequences of length four: 39, 67, 69, 87 and 39, 67, 69, 82. The expected return value is {4,2}.

To solve this, we'll work from left to right through the prices array. For each position, we'll calculate the longest sequence that ends at that position and store that in the maxLength[] array. We also store the number of sequences of that maximum length in the waysToReachMaxLength[] array.

To find the longest sequence that ends at the current position we'll look at positions to the left of the current position. This is a Dynamic Programming technique where we use values that have already been calculated to calculate the next value. The value will be 1 more than the longest sequence to the left, only counting prices that are less than the current price.

Once we know the length of the longest sequence that ends at the current element, we again look to the left, and sum the number of ways to reach any price that shares that maximum length. Again, only considering smaller prices. To illustrate how these two values are calculated, let's walk through using the sample input given above.

Array / Index 0 1 2 3 4 5 6 7 8 9
prices 39 88 67 5 69 87 82 64 58 61
maxLength ? ? ? ? ? ? ? ? ? ?
waysToReachMaxLength ? ? ? ? ? ? ? ? ? ?

The first price is 39. Since there are no previous prices, the longest sequence for index 0 is 1, and there is 1 way to accomplish that.

The price at the next position is 88. To get the longest, we look left and see that the longest sequence with a price less than 88 is 39. 39 has a sequence length of 1, so the length to 88 is 2. There is only one way to achieve the length of 2.

The same applies to the next position, 67. The longest previous sequence with a price less than 67 belongs to 39. Again the length is 2, and there is one way to achieve that length (39 -> 67). Our arrays now look like this:

Array / Index 0 1 2 3 4 5 6 7 8 9
prices 39 88 67 5 69 87 82 64 58 61
maxLength 1 2 2 ? ? ? ? ? ? ?
waysToReachMaxLength 1 1 1 ? ? ? ? ? ? ?

The next position 5 has no price smaller than it to the left. It's maximum length is therefore 1, and there is 1 way to do it.

Next is 69 at index 4. There are two prices smaller that it (39, and 67). Since 67 ends a sequence of length 2, 69 is added to form a sequence length of 3. Still there is only one way to reach a length of 3 (39 -> 67 -> 69).

The longest sequence to the left of 87 is that belonging to 69. So, 87 gets one more than 69's length. The same goes for the next position, 82. Note that 82, cannot use 87 length of 4, since 87's price is greater. Our arrays now look like:

Array / Index 0 1 2 3 4 5 6 7 8 9
prices 39 88 67 5 69 87 82 64 58 61
maxLength 1 2 2 1 3 4 4 ? ? ?
waysToReachMaxLength 1 1 1 1 1 1 1 ? ? ?

At index 7, we get a maximum sequence length that can be reached in different ways. Looking left, we see that 39 and 5 both end a sequence of length 1, which is the longest sequence coming into 64. Therefore, we can reach 64 in two ways 39 -> 64, and 5 -> 64.

Similarly, 58, has two ways to choose its maximum length sequence, 39 -> 58 and 5 -> 58.

Finally, 61, has two sequences of length 3: 39 -> 58 -> 61 and 5 -> 58 -> 61. At the end, our arrays look like this:

Array / Index 0 1 2 3 4 5 6 7 8 9
prices 39 88 67 5 69 87 82 64 58 61
maxLength 1 2 2 1 3 4 4 2 2 3
waysToReachMaxLength 1 1 1 1 1 1 1 2 2 2

Last, it's just a matter of summing all the ways to reach the elements that share the maximum length. 87 contributes 1, and 82 contributes another, for a final answer of {4,2}.

No comments:

Post a Comment