Tips for applying Back Tracking or Complete Search.

Tips

Suppose that your Complete Search takes ~10 Seconds on worst-case and TL is 10 Seconds, and the judge gives TLE, then you should tweak the code instead of designing a new algorithm.

Tip 1: Filtering versus Generating:

Programs that examine lots of(if not all) candidate solutions and choose the ones that are correct are called filters.

Programs that build the solutions and prune out invalid partial solutions -> generators.

Usually, 'generator' programs are easier to implement when written recursively as it gives us greater flexibility for pruning the search space...

Tip 2: Prune Infeasible?Inferior Search Space Early

Most often, we may encounter a partial solution that will never lear to a full solution. We can keep a note of it and prune the search space there and explore other parts of the search space. As a rule of thumb, the earlier you can prune the search space, the better.

Tip 3: Utilize Symmetries

Some problems have symmetries, and this can be taken advantage of.

In Cp, this is usually not the best way (we want to minimize the bugs). If the gain obtained by dealing with symmetry is not significant in solving the problem, just ignore this tip.

Tip 4: Pre-Computation a.k.a. Pre-Calculation

Sometimes it is helpful to generate tables or other DS that accelerate the lookup of a result prior to the execution of the program itself. This is called Pre-Computation.

Tip 5: Optimizing your source code

1. Use C++ instead of Java. C++ gets implemented faster in C++ than in Java. Few judges give Java users extra time for this lag though.

2. User scanf/printf rather than cin/cout.

3. Access a 2D array in a row-major fashion(row by row) rather than in a column-major fashion. Multidimensional arrays are stored in row-major order in memory.

4. Bit manipulation on the built-in integer data types is more efficient than index manipulation in an array of booleans. If we need more than 64 bits, use the C++ STL bitset rather than vector<bool>.

5. Preer arrays over vectors if memory is not an issue. 

8. Declare most data structures(especially the bulky ones) by placing them in the global scope. And clear it as and when needed.

9. If there is an option to write code iteratively or recursively, choose the iterative version.

10. Array access costs. If you need to access A[i] many times, it may be good to store it in temp=A[i] and work with it instead.

11. Use macros or inline functions.

12. C-style character arrays are faster than string.

Tip 7:

Using better DS and Algo will beat all other tips.

Disclaimer: All my notes are based on the Competetive Programming 3 book.