The Hidden Arithmetic Progression

Computer Science Level 4

Here is a set S S of numbers.

There is some subset X ⊂ S X \subset S such that all the elements of X X form an arithmetic progression when sorted.

What is the largest possible value of ∣ X ∣ |X| ?

Extra Credit: Minimize the time complexity of your solution.


The answer is 288.

View wiki
Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

5 solutions 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
 
#include <iostream>
#include <vector>
#include <algorithm>

typedef std::vector<int> vi;
typedef std::vector<vi> vvi;

int main(){
  int N;
  std::cin >> N;

  vi numbers(N);

  for(int i=0; i < N; i++)
    std::cin >> numbers[i];

    //2 numbers always form an AP;
    if (N <= 2){
      std::cout << N << std::endl;
      return 0;
    }

    //preprocessing - sort the vector of numbers
    std::sort(numbers.begin(), numbers.end());

    //Create a dp table where dp[i][j] = size of longest arithmetic progression that starts with numbers[i], numbers[j]
    int dp[1000][1000];
    int longestAP = 2; //initialization

    //Clearly dp[i][N-1] = 2;
    for (int i=0; i < N-1; i++){
      dp[i][N-1] = 2;
      //std::cout << "still here" << std::endl;
    }

    //We will consider every possible j, and look for i and k such that i, j, k form an AP
    //If they do, dp[i][j] = dp[j][k] + 1

    for(int j=N-2; j >= 1; j--){ //We're going to fill the table from the right since we've the edge cases there.
      //adjust i,k until they all form an AP
      //std::cout << j << std::endl;
      int i = j-1, k = j+1;
      while (i >= 0 && k <= N-1)
        if (numbers[i] + numbers[k] < 2*numbers[j])
          k++;
        else if (numbers[i] + numbers[k] > 2*numbers[j]){
          dp[i][j] = 2; //since this  i does not have a corresponding k, it is a 2 termed AP
          i--;
        }
        else{
          dp[i][j] = dp[j][k] + 1;
          longestAP = std::max(dp[i][j], longestAP); //keep track of maximum

          //fill other values of dp[i][j] for different values of i
          i--;
          k++;
        }
      //in case the loop stopped because k went out of range, we need to fill all the i's that are left with 2's.
      for (; i >= 0; i--)
        dp[i][j] = 2;
    }


    /*for (int i=0; i < N; i++){
      for (int j=0; j < N; j++)
        std::cout << dp[i][j] << " ";
      std::cout << std::endl;
    }*/



  std::cout << longestAP << std::endl;

  return 0;
}


1
2
 
chattopadhyay@chattopadhyayPC:~/Documents$ cat data | ./llap
288

That gives 288.

For the sake of completion, the arithmetic progression starts with 3530 , 3548 , ⋯ 3530, 3548, \cdots for 288 terms

3 Helpful 0 Interesting 0 Brilliant 0 Confused
Rushikesh Jogdand
Jul 21, 2016

Don't know whether it's most efficient solution 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
 
