Tips

Header Files

Instead of including multiple header files, there is a nice header file that will automatically include all other header files: bits/stdc++.h


  
If the above fails to compile (on older compilers), here is the list of commonly used header files.

  



  
  
Define

  
Using #define can save you time coding and debugging. It also makes your code look neater.

  

  
  
Iterators

  
Using iterators might be of a hassle, but it also decreases the complexity of your code, making debugging easier and faster. It is also easier to read. Compare the following two codes when iterating the vector adjList[x]

  

  

  
  
  
Typedef

  
In the previous section, you might have realised that vector< pair >::iterator might have been a lot to type. You can use typedef to reduce the hassle.

  

  
  
Typeof

  
You may also want to use typeof to let the compiler decipher what is the variable type.

  






  
Bit Manipulation

  
Computers represent data in the form of bits. As such, bit operators tend to be faster than arithmetic operations and can speed up your code!
 

  
  
Basic Operations

  
We can manipulate the bits of an integer using several bitwise operations.

  
AND will return 1 when both bits are 1

  
OR will return 1 if either of the bits are 1

  
XOR will return 1 if the bits are different

  
LEFT PUSH X will push all the bits to the left by X positions (Same as dividing by 2X)

  
RIGHT PUSH X will push all the bits to the right by X positions (Same as multiplying by 2X)

  


  
Bitmask

  
For some problems, the state involves storing whether certain items are taken or not. For example: out of item 0 to 5, item 0, 2 and 5 are taken. To do that, we can employ the bit representations of integers to store them efficiently. This technique is called bitmask or bitmasking.

  
Let the 0th item be represented by the first bit, 1st item by the second bit.. and so on.

  
You will realise that for the Xth bit, it is represented by the bit that is '1' in the binary representation of 2X or 1<<X
  
Lets say you have a bitmask (integer) of base 2: 000101. It means that items 0 and 2 are taken (hence the first bit and the 3rd bit is 1).

  
To check if an item is taken, we check if the corresponding bit is '1' using bitwise AND.

  
To denote that an item is taken, we simply change the corresponding bit to '1' and vice-versa if the item is untaken. To do so, we can toggle the bit from '0' to '1' or '1' to '0' using bitwise XOR

  

  

    
Shortcuts

    
To set the first X items to be taken, you can do bitmask = (1<<X)-1

    
To always set the Xth item to be taken (even if it is already taken), you can do bitmask = bitmask | (1<<X)

    
To always set the Xth item to be not taken (even if it is already not taken), you can do bitmask = bitmask & (~(1<<X))

    
LSOne (bitmask&(-bitmask)) can be utilized to only iterate through the '1' bits in a bitmask.