Since this is the first novice contest, the questions will be quite doable and easy. As such, there are not many specific topics that need revision. However, the topics which one could revise are as follows -
1. Memoizaton
When we calculate values of a function with different parameters recursively, often value of function with same parameters is needed multiple times. Instead of calculating the same value every single time it is needed, we can just store a flag that this particular value has been calculated already and need not be calculated again. In that case, if flag is set, we just return the stored answer. This is called memoization. It speeds up your program significantly, as appropriate.
Example :
// Initially calculated[] array is set to 0 or false
//main function body calculating the answer in variable “ans”
calculated [a] [b] = true;
answer [a] [b] = ans;
return ans;
}
This is the basic working. Kindly go through the material on the net for further information. Memoization is used mostly when we are trying to recursively calculate values. It is most common when implementing Dynamic Programming.
2. Basic Geometry
One of the basic problems with implementing geometry problems on computers (Computational Geometry) is that you have to deal with floating values and not integers. There is also a lot of division operations which further reduce the accuracy of the values. As such, with multiple operations, values become highly inaccurate leading to large errors. Division with 0 is also something to be taken care of (e.g. when calculating slope).
Therefore, we try and keep the calculations as error free as possible. A big tool in this regard is the cross product of two vectors or (line segments).
Kindly go through CLRS (introduction to Algorithm 3rd edition) section 33.1. You will find vector treatment revised which will help while doing simple geometry problems.
We advice you to read the whole 33rd chapter in CLRS later when you get time.
3. Modular Arithmetic
Wikipedia definition : Modular arithmetic (sometimes called clock arithmetic) is a system of
arithmetic for integers, where numbers "wrap around" after they reach a certain value—the modulus.
I guess we are all familiar with the modulus/mod/% operation which gives the remainder when dividend is divided by the divisor. For eg. 20%6 = 2.
For today’s competition, it might help to see how mod of an integer A with respect to a certain divisor B changes when the integer is mulitiplied with another integer C.
Specifically, if A mod B = D, then A*C mod B = D*C mod B.
It is a simple rule which you can figure out by doing it on paper. We advice you to go through the intricacies of modular arithmetic from the net or better still do Chapter 31 from CLRS.
4. Breadth First Search
In a graph with a set of nodes and edges (all with same weight), you often wish to find shortest path or distance between two nodes. BFS helps you do that amongst many other applications.
You start a BFS from a source node, and by end of it, it gives you the information about the shortest path from that source node to all other nodes. The information can be the path itself or the length of the path.
We will not explain the algorithm here. I suggest you check out the wikipedia page for a pseudocode or introduction. Better still, it is must to do BFS (and DFS) from chapter 22 in CLRS. For today, BFS (section 22.2) pseudocode is given on page 532 and should be sufficient for today. BFS uses a queue. DFS uses a stack (not relevant today).
a. CLRS refers to the book Introduction to Algorithms 3rd Edition commonly known as Cormen (one of the authors).
b. Kindly use Google for more information regarding various topics. Our aim was to point you in the right direction with sufficient push. Hopefully, you will do the rest.
That is about it. We will share more information and solution codes at end of the contest. We will also give links to more resources or tutorials regarding the same.
We strongly suggest that after doing these topics (if you haven’t done them before), kindly solve lots of problems on the same on SPOJ or somewhere else. Do these and related topics in full depth after the contest since we won’t be focusing on them again.
Best of luck,
Rohil Sinha
Ankul Garg
Mahesh Chandra Sharma
Want to print your doc? This is not the way.
Try clicking the ⋯ next to your doc name or using a keyboard shortcut (
