This page mainly lists some useful tips for programming contests.
Taking Advantage of Locality
Locality refers to the tendency of a program to reference data items adjacent to other data items referenced recently, or the recently referenced data items themselves. Locality is divided into temporal locality and spatial locality.
For details, see Loop Unroll, Code Layout Optimizations, and other content.
Loop Macros
The following code can be simplified using a macro:
for (int i = 0; i < N; i++) {
// Omit the loop body
}
// Simplify with a macro
#define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x)
// This simplifies loop code to `f(i, 0, N)`. For example:
// a is a STL container
f(i, 0, a.size()) { ... }
Another relatively useful macro is also recommended:
#define _rep(i, a, b) for (int i = (a); i <= (b); ++i)
Use Namespaces Effectively
Using namespaces can make programs more readable and facilitate debugging.
Example: NOI 2018 Dragon Slayer
// 40-point partial-score code for NOI 2018 Dragon Slayer
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
long long n, m, a[100005], p[100005], aw[100005], atk[100005];
namespace one_game {
// Variables can also be declared inside a namespace
void solve() {
for (int y = 0;; y++)
if ((a[1] + p[1] * y) % atk[1] == 0) {
cout << (a[1] + p[1] * y) / atk[1] << endl;
return;
}
}
} // namespace one_game
namespace p_1 {
void solve() {
if (atk[1] == 1) { // solve 1-2
sort(a + 1, a + n + 1);
cout << a[n] << endl;
return;
} else if (m == 1) { // solve 3-4
long long k = atk[1], kt = ceil(a[1] * 1.0 / k);
for (int i = 2; i <= n; i++)
k = aw[i - 1], kt = max(kt, (long long)ceil(a[i] * 1.0 / k));
cout << k << endl;
}
}
} // namespace p_1
int main() {
int T;
cin >> T;
while (T--) {
memset(a, 0, sizeof(a));
memset(p, 0, sizeof(p));
memset(aw, 0, sizeof(aw));
memset(atk, 0, sizeof(atk));
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> p[i];
for (int i = 1; i <= n; i++) cin >> aw[i];
for (int i = 1; i <= m; i++) cin >> atk[i];
if (n == 1 && m == 1)
one_game::solve(); // solve 8-13
else if (p[1] == 1)
p_1::solve(); // solve 1-4 or 14-15
else
cout << -1 << endl;
}
return 0;
}
Use Macros for Debugging
When testing locally, programmers often add some debugging statements. When submitting to an OJ, to prevent the output of debugging statements from affecting the OJ from judging the program's output, all of them must be removed, which can take considerable time. In this situation, macros can be defined to save time. The general program framework is as follows:
#define DEBUG
#ifdef DEBUG
// do something when DEBUG is defined
#endif
// or
#ifndef DEBUG
// do something when DEBUG isn't defined
#endif
#ifdef checks whether this identifier has been defined by a #define in the program; if it has, the following statements are executed. #ifndef executes the statements when this identifier has not been defined.
Thus, writing the debugging code inside #ifdef DEBUG and the actual submission code inside #ifndef DEBUG makes local testing convenient. When submitting the program, you only need to comment out the line #define DEBUG. You can also leave the identifier undefined in the program and define the DEBUG identifier through the -DDEBUG compilation option. This way, you do not need to modify the program when submitting it.
Many OJs enable the -DONLINE_JUDGE compilation option. Making good use of this feature can save considerable time.
Differential Testing
Differential testing is a method for testing or debugging: it checks a program's correctness by comparing the outputs of two programs. You can compare the output of your own program with that of another program to determine whether your program is correct.
Because differential testing is performed many times, batch processing is needed to automate it.
Specifically, differential testing requires a data generator and two programs whose output will be compared.
Each time the data generator is run, it writes the generated data to an input file. Through redirection, the two programs read the data and write their output to specified files. Finally, the fc command on Windows (the diff command on Linux) is used to compare the files and check whether the program is correct. If an error is found, the data just generated can be used directly for debugging.
The general framework of a differential-testing program is as follows:
#include <cstdio>
#include <cstdlib>
int main() {
// For Windows
// Do not use file input/output during differential testing
// Of course, this program can also be rewritten as a batch file
while (true) {
system("gen > test.in"); // The data generator writes generated data to the input file
system("test1.exe < test.in > a.out"); // Get the output of program 1
system("test2.exe < test.in > b.out"); // Get the output of program 2
if (system("fc a.out b.out")) {
// This compares the input and output
// fc returns 0 when the outputs are identical, and a nonzero value otherwise
system("pause"); // Make it convenient to inspect the differences
return 0;
// The input data has been stored in test.in and can be used directly for debugging
}
}
}
Memory Pool
When dynamically allocating memory, frequent use of new/malloc consumes a large amount of time and space and may even create a large amount of memory fragmentation, thereby reducing program performance and causing an otherwise correct program to receive TLE/MLE.
In this situation, the technique known as a "memory pool" is needed: before actually using memory, first request and allocate a certain amount of memory as a reserve. When dynamic allocation is needed, simply allocate a block directly from the reserve.
In most OI problems, the maximum memory required can be calculated in advance and allocated all at once.
Example:
// Allocate a dynamically allocated 32-bit signed integer array:
int* newarr(int sz) {
static int pool[MAXN], *allocp = pool;
return allocp += sz, allocp - sz;
}
// Code for dynamically creating segment-tree nodes:
Node* newnode() {
static Node pool[MAXN << 1], *allocp = pool - 1;
return ++allocp;
}
References
Introduction to Algorithms: Classic Problems and Solutions