Hi. I was solving this question: http://usacotraining.blogspot.in/2014/02/problem-143-arithmetic-progressions.html
My question is very strange. I used pure brute force. The vector ‘bis’ stores all the bisquares upto ‘m’ and the array ‘a’ marks whether ‘i’ is bisquare or not. Since m <= 250 and n <= 25. If we check the number of computations for n=25 and m=250 then they would be roughly (250250)^225. Which would be of the order 10^10. The timelimit of the question is 5 sec. What surprises me is that my code unexpectedly passed and showed the correct output within 2 seconds! Can anyone explain me how? Either I am going somewhere wrong with my math or there is something new to learn.
Also, the test cases were not weak. The last input set was indeed n=25 and m=250.
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<cstdio>
#include<cstring>
#include<string>
#include<cstdlib>
#include<iomanip>
#include<queue>
#include<stack>
#include<cmath>
#include<utility>
using namespace std;
int a[125005] = {0};
int n,m;
struct prog {
int a;
int d;
};
bool func(int n) {
if(n > 2*m*m) return false;
if(a[n] == 0) return false;
return true;
}
bool myfunc(prog i, prog j) {
if(i.d < j.d) return true;
if(i.d == j.d && i.a < j.a) return true;
return false;
}
int main() {
ifstream fin("ariprog.in");
ofstream fout("ariprog.out");
fin >> n >> m;
vector<int> bis;
bis.push_back(0);
for(int i = 0;i <= m;i++) {
for(int j = i;j <= m;j++) {
if(i == j && i == 0) continue;
a[i*i+j*j] = 1;
}
}
for(int i = 0;i < 125005;i++) {
if(a[i] == 1) bis.push_back(i);
}
sort(bis.begin(),bis.end());
int k = bis.size();
vector<prog> ans;
//cout << bis.size() << endl; **Checking the number of elements in 'bis'**
//They came out to be ~21000 when m=250.
int iterations = 0; //To check how many iterations were done
for(int i = 0;i < k;i++) {
for(int j = i+1;j < k;j++) {
int d = bis[j]-bis[i];
int temp = bis[j];
bool check = true;
for(int ctr = 1;ctr < n-1;ctr++) {
iterations++; //Checking iterations
temp += d;
if(!func(temp)) {
check = false;
break;
}
}
if(check == true) {
prog temp2;
temp2.a = bis[i];
temp2.d = d;
ans.push_back(temp2);
}
}
}
sort(ans.begin(),ans.end(),myfunc);
if(ans.size() == 0) fout << "NONE" << endl;
for(int i = 0;i < ans.size();i++)
fout << ans[i].a << " " << ans[i].d << endl;
//cout << iterations << endl; //Came out to be around ~10^10
//system("PAUSE");
return 0;
}