TopCoder Problem Statement - PotentialGeometricSequence
Calculate the number of sub-sequences of an array that may generate a geometric sequence.
01: public class PotentialGeometricSequence {
02:
03: public int numberOfSubsequences(int[] d) {
04:
05: int count = 0;
06:
07: /*
08: * j bounces back and forth between i and d.length as i
09: * moves from 0 to d.length.
10: * This gives us every possible contiguous subsequence.
11: */
12: for (int i = 0; i < d.length; i++) {
13: for (int j = i; j < d.length; j++) {
14: if (checkSequence(i, j, d)) {
15: count++;
16: }
17: }
18: }
19:
20: return count;
21: }
22:
23: /*
24: * Checks to see if the values in d[] decrease by the same amount
25: * for each step from j down to i. If so, return true; otherwise false.
26: * For example, if the values in d[] are {3,4,5} it will return true
27: * because we decrease by 1 to go from 5 to 4, and then by 1 again to
28: * go from 4 to 3.
29: */
30: private static boolean checkSequence(int i, int j, int[] d) {
31:
32: /*
33: * If there are 0 or 1 steps between i and j, then it must be true
34: */
35: if ((j - i) <= 1) return true;
36:
37: /*
38: * Get the difference between the two right-most values. Each step
39: * from here on must differ by this same amount.
40: */
41: int diff = d[i + 1] - d[i];
42:
43: /*
44: * Work right to left from j down to i. Ensure that each step
45: * differs by diff
46: */
47: for (int x = i; x < j; x++) {
48: if ((d[x] + diff) != (d[x+1])) {
49: return false;
50: }
51: }
52:
53: return true;
54: }
55:
56: }
Possibly the most confusing problem statement I've come across so far on TopCoder. The solution above passes all of the system tests, but I still have no idea what the problem is asking for.
My advice is to ignore almost everything in the problem statement and notes. The mention of possible geometric sequences, trailing zeros in the binary representation of the number, answers being positive or negative, etc. are all irrelevant. There is no need to examine the binary representation of any numbers, or calculate geometric sequences. Here, in one sentence, is what you need to do:
For each possible sub-sequence in d[], determine if the values are evenly spaced. That's it!
Any sub-sequence of size 1 or 2 will be evenly spaced by definition, and therefore included in the count. For larger sub-sequences, calculate the step size by subtraction: d[x+1] - d[x]. Now, test to see if each d[i] + step = d[i + 1] for all values of i between x and j.
The following tables illustrates the 37 possible sub-sequences expected by Example #4
| Index in d[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| Value of d[x] | 1 | 3 | 5 | 5 | 5 | 5 | 64 | 4 | 23 | 2 | 3 | 4 | 5 | 4 | 3 |
| count | Start Index | End Index | Length |
|---|---|---|---|
| 1 | 0 | 0 | 1 |
| 2 | 1 | 1 | 1 |
| 3 | 2 | 2 | 1 |
| 4 | 3 | 3 | 1 |
| 5 | 4 | 4 | 1 |
| 6 | 5 | 5 | 1 |
| 7 | 6 | 6 | 1 |
| 8 | 7 | 7 | 1 |
| 9 | 8 | 8 | 1 |
| 10 | 9 | 9 | 1 |
| 11 | 10 | 10 | 1 |
| 12 | 11 | 11 | 1 |
| 13 | 12 | 12 | 1 |
| 14 | 13 | 13 | 1 |
| 15 | 14 | 14 | 1 |
| 16 | 0 | 1 | 2 |
| 17 | 1 | 2 | 2 |
| 18 | 2 | 3 | 2 |
| 19 | 3 | 4 | 2 |
| 20 | 4 | 5 | 2 |
| 21 | 5 | 6 | 2 |
| 22 | 6 | 7 | 2 |
| 23 | 7 | 8 | 2 |
| 24 | 8 | 9 | 2 |
| 25 | 9 | 10 | 2 |
| 26 | 10 | 11 | 2 |
| 27 | 11 | 12 | 2 |
| 28 | 12 | 13 | 2 |
| 29 | 13 | 14 | 2 |
| 30 | 0 | 2 | 3 |
| 31 | 2 | 4 | 3 |
| 32 | 3 | 5 | 3 |
| 33 | 9 | 11 | 3 |
| 34 | 10 | 12 | 3 |
| 35 | 12 | 14 | 3 |
| 36 | 2 | 5 | 4 |
| 37 | 9 | 12 | 4 |
In the bottom table, we see each possible sub-sequence of lenght 1 or 2. Also included are all subsequences where the step from one index to the next is equal. For example, for count #37 d[9] = 2 and d[10] = 3. A step size of 1. d[11] and d[12] continue this pattern, but d[13] breaks it. Therefore we include the subsequence from d[9] to d[12].
No comments:
Post a Comment