a=[8192,6146,5803,8534,4106,4109,6158,2065,8210,8213,9220,4124,6176,4130,8228,3761,4142,6194,6198,4151,4160,6212,2118,8264,6218,4171,4172,5474,4178,6230,4185,8282,6842,4193,4196,6248,8300,4214,1385,6266,2171,8318,8319,6276,4232,4235,6284,2754,4238,8336,146,4250,157,6302,4256,6305,8354,6307,4260,2213,210,4268,6320,8372,4277,4286,192,6338,4291,8390,2764,4298,9591,1058,4304,7544,6354,6356,7886,6358,8408,4132,7683,4319,4322,2277,6374,8425,8426,7100,238,4340,5600,6392,1482,8444,4349,2302,4821,4358,263,4361,6410,6411,8462,4376,2436,2330,6428,4382,6432,5852,4394,4397,6446,8584,8498,4403,2782,4412,6464,8516,8246,4424,330,6199,4430,2383,6482,8531,6485,4438,2391,740,4445,4448,4450,6500,3814,8552,6888,6510,369,4466,6517,6518,376,8570,3818,1429,4484,4487,6536,8588,9697,4502,4503,6554,4508,1434,8606,2800,422,4520,8743,6570,6572,6574,4527,8624,4529,2489,4538,6588,8266,6590,8642,4550,2124,4556,6608,8660,4571,4574,6623,6626,8678,698,2542,4592,3496,8690,6644,5404,8696,4609,4610,4613,6662,6663,4616,2569,6666,2818,528,4628,6680,4634,2480,2595,2596,5894,4646,2599,2602,2605,4655,2608,2824,2611,2614,4664,2617,2620,2623,2626,4676,2629,2632,6729,4682,2635,2638,2641,2644,2647,6744,100,2650,4700,2653,606,2656,4705,2658,2659,2662,2665,4715,2668,4718,2671,104,2674,4883,2677,2680,2836,634,2683,3178,2686,4736,2689,4739,6788,790,2695,6252,2698,652,2701,2704,8849,4754,2707,2710,4760,2713,2716,8001,2719,4768,2722,3867,4772,2725,6822,2728,2731,4781,2734,687,2737,6835,2740,8885,4790,2743,6841,4794,2747,700,2749,6824,8637,2752,4802,2755,2746,4808,2761,6860,2767,433,2770,2773,4823,2776,4826,2779,6878,2785,2788,2854,2791,744,2794,1525,4844,2797,6896,2803,6900,2806,2807,2809,8955,2812,4862,2815,4865,6914,2821,4872,4874,2827,2830,4880,2833,6930,8979,6932,789,4886,2839,793,2842,2845,2848,4898,2851,6950,1868,2857,4907,2860,2863,9008,2866,4916,2869,6968,2875,2878,4927,4928,2881,6978,836,4934,2887,6986,2893,846,2896,2872,6994,2899,4949,4950,4952,2905,3370,2908,2911,2913,2914,2917,2920,4970,2923,4972,2925,2926,2929,2932,2935,2938,4988,2941,4991,2944,2947,2950,7047,2953,2956,5006,2959,2758,2962,5012,2965,2966,2968,2884,9114,2971,2974,5024,2977,6676,5028,2983,5033,2986,2989,2992,5042,2995,2998,952,3001,3004,2890,3007,3566,3010,5060,3013,3014,967,3016,8012,3019,3022,9167,3025,3028,5078,3031,7130,3037,5086,3040,3043,3046,5096,3049,3052,1005,3055,7153,3058,3061,3064,5114,3067,3070,3072,3073,3076,2902,3079,3082,5132,3085,3088,5139,6104,7197,5150,3103,1056,2224,7202,7206,7004,5298,5166,5168,8054,7220,3125,9273,522,2012,5184,5186,7238,5192,8902,514,5204,1111,7256,7259,3549,9061,5222,7274,9326,3944,7286,5239,5240,1145,7292,5245,7019,9750,5257,5258,1164,7310,7312,7022,5276,3231,7328,9379,1189,1196,5294,7346,1203,4980,1210,5312,1217,7364,7365,1224,1231,5328,3281,5330,3284,7382,9432,7375,5340,1245,5348,5351,7400,1259,1234,1266,5366,1273,7418,6698,1280,7040,1238,1287,5384,3337,7436,9485,1294,899,1301,5402,1308,7454,3973,560,1315,7464,5417,5418,1323,5420,7471,7472,1329,1336,1588,3387,5438,5439,7490,3638,1350,5978,1357,5456,5457,7508,1252,1371,1376,6032,1378,7524,7526,3432,6716,7058,1392,3443,5492,1399,5496,1406,7553,5506,3459,1412,1413,5510,7562,1420,1427,3477,1945,5528,7577,5530,7580,6042,581,1441,1448,1449,5546,9644,7598,1455,1462,3657,5563,5564,1469,7616,3522,1476,1270,5574,3530,1483,5582,4344,1490,6734,2980,5595,3548,1501,1504,5712,7652,7184,1511,6396,1518,3567,5616,5618,5621,7670,1532,1535,3584,1539,5636,7688,1546,1553,3602,5652,5654,4697,1560,7706,7076,3612,5722,1567,3620,5669,1574,5672,8796,7724,1581,5684,3637,1590,7736,5690,1595,7742,6752,1602,6941,7094,3655,3656,1609,9803,5708,7778,1616,611,3342,1623,7760,3674,5726,5730,1637,1641,3692,7789,5744,1651,7796,3702,3192,1658,3708,3710,9856,1665,5762,7814,1672,1644,5262,5773,3726,1679,3728,5780,1686,7832,7108,4662,1693,1694,5061,3746,3747,1700,5798,2648,284,7850,1707,6770,5808,7112,1714,3764,8478,5816,1721,7868,8138,1728,8480,5828,3782,1735,5834,1742,3792,1747,1749,7895,3800,1756,1497,7904,1763,5862,3815,1768,1770,468,5870,1777,7922,6782,1784,5881,3836,1322,5886,1791,5888,7940,878,1798,1800,7948,1805,3854,3857,5906,1812,7958,7630,2692,1819,3034,3872,1826,5924,3878,7976,1833,5934,1840,3890,5942,1847,7994,3899,1630,1853,1854,5951,3904,1857,3908,1861,5960,5964,3920,1875,3926,1882,5775,8030,1889,5987,3941,1896,316,5996,1903,8048,1906,3390,1910,3962,1343,1917,6014,8066,1924,6806,7148,1931,3980,9538,3983,7634,1938,8084,6040,3993,1946,3998,1952,6050,4004,8102,1959,8107,5106,1966,4016,6068,1973,8120,4025,4026,1980,475,4034,1987,6086,1994,6093,4046,2001,4052,2008,8156,2015,8160,4067,4070,6120,6122,8174,4079,6129,4082,2035,7166,7842,4088,1364,6140]
a.sort()
maxl=0
for i in range(0,len(a)):
    for j in range(i+1,len(a)):
        d=a[j]-a[i]
        l=1
        e=a[i]
        while e+d in a:
            e+=d
            l+=1
        if l>maxl:maxl=l
