What is competitive programming?
Sometimes I attend competitive programming competitions or olympiads. I am not really experienced in this area, but I find it interesting and funny to participate in such events. During these competitions, participants are given tasks wich require coming up with a solution algorithm which meet the requirements of speed and memory consumption. Some examples of competitive programming contests are Google Code Jam, Facebook Hacker Cup (those two are online competitions) and a lot of others.
For solving competitive programming tasks they usually use C++ or Python.
C++ is fast and gives some space for optimizations, while Python makes it
simple to implement more complex algorithms.
But I usually choose Java, because I feel most comfortable and I have most experience using this language. I decided to write down in this blog post as many tips for competitve programming with Java as much as I could find and think of. Hopefully this will be useful for me later and maybe for some other people who cosider using Java at their contest.
So here are tricks I find interesting and useful:
1. Checking if number is even or odd without using % operator
(a & 1) == 02. Fast Multiplication or Division by 2
n = n << 1; // multiply n = n >> 1; // divide3. Swapping of 2 numbers without using of 3rd variable
a ^= b; b ^= a; a ^= b;4. Use StringBuffer for string manipulations 5. Calculating the most significant digit
double k = Math.log10(n); k = k - Math.floor(k); int x = (int) Math.pow(10, k);6. Number of digits
Math.floor(Math.log10(n)) + 1;7. Checking for prime number:
BigInteger.valueOf(42).isProbablePrime(1);8. Greatest common divisor
BigInteger a = BigInteger.valueOf(42); BigInteger b = BigInterger.valueOf(86); System.out.println(a.gcd(b));9. Efficient trick to know if a number is a power of 2:
x != 0 && (x && (x-1)) == 010. Use Arrays.sort() or Collections.sort() for sorting
11. Use Arrays.binarySearch() or Collections.binarySearch() for searching
12. Use Arrays.copyOf() or Arrays.copyOfRange() for copying
13. Use Collections.rotate() to rotate (shift) all elements at certain distance
14. Use Collections.frequency() to get frequency of certain element
15. Use BufferedReader for faster I/O
16. Use StringBuilder to print all output. Firstly, build all output in StringBuilder and then print it all at once (to save I/O operations)
17. PriorityQueue is good for heap data structure
18. Sometimes it is better to use char array to avoid string concatenations
19. BigInteger class is extremelly useful sometimes.
That's all for now. I hope to update this post with more tips in the future :)