USACOs Arithmetic Progression

Question

I was working on the USACO problem arithmetic progression.

You can see the problem (and a solution) here - http://massivealgorithms.blogspot.com/2015/08/arithmeticprogressions-codetrick.html

My code successfully runs for the first 7 test cases. However, once it reaches test case 8 (22,250) it times out. What modifications should I make to make my code more efficent? Most solutions I found online were also o(m^2*n) complexity, so I'm not sure what I need to change.

Here is my code:

 //#include "stdafx.h"
    #include <iostream>
    #include <fstream>
    #include <string>
    #include <algorithm>
    #include <vector>
    using namespace std;

int main()
{
    ofstream fout("ariprog.out");
    ifstream fin("ariprog.in");
    int n, m;
    fin >> n >> m;
    int bisquare[125001] = {};

    for (int a = 0; a <= m; a++) {
        for (int b = a; b <= m; b++) {
            bisquare[(a*a) + (b*b)] = 1;
        }
    }
    int max = 2 * m*m;
    int value;
    bool tb = false;
    pair<int, int> all[125001];
    int yeah = 0;
    for (int s = 0; s <= max/2; s++) {              
        for (int i = 1;i<=max/2; i++) {
            for (int x = 0; x < n; x++) {
                value = s + x*i;

                if (value > max) {
                    tb = true;
                    break;
                }
                if (!bisquare[value]) break;
                if (bisquare[value] && x==n-1)  {
                    all[yeah] = make_pair(i,s);
                    yeah++;
                }
            }
            if (tb) {
                tb = false;
                break;
            }
        }
    }
    sort(all,all+yeah);
    for (int i = 0; i < yeah; i++) {
        fout << all[i].second << " " << all[i].first << endl;
    }
    if (all[0].first == 0) {
        fout << "NONE" << endl;
    }
}

Answer 1

Faster searching

Suppose you have an array filled with either 1 and 0, and you are trying to search for a consecutive sequence of twenty 1's in a row. The way you are doing it is like this:

111111111111111100001111111110111011111111
^               ^
|...............|
start here      end here  length = 15, not long enough, so move on

Next iteration:

111111111111111100001111111110111011111111
 ^              ^
 |..............|
 start here     end here  length = 14, not long enough, so move on

Next iteration:

111111111111111100001111111110111011111111
  ^             ^
  |.............|
  start here    end here  length = 13, not long enough, so move on

As you can imagine, the above algorithm is not very efficient because you are wasting time looking at the same array values over and over again. The above can take up to \$O(M*N)\$ time, where \$M\$ is the length of the string and \$N\$ is the length of the sequence you are searching for.

Instead of restarting your search from the next index, you should be restarting your search from just past the zero you found:

111111111111111100001111111110111011111111
^               ^
|...............|
start here      end here  length = 15, not long enough, so move on

Next iteration:

111111111111111100001111111110111011111111
                 ^
                 |
                 Restart here, not back there

By doing this, the search now only takes \$O(M)\$ time. You could do even better by mimicking the Boyer Moore string search algorithm and skipping to the end and searching backwards, like this:

111111111111111101111111111110111011111111
^
|
start here

111111111111111101111111111110111011111111
                   ^
                   |
                   jump 19 spots ahead and search backwards

111111111111111101111111111110111011111111
                ^
                |
                Found a zero here

111111111111111101111111111110111011111111
                 ^
                 |
                 Restart here

This is still an \$O(M)\$ algorithm in the worst case, but it can be as fast as \$O(M/N)\$ in the best case (an array filled with all 0s).

Loop rearrangement

The way you have set up your loops does not lend itself to doing the faster searching methods. You will need to rearrange your loops in order to be able to restart your searches properly. I suggest you move your x loop from being the innermost loop to being the outermost loop. Then you may find that the two other loops collapse into a single search loop.