## Tips and Tricks

- Chua Hock-Chuan (ehchua@ntu.edu.sg)

### (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 )