print(maxl)

2 Helpful 0 Interesting 0 Brilliant 0 Confused
You Kad
Jul 29, 2016 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
 
from urllib.request import urlopen
with urlopen('https://gist.githubusercontent.com/anonymous/7bbd0959b81b2e33589f00adce7a1b2b/raw/a573b4d0c38d6ca367d407c29ea7cec08871252f/gistfile1.txt') as f:
    L = sorted([int(i) for i in f.read().split()])
    S = set(L)
    n =  len(L)
    maxi = 2
    for i in range(n-1):
        for j in range(i+1, n):
            d = L[j] - L[i]
            k = 2
            while L[i]+k*d in S:
                k+=1
            if k > maxi:
                maxi = k
    print(maxi)

1 Helpful 0 Interesting 0 Brilliant 0 Confused
Gopinath No
Aug 2, 2016

A direct translation of the pseudo-code explained here 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
a = [0, 8192, 6146, 5803, 8534, 4106, 4109, 6158, 2065, 8210, 8213, 9220, 4124, 6176, 4130, 8228, 3761, 4142, 6194, 6198, 4151, 4160, 6212, 2118, 8264, 6218, 4171, 4172, 5474, 4178, 6230, 4185, 8282, 6842, 4193, 4196, 6248, 8300, 4214, 1385, 6266, 2171, 8318, 8319, 6276, 4232, 4235, 6284, 2754, 4238, 8336, 146, 4250, 157, 6302, 4256, 6305, 8354, 6307, 4260, 2213, 210, 4268, 6320, 8372, 4277, 4286, 192, 6338, 4291, 8390, 2764, 4298, 9591, 1058, 4304, 7544, 6354, 6356, 7886, 6358, 8408, 4132, 7683, 4319, 4322, 2277, 6374, 8425, 8426, 7100, 238, 4340, 5600, 6392, 1482, 8444, 4349, 2302, 4821, 4358, 263, 4361, 6410, 6411, 8462, 4376, 2436, 2330, 6428, 4382, 6432, 5852, 4394, 4397, 6446, 8584, 8498, 4403, 2782, 4412, 6464, 8516, 8246, 4424, 330, 6199, 4430, 2383, 6482, 8531, 6485, 4438, 2391, 740, 4445, 4448, 4450, 6500, 3814, 8552, 6888, 6510, 369, 4466, 6517, 6518, 376, 8570, 3818, 1429, 4484, 4487, 6536, 8588, 9697, 4502, 4503, 6554, 4508, 1434, 8606, 2800, 422, 4520, 8743, 6570, 6572, 6574, 4527, 8624, 4529, 2489, 4538, 6588, 8266, 6590, 8642, 4550, 2124, 4556, 6608, 8660, 4571, 4574, 6623, 6626, 8678, 698, 2542, 4592, 3496, 8690, 6644, 5404, 8696, 4609, 4610, 4613, 6662, 6663, 4616, 2569, 6666, 2818, 528, 4628, 6680, 4634, 2480, 2595, 2596, 5894, 4646, 2599, 2602, 2605, 4655, 2608, 2824, 2611, 2614, 4664, 2617, 2620, 2623, 2626, 4676, 2629, 2632, 6729, 4682, 2635, 2638, 2641, 2644, 2647, 6744, 100, 2650, 4700, 2653, 606, 2656, 4705, 2658, 2659, 2662, 2665, 4715, 2668, 4718, 2671, 104, 2674, 4883, 2677, 2680, 2836, 634, 2683, 3178, 2686, 4736, 2689, 4739, 6788, 790, 2695, 6252, 2698, 652, 2701, 2704, 8849, 4754, 2707, 2710, 4760, 2713, 2716, 8001, 2719, 4768, 2722, 3867, 4772, 2725, 6822, 2728, 2731, 4781, 2734, 687, 2737, 6835, 2740, 8885, 4790, 2743, 6841, 4794, 2747, 700, 2749, 6824, 8637, 2752, 4802, 2755, 2746, 4808, 2761, 6860, 2767, 433, 2770, 2773, 4823, 2776, 4826, 2779, 6878, 2785, 2788, 2854, 2791, 744, 2794, 1525, 4844, 2797, 6896, 2803, 6900, 2806, 2807, 2809, 8955, 2812, 4862, 2815, 4865, 6914, 2821, 4872, 4874, 2827, 2830, 4880, 2833, 6930, 8979, 6932, 789, 4886, 2839, 793, 2842, 2845, 2848, 4898, 2851, 6950, 1868, 2857, 4907, 2860, 2863, 9008, 2866, 4916, 2869, 6968, 2875, 2878, 4927, 4928, 2881, 6978, 836, 4934, 2887, 6986, 2893, 846, 2896, 2872, 6994, 2899, 4949, 4950, 4952, 2905, 3370, 2908, 2911, 2913, 2914, 2917, 2920, 4970, 2923, 4972, 2925, 2926, 2929, 2932, 2935, 2938, 4988, 2941, 4991, 2944, 2947, 2950, 7047, 2953, 2956, 5006, 2959, 2758, 2962, 5012, 2965, 2966, 2968, 2884, 9114, 2971, 2974, 5024, 2977, 6676, 5028, 2983, 5033, 2986, 2989, 2992, 5042, 2995, 2998, 952, 3001, 3004, 2890, 3007, 3566, 3010, 5060, 3013, 3014, 967, 3016, 8012, 3019, 3022, 9167, 3025, 3028, 5078, 3031, 7130, 3037, 5086, 3040, 3043, 3046, 5096, 3049, 3052, 1005, 3055, 7153, 3058, 3061, 3064, 5114, 3067, 3070, 3072, 3073, 3076, 2902, 3079, 3082, 5132, 3085, 3088, 5139, 6104, 7197, 5150, 3103, 1056, 2224, 7202, 7206, 7004, 5298, 5166, 5168, 8054, 7220, 3125, 9273, 522, 2012, 5184, 5186, 7238, 5192, 8902, 514, 5204, 1111, 7256, 7259, 3549, 9061, 5222, 7274, 9326, 3944, 7286, 5239, 5240, 1145, 7292, 5245, 7019, 9750, 5257, 5258, 1164, 7310, 7312, 7022, 5276, 3231, 7328, 9379, 1189, 1196, 5294, 7346, 1203, 4980, 1210, 5312, 1217, 7364, 7365, 1224, 1231, 5328, 3281, 5330, 3284, 7382, 9432, 7375, 5340, 1245, 5348, 5351, 7400, 1259, 1234, 1266, 5366, 1273, 7418, 6698, 1280, 7040, 1238, 1287, 5384, 3337, 7436, 9485, 1294, 899, 1301, 5402, 1308, 7454, 3973, 560, 1315, 7464, 5417, 5418, 1323, 5420, 7471, 7472, 1329, 1336, 1588, 3387, 5438, 5439, 7490, 3638, 1350, 5978, 1357, 5456, 5457, 7508, 1252, 1371, 1376, 6032, 1378, 7524, 7526, 3432, 6716, 7058, 1392, 3443, 5492, 1399, 5496, 1406, 7553, 5506, 3459, 1412, 1413, 5510, 7562, 1420, 1427, 3477, 1945, 5528, 7577, 5530, 7580, 6042, 581, 1441, 1448, 1449, 5546, 9644, 7598, 1455, 1462, 3657, 5563, 5564, 1469, 7616, 3522, 1476, 1270, 5574, 3530, 1483, 5582, 4344, 1490, 6734, 2980, 5595, 3548, 1501, 1504, 5712, 7652, 7184, 1511, 6396, 1518, 3567, 5616, 5618, 5621, 7670, 1532, 1535, 3584, 1539, 5636, 7688, 1546, 1553, 3602, 5652, 5654, 4697, 1560, 7706, 7076, 3612, 5722, 1567, 3620, 5669, 1574, 5672, 8796, 7724, 1581, 5684, 3637, 1590, 7736, 5690, 1595, 7742, 6752, 1602, 6941, 7094, 3655, 3656, 1609, 9803, 5708, 7778, 1616, 611, 3342, 1623, 7760, 3674, 5726, 5730, 1637, 1641, 3692, 7789, 5744, 1651, 7796, 3702, 3192, 1658, 3708, 3710, 9856, 1665, 5762, 7814, 1672, 1644, 5262, 5773, 3726, 1679, 3728, 5780, 1686, 7832, 7108, 4662, 1693, 1694, 5061, 3746, 3747, 1700, 5798, 2648, 284, 7850, 1707, 6770, 5808, 7112, 1714, 3764, 8478, 5816, 1721, 7868, 8138, 1728, 8480, 5828, 3782, 1735, 5834, 1742, 3792, 1747, 1749, 7895, 3800, 1756, 1497, 7904, 1763, 5862, 3815, 1768, 1770, 468, 5870, 1777, 7922, 6782, 1784, 5881, 3836, 1322, 5886, 1791, 5888, 7940, 878, 1798, 1800, 7948, 1805, 3854, 3857, 5906, 1812, 7958, 7630, 2692, 1819, 3034, 3872, 1826, 5924, 3878, 7976, 1833, 5934, 1840, 3890, 5942, 1847, 7994, 3899, 1630, 1853, 1854, 5951, 3904, 1857, 3908, 1861, 5960, 5964, 3920, 1875, 3926, 1882, 5775, 8030, 1889, 5987, 3941, 1896, 316, 5996, 1903, 8048, 1906, 3390, 1910, 3962, 1343, 1917, 6014, 8066, 1924, 6806, 7148, 1931, 3980, 9538, 3983, 7634, 1938, 8084, 6040, 3993, 1946, 3998, 1952, 6050, 4004, 8102, 1959, 8107, 5106, 1966, 4016, 6068, 1973, 8120, 4025, 4026, 1980, 475, 4034, 1987, 6086, 1994, 6093, 4046, 2001, 4052, 2008, 8156, 2015, 8160, 4067, 4070, 6120, 6122, 8174, 4079, 6129, 4082, 2035, 7166, 7842, 4088, 1364, 6140]

a.sort()

n = len(a)-1
L = [[1]*(n+1) for i in range(n+1)]

longest = 2

for j in range(n-1,0,-1):
    i,k = j-1, j+1
    while i>= 1 and k<=n:
        if a[i]+a[k] < 2*a[j]:
            k += 1
        elif a[i]+a[k] > 2*a[j]:
            L[i][j] = 2
            i -= 1
        else:
            L[i][j] = L[j][k]+1
            longest = max(longest, L[i][j])
            i, k = i-1, k+1

    while i >= 1:
        L[i][j] = 2
        i -= 1

print longest

0 Helpful 0 Interesting 0 Brilliant 0 Confused
Michael Mendrin
Jul 21, 2016

First I sorted the 931 numbers, then made a list of 930 differences between successive numbers, and then I eyeballed the list and noticed a lot of 18s in it--more so than either 3 or 7 or 53. That led me to the discovery of the sequence of 288 numbers that differ by 18.

List

Does this minimize the time complexity in this?

0 Helpful 0 Interesting 0 Brilliant 0 Confused

How do you quantify your time complexity?

Pi Han Goh - 4 years, 10 months ago

Log in to reply

Well, that was my point. Still, I got away with eyeballing because the list is only 931 numbers long, instead of 931,000 numbers long. Then probably we should worry about time complexity of any computer method used.

Michael Mendrin - 4 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...