6 May 2011

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 )
Tags: , ,

You may have missed:

Comments are closed.