Problem with contest program

[CoolGamer48]

I'm writing a program for a contest (it's a demo, not the actual thing - so I'm not cheating by asking for help - and my question isn't directly related to the algorithm they want anyway). To submit a program, you send them the .cpp file, and they execute it on their server (automatically) for a number of test trials (around 10), and show you the results. This problem has 11 trials. For the first five trials, the program runs fine. However, the sixth run of the program fails, and it throws std::bad_alloc (I'm guessing its caused by vector::push_back - the only other things I'm using from std are file streams and strings). Then, trial 7 works fine. Trials 8 and 9 failed, same reason. Trial 10's runtime was too long (it was stopped at around 1.5 secs, shouldn't go over 1 second), and trial 11 had the bad_alloc again.

I wanted to see exactly where the bad_alloc was occurring, so I copied the test input data for trial 6 into the test input file on my machine, and ran the program. I didn't get bad_alloc, but the program didn't end (for the time I ran it, maybe 10 seconds - I'm going to try leaving it for longer while outputting debug info).

Anyway - this is my assumption of what's going on, tell me if I'm right:
On the virtual machine on the competition's servers, the program is only given the amount of memory that they think it needs to execute. So, my program is memory inefficient, and on their machine, it runs out of memory. However, on my machine, the memory isn't limited, so it keeps using it up, and so instead of getting bad_alloc, the program just runs for a long time. Is this a correct assumption?

[iamthwee]

I would surmise you're using a brute force solution when perhaps a dynamic solution exists.

This is quite common on online contests such as topcoder etc.

[VernonDozier]

I'm writing a program for a contest (it's a demo, not the actual thing - so I'm not cheating by asking for help - and my question isn't directly related to the algorithm they want anyway). To submit a program, you send them the .cpp file, and they execute it on their server (automatically) for a number of test trials (around 10), and show you the results. This problem has 11 trials. For the first five trials, the program runs fine. However, the sixth run of the program fails, and it throws std::bad_alloc (I'm guessing its caused by vector::push_back - the only other things I'm using from std are file streams and strings). Then, trial 7 works fine. Trials 8 and 9 failed, same reason. Trial 10's runtime was too long (it was stopped at around 1.5 secs, shouldn't go over 1 second), and trial 11 had the bad_alloc again.

I wanted to see exactly where the bad_alloc was occurring, so I copied the test input data for trial 6 into the test input file on my machine, and ran the program. I didn't get bad_alloc, but the program didn't end (for the time I ran it, maybe 10 seconds - I'm going to try leaving it for longer while outputting debug info).

Anyway - this is my assumption of what's going on, tell me if I'm right:
On the virtual machine on the competition's servers, the program is only given the amount of memory that they think it needs to execute. So, my program is memory inefficient, and on their machine, it runs out of memory. However, on my machine, the memory isn't limited, so it keeps using it up, and so instead of getting bad_alloc, the program just runs for a long time. Is this a correct assumption?

Sounds like a reasonable assumption. You could easily have a program that ran out of memory in one environment with limited memory resources, but not run out in an environment with more resources. push_back is going to result in a bad_alloc error when you run out of memory. I got about 134,000,000 allocations in the program below before hitting the bad_alloc exception, but it could easily vary with different systems.

#include <vector>
#include <string>
#include <iostream>
using namespace std;

int main ()
{
    vector <int> v;
    cout << "Absolute maximum allocations = " << v.max_size() << endl;

    int counter = 0;
    bool done = false;
    while(!done)
    {
        try
        {
              v.push_back(counter);
              counter++;
        }
        catch (std::bad_alloc)
        {
              done = true;
              cout << "Number of allocations = " << counter << endl;
              cout << "Bad allocation" << endl;
        }
    }
    
    cout << "Done with program" << endl;
    return 0;
}

[CoolGamer48]

I would surmise you're using a brute force solution when perhaps a dynamic solution exists.

This is quite common on online contests such as topcoder etc.

My solution may be a brute force - I'm not entirety sure. I would have preferred to think of the algorithm on my own - but this is the basic structure of the problem/program, is it a brute force?

The problem:
You're given x number of lowercase characters and a password length. You need to find all the valid passwords you can construct from the given letters.
valid passwords:
- have at least one vowel
- have at least two consonants
- have characters in alphabetical order, ie: abc is ok, bac, or cab, is not

You need to then alphabetize the results you get and print up to 25000 of them. Here's how I go about it (I'm away from home so I don't have the code with me).

Find all the possible combos given the letters.

Weed out the incorrect ones

Alphabetize what's left.

Output up to 25000

Is this a brute force method? If so, what would be a possible dynamic method (if you can sort of hint at the answer or put me on the right track without giving me the answer, that'd be nice).

[VernonDozier]

My solution may be a brute force - I'm not entirety sure. I would have preferred to think of the algorithm on my own - but this is the basic structure of the problem/program, is it a brute force?

The problem:
You're given x number of lowercase characters and a password length. You need to find all the valid passwords you can construct from the given letters.
valid passwords:
- have at least one vowel
- have at least two consonants
- have characters in alphabetical order, ie: abc is ok, bac, or cab, is not

You need to then alphabetize the results you get and print up to 25000 of them. Here's how I go about it (I'm away from home so I don't have the code with me).

Find all the possible combos given the letters.

Weed out the incorrect ones

Alphabetize what's left.

Output up to 25000

Is this a brute force method? If so, what would be a possible dynamic method (if you can sort of hint at the answer or put me on the right track without giving me the answer, that'd be nice).

I'd say that was overly brute-force. One, assume that by "combos" you mean "combinations" rather than "permutations". If you are calculating all permutations, that's definitely too brute-force since you know in advance these are going to be alphabetized. So if you have a vector and you are adding both "ab" and "ba" onto that vector, definitely don't. At the very minimum, only add "ab", but you really shouldn't add "ab" at all. Test for legality BEFORE pushing a potential solution onto the vector. There's no need to add something to the vector that you are going to take off later. If you only add actual solutions to your vector, that may solve your bad_alloc right there.

A good algorithm, I think, will actually work in such a way that the solutions are actually added to the vector already in alphabetical order, so there is no need to sort. I would also NOT generate all possible combinations (let alone permutations). Some you know right away are illegal (i.e. all consonants), so don't even generate them. Start with a vowel and two consonants, and THEN generate all combinations of the remaining letters. Those will all be legal combinations (you'll need to sort the letter into alphabetical order before adding it to the vector, but it'll be a legal combination of letters).

[iamthwee]

I would definitely agree with the above. There are a lot of shortcuts you can apply to drastically cut out the number of calculations you need to do.

Have another think about it.

[CoolGamer48]

I got home recently, and I'll try to make the program more memory efficient, but I just let the program run for 40 mins with one of the failed sets of test data, and it didn't get past the portion where it finds all the possible combinations you can have, so I'm thinking there may be some other issue, but I'll try to make it less of a brute-force and see what happens.

Here's the code, if anyone cares to read it:

#include <fstream>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int password_length;
int num_chars;
vector<string> possible_combos;
char* chars;

void FindAll(string current,vector<int> char_ids_used)
{
	if(current.length() == password_length)
	{
		possible_combos.push_back(current);
		return;
	}

	for(int i = 0; i < num_chars;i++)
	{
		bool used = false;
		for(int j = 0;j < char_ids_used.size();j++)
		{
			if(i == char_ids_used[j])
				used = true;
		}
		if(!used)
		{
			vector<int> my_used = char_ids_used;
			my_used.push_back(i);
			FindAll(current + chars[i],my_used);
		}
	}
}

bool IsVowel(char c)
{
	switch(c)
	{
	case 97:
	case 101:
	case 105:
	case 111:
	case 117:
		return true;
	}

	return false;
}

bool HasVowel(string str)
{
	int length = str.length();
	for(int i = 0;i < length;i++)
	{
		if(IsVowel(str[i]))
			return true;
	}

	return false;
}

bool HasTwoConsonants(string str)
{
	int numConsonants = 0;
	
	int length = str.length();
	for(int i = 0;i < length;i++)
	{
		if(!IsVowel(str[i]))
			numConsonants++;
	}

	if(numConsonants >= 2)
		return true;

	return false;
}

bool InAlphaOrder(string str)
{
	for(int i = 1;i < str.length();i++)
	{
		char prev = str[i-1];
		char current = str[i];
		if(int(prev) > int(current))
			return false;
	}

	return true;
}

bool InAlphaOrder(string first,string second)
{
	int length = first.length();
	for(int i = 0;i < length;i++)
	{
		if(int(first[i]) < int(second[i]))
			return true;
		else if(int(first[i]) > int(second[i]))
			return false;
	}

	return true;//strings are the same
}

int main()
{
	ofstream debug("passwd.debug");

	debug << "Program start\n";
	cout << "Program start\n";
	
	debug << "Reading data from passwd.in\n";
	cout << "Reading data from passwd.in\n";
	ifstream fin("passwd.in");
	fin >> password_length >> num_chars;
	chars = new char[num_chars];
	for(int i = 0;i < num_chars;i++)
		fin >> chars[i];

	fin.close();
	debug << "Done reading\n";
	cout << "Done reading\n";

	debug << "Finding possible combos\n";
	cout << "Finding possible combos\n";
	for(int i = 0;i < num_chars;i++)
	{
		vector<int> used_chars;
		used_chars.push_back(i);
		string current;
		current = chars[i];
		FindAll(current,used_chars);
	}
	debug << "Done finding\n";
	cout << "Done finding\n";

	debug << "Validating results\n";
	cout << "Validating results\n";
	int num_combos = possible_combos.size();
	vector<string> valid_combos;
	for(int i = 0;i < num_combos;i++)//added i < 25001
	{
		if(!InAlphaOrder(possible_combos[i]))
			continue;
		if(!HasVowel(possible_combos[i]))
			continue;
		if(!HasTwoConsonants(possible_combos[i]))
			continue;

		valid_combos.push_back(possible_combos[i]);
	}
	debug << "Done validating\n";
	cout << "Done validating\n";

	possible_combos.clear();//all valid results have been copied to the valid_combos vector

	debug << "Alphabetizing results\n";
	cout << "Alphabetizing results\n";
	for(int i = 1;i < valid_combos.size() && i <= 25000;i++)
	{
		if(!InAlphaOrder(valid_combos[i-1],valid_combos[i]))
		{
			string temp = valid_combos[i];
			valid_combos[i] = valid_combos[i-1];
			valid_combos[i-1] = temp;

			for(int j = i-1;j > 0;j--)
			{
				valid_combos[j-1];
				valid_combos[j];
				if(InAlphaOrder(valid_combos[j-1],valid_combos[j]))
					break;
				else
				{
					temp = valid_combos[j];
					valid_combos[j] = valid_combos[j-1];
					valid_combos[j-1] = temp;
				}
			}
		}
	}
	debug << "Done alphabetizing\n";
	cout << "Done alphabetizing\n";

	debug << "Outputting results\n";
	cout << "Outputting results\n";
	ofstream fout("passwd.out");
	int size = valid_combos.size();
	if(size > 25000)
		size = 25000;
	for(int i = 0;i < size;i++)
	{
		fout << valid_combos[i] << "\n";
	}

	debug << "Done outputting\n";
	cout << "Done outputting\n";

	debug << "Program end\n";
	cout << "Program end\n";

	fout.close();

	return 0;
}

[CoolGamer48]

Alright, I added the validations before I store the combo in a vector, and that did get rid of the bad_alloc. However, now I'm having issues with runtime. All of the tests that failed before still all fail, it's just that now they fail due their runtime passing one second. I'll try to make the program more efficient as far as runtime, but I still think that there's something up with the brute-force logic I have in place. I can't imagine that one of the tests would take 40+ mins. while others would take fractions of seconds. Though perhaps that 's because I'm not used to these types of problems. I'll look into both improving my logic and seeing if there are issues with it as it is currently implemented.

[VernonDozier]

Question: Can you have more than one of the same character or must all characters be unique? If you can have multiple characters (i.e. aaert), that's a harder program, I would imagine. Or must all characters be unique (i.e. aert)?

[CoolGamer48]

Question: Can you have more than one of the same character or must all characters be unique? If you can have multiple characters (i.e. aaert), that's a harder program, I would imagine. Or must all characters be unique (i.e. aert)?

I thought of that too (while I was out), and I thought of a possible solution. I just checked, and yes, the chars given in the input must be unique. It gave me an idea:

Right after you get the input chars, alphabetize them. Then, go to the first char, and cycle through all the possible combos, but stop if you find that any of the chars you are adding to the string make the string not be in alphabetical order. That will make each output be in alphabetical order, and the outputs themselves will be organized alphabetically.

That logic might be slightly flawed, I just spurred it out. As I'm implementing it I might see any flaws in it, but I think I'm on the right track.

Was this what you were thinking of?

[CoolGamer48]

I got it. I was pretty much on the right track with my theory. The program executes fine for all 11 tests now. If anyone cares, here is the condensed and more efficient program:

#include <fstream>
#include <string>
#include <vector>
using namespace std;

int password_length;
int num_chars;
vector<string> possible_combos;
char* chars;
bool limit_reached = false;


bool IsVowel(char c)
{
	switch(c)
	{
	case 97:
	case 101:
	case 105:
	case 111:
	case 117:
		return true;
	}

	return false;
}

bool HasVowel(string str)
{
	int length = str.length();
	for(int i = 0;i < length;i++)
	{
		if(IsVowel(str[i]))
			return true;
	}

	return false;
}

bool HasTwoConsonants(string str)
{
	int numConsonants = 0;
	
	int length = str.length();
	for(int i = 0;i < length;i++)
	{
		if(!IsVowel(str[i]))
			numConsonants++;
	}

	if(numConsonants >= 2)
		return true;

	return false;
}

void FindAll(string current,int last_char_id)
{
	if(limit_reached)
		return;

	if(current.length() == password_length)
	{
		if(!HasVowel(current))
			return;
		if(!HasTwoConsonants(current))
			return;
		
		possible_combos.push_back(current);
		if(possible_combos.size() == 25000)
			limit_reached = true;
		return;
	}

	for(int i = last_char_id+1; i < num_chars;i++)//check first part of the for
	{
		FindAll(current + chars[i],i);
	}
}

int main()
{
	ifstream fin("passwd.in");
	fin >> password_length >> num_chars;
	chars = new char[num_chars];
	for(int i = 0;i < num_chars;i++)
		fin >> chars[i];

	fin.close();

	for(int i = 1;i < num_chars;i++)
	{
		if(int(chars[i-1]) > int(chars[i]))
		{
			char temp = chars[i-1];
			chars[i-1] = chars[i];
			chars[i] = temp;
			for(int j = i - 1;j > 0;j--)
			{
				if(int(chars[j-1]) > int(chars[j]))
				{
					temp = chars[j-1];
					chars[j-1] = chars[j];
					chars[j] = temp;
				}
				else
					break;
			}
		}
	}

	for(int i = 0;i < num_chars;i++)
	{
		string current;
		current = chars[i];
		FindAll(current,i);
	}

	ofstream fout("passwd.out");
	int size = possible_combos.size();
	for(int i = 0;i < size;i++)
	{
		fout << possible_combos[i] << "\n";
	}

	fout.close();

	return 0;
}

Thanks for all the help.