PROGRAMMING
TIPS, TRICKS & TWEAKS
Last modified: September 14, 2007
(C/C++) Avoiding "if (i=0) {...}" error – This is probably C++ Tips Number 1
If you are comparing with a constant, you could place the constant on the LHS (instead of the usual RHS). That is, instead of writing "if (i == 0) {...}
", write "if (0 == i) {...}
". The compiler will flag out a syntax error if you inadvertently write "if (0 = i) {...}"
. [Java introduces a new data type called boolean
, which kills this problem.]
[Contributed by Nguyen Trung Nghia]
(C/C++/Java) switch is better than nested-if
Instead of writing:
if (0 == i) //do something else if (1 == i) //do something else if (2 == i) //do something else if (3 == i) //do something else //do something
It is better to write:
switch(i) { // for int and char only case 0: //do something break; case 1: //do something break; case 2: //do something break; case 3: //do something break; default: //do something }
[Contributed by Nguyen Trung Nghia]
(C/C++) The dreaded #define
Nghia recommends the following #define
to speed up your programming in the contest:
#define REP(i,a) for(i=0;i<a;i++) #define FOR(i,a,b) for(i=a;i<b;i++) #define VE vector<int> #define SZ size() #define PB push_back
My Note: Beware of #define
in normal programming. You could use #define
to change the C++ language into C--
, a useless language that only you can understand (in other words, this is not a good software engineering practice).
(C/C++/Java) Bit Manipulation
From http://en.wikipedia.org/wiki/Bit_manipulation:
To "set" a bit (where n is the bit number, and bit 0 is the least significant bit):
unsigned char a |= (1 << n); // '|' is bitwise OR, '<<' is bit left-shift
To "clear" a bit:
unsigned char b &= ~(1 << n); // '&' is bitwise AND
To "toggle" a bit:
unsigned char c ^= (1 << n); // '^' is bitwise XOR
To "test" a bit:
unsigned char e = d & (1 << n); //d has the byte value.
(Training Problem) Prime Numbers
The simplest, most elegant algorithm is perhaps the sieve of Eratosthenes. This pseudo-code is given in http://en.wikipedia.org/wiki/Prime_number:
// arbitrary search limit limit ← 1000000 // assume all numbers are prime at first is_prime(i) ← true, i ∈ [2, limit] for n in [2, √limit]: if is_prime(n): // eliminate multiples of each prime, // starting with its square // 2n, 3n, ..., (n-1)n already eliminated // nn, (n+1)n, (n+2)n, ... to be eliminated is_prime(i) ← false, i ∈ {n^2, n^2+n, n^2+2n, ..., limit} for n in [2, limit]: if is_prime(n): print n
Nghia wrote: with this simple algorithm, you can solve quite a number of problems in acm.uva.es. You should use bit operations to reduce the size of memory used.
- http://acm.uva.es/p/v1/136.html (warming up)
- http://acm.uva.es/p/v1/160.html
- http://acm.uva.es/p/v4/406.html
- http://acm.uva.es/p/v5/583.html
- http://acm.uva.es/p/v103/10394.html
- http://acm.uva.es/p/v105/10539.html
- http://acm.uva.es/p/v108/10858.html
- http://acm.uva.es/p/v108/10856.html (this problem needs prime generator + very simple DP + very useful and basic search technique)
(Training Problem) To find B^P mod M
B^P means B raise to the power of P. B and P are integers in the range 0 to 2147483647 inclusive. M is an integer in the range 1 to 46340 inclusive.
Hint:
- P = a0 x 2^0 + a1 x 2^1 + a2 x 2^2 + a3 x 2^3 + ... + an x 2^n (n<32)
- Find B^a0 mod m, B^a1 mod m, B^a2 mod m, B^a3 mod m, ..., B^an mod m (32 term only)
- B^ai mod m can be found by using the result from B^aj mod m, j = i - 1 (this is called Dynamic Programming)
- Please remember (axb) mod m = ((a mod m) x (b mod m)) mod m (to avoid overflow errors)
- The complexity of this algorithm is log(P)
- try to make your source code as short as possible. In order to do that, you may need to use bit operation and only one for/while loop.
Try these problems:
- http://acm.uva.es/p/v3/374.html
- http://online-judge.uva.es/p/v102/10229.html ( try to represent f[n] as = [ a b ; c d ]^n )