Question about an ACM-ICPC live archive problem

[pigwoley]

This one, 3079 - Anti-prime sequences, is from the East Central (North America) regionals.

My friend and I decided to take a backtracking approach, but apparently it isn't fast enough. What is the correct algorithm, and what did we do wrong?

Code: Select all

#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <map>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

int n,m,d;
vector<int> IsNotPrime(0);
int found;
int seqsize;

#define in cin

void Sieve(vector<int> &PrimeTable) 
{
	PrimeTable[0] = 1;
	PrimeTable[1] = 1;
	PrimeTable[2] = 0;
	for(unsigned int j = 2; j <= PrimeTable.size(); ++j)
	{
		if(!PrimeTable[j])
		{
			unsigned int k = j+j;
			while(k < PrimeTable.size())
			{
				PrimeTable[k] = 1;
				k += j;
			}
		}
	}
}

int BackTrack(int pos, vector<int> &current, vector<int> &used)
{
	if(pos == seqsize)
	{
		cout << current[0];
		for(unsigned int i = 1; i < pos; ++i )
		{
			cout << ",";
			cout << current[i];
		}
		cout << endl;
		found = 1;
		return 1;
	}
	
	for(int i = n; i <= m; ++i)
	{
		if(used[i])
			continue;
			
		int accum = i;
		for(int q = pos-1; q>=max((int)(pos-d+1),0); --q)
		{
			accum += current[q];
			if(!IsNotPrime[accum])
				goto happy;
		}
			 
		current[pos] = i;
		used[i] = 1;
		if(BackTrack(pos+1, current, used))
			return 1;
		used[i] = 0;
		current[pos] = -1;
		
	happy:; 
	} 
	
	return 0;
}


int main() 
{
	//ifstream in("in.txt");
	int PrimeSize = 0;
	
	//11 might be too much
	for(int j = 1000; j > 1000-11; --j)
		PrimeSize += j;
		
	IsNotPrime.resize(PrimeSize);
	Sieve(IsNotPrime);
	
	

	vector<int> MyAwesomeVector(1007);
	n = 1;
	m = 2;
	d = 10;
	while(1)
	{
		in >> n >> m >> d;
		if(n==0)
			break;
	
		
		seqsize = m-n+1; 
		found = 0;
		vector<int> u(1007);
		BackTrack(0, MyAwesomeVector, u);
		if(!found)
			cout << "No anti-prime sequence exists." << endl;
	}
	 
	return 0; 
}