Posts

Showing posts from February, 2017

Tips to be Competitive

General tips below: Tip 1: Type Code Faster! No kidding! Although this tip may not mean much as ICPC and (especially) IOI are not typing contests, we have seen Rank i and Rank i + 1 ICPC teams separated only by a few minutes and frustrated IOI contestants who miss out on salvaging important marks by not being able to code a last-minute brute force solution properly. When you can solve the same number of problems as your competitor, it will then be down to coding skill (your ability to produce concise and robust code) and ... typing speed. Try this typing test at http://www.typingtest.com and follow the instructions there on how to improve your typing skill. Steven’s is ∼85-95 wpm and Felix’s is ∼55-65 wpm. If your typing speed is much less than these numbers, please take this tip seriously! On top of being able to type alphanumeric characters quickly and correctly, you will also need to familiarize your fingers with the positions of the frequently used programming langu...

Introduction to Big O

Big O Notation Big O is defined as the asymptotic upper limit of a function. In plain english, it means that is a function that cover the maximum values a function could take. As we saw a little earlier this notation help us to predict performance and compare algorithms. Growth Rate Name 1 Constant log(n) Logarithmic n Linear n log(n) Linearithmic n^2 Quadratic n^3 Cubic 2^n Exponential This is kinda abstract let’s see what it means in code: Growth Rate Name Code Example description 1 Constant a= b + 1; statement (one line of code) log(n) Logarithmic while(n>1){ n=n/2; } Divide in half (binary search) n Linear for(c=0; c<n; c++){ a+=1; } Loop n*log(n) Linearithmic Mergesort, Quicksort, … Effective sorting algorithms n^2 Quadratic for(c=0; c<n; c++){ for(i=0; i<n; i++){ a+=1; } } Double loop n^3 Cubic for(c=0; c<n; c++){ for(i=0; i<n; i++){ for(x=0; x<n; x++){ a+=1; } } } Triple loop...