
This is a rewrite of this recipe by it4.kp.
Problem
It's common for a solution to fail due to a small mistake or even misprint that was not found during testing. Problem statements usually don't provide enough examples, and inventing them by hand still can miss a bug. One way to detect them in semiautomatic mode is to test your solution on multiple small random test cases using an alternative bruteforce solution.
Solution
Bruteforce is the most natural way of solving many problems. Unfortunately, this straightforward method is not appropriate in absolute majority of TopCoder problems due to tight time constraints, so more complicated, more algorithmic and more efficient solutions are required. However, if you want to test your solution on some small test cases, using another bruteforce solution is a good way to automate the testing.
This is done much as the name implies  you write a local bruteforce solution, run it on a set of small test cases and compare the returns of this solution and the one that is being tested. Since bruteforce solution is simpler, it's also less errorprone, so if the results differ on certain test case, it's a reason to start a more detailed investigation on the reasons of the difference.
Discussion
The very first thing to note is that this testing technique is nowhere near a panacea for all problems. Sometimes writing a bruteforce solution can be to tricky to waste your time implementing it. Also, your solution can exceed time or memory limit, or suffer from overflow on large test cases, which errors this technique doesn't detect. Nevertheless, it can be useful in general.
Thus, if you submitted a solution and there is no much time left to try another problem, consider testing your solution as described above and shown below. This makes sense for problems which use a rather complicated algorithm you're not so sure about, or for problems with lengthy code which is likely to have a bug. Not much sense to test in this way problems which are a short DP, or are based on a thoroughly tested prewritten code. The bruteforce solution mustn't be optimized or anything  it has just to be short and clean enough to be sure that it's correct.
To make this technique really useful, one has to automate applying it as much as possible: write a customizable test case generator and a tool to run two solutions against the same test cases and compare the results, so that during the contest you have only to write the two solutions and to tune test case generation.
Now, to the examples. Problem statement of ForbiddenStrings contains only three example test cases  clearly too little for a decent testing. The correct solution involved getting recursive formula, but you could easily write a bruteforce one that would iterate through all strings of length n and pick nonforbidden ones:
int brute(int n){
int total = 1, cnt_forbidden = 0;
// Count the total number of strings of letters A, B, C which length is n.
// Apparently, it's 3^n
for (int i=1; i<=n; ++i) total *= 3;
// Iterate through all such strings
for (int i=0; i<total; ++i){
char s[20];
int cur = i; // cur is the representation of current string in 3base numeral system
for (int j=0; j<n; ++j) {
s[j] = cur%3 + 'A';
cur /= 3;
}
bool forbidden = false; // Is current string forbidden?
for (int j=2; j<n; ++j) if (s[j]!=s[j1] && s[j]!=s[j2] && s[j1]!=s[j2]) {
forbidden = true;
break;
}
// Increment the number of forbidden strings
if (forbidden) ++cnt_forbidden;
}
// Return the number of unforbidden strings
return total  cnt_forbidden;
}
Another example can be PalindromePhrases: the correct solution involves fairly complex computations, based on dynamical programming; but if we limit ourselves with the sets of 1 to 6 random words, we can just try all possible phrases and count those of them that are palindromes:
int brute(vector<string> words){
int n = words.size();
set<string> palindromic_phrases;
// Iterate through all permutations of words
sort(words.begin(),words.end());
do {
// Iterate through all nonempty subsets of words
for (int mask = 1; mask < (1<<n); ++mask) {
string phrase = "";
string phrase_without_spaces = "";
for (int j = 0; j < n; ++j) if (mask & (1<<j)) {
// jth word is included in the current subset
if (phrase != "") phrase += " ";
phrase += words[j];
phrase_without_spaces += words[j];
}
if (is_palindrome(phrase_without_spaces))
palindromic_phrases.insert(phrase);
}
} while (next_permutation(words.begin(),words.end()));
return palindromic_phrases.size();
}
