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.


(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:

Try these problems: