Saturday, September 6, 2014

PotentialGeometricSequence

Problem:

TopCoder Problem Statement - PotentialGeometricSequence

Overview:

Calculate the number of sub-sequences of an array that may generate a geometric sequence.

Java Source:
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: }
Notes:

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

Input array. Given as parameter d[]
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


Subsequences that meet the problem's criteria
count Start Index End Index Length
1001
2111
3221
4331
5441
6551
7661
8771
9881
10991
1110101
1211111
1312121
1413131
1514141
16012
17122
18232
19342
20452
21562
22672
23782
24892
259102
2610112
2711122
2812132
2913142
30023
31243
32353
339113
3410123
3512143
36254
379124

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