Chapter 1 : BASICS OF COMPETITIVE CODING 1

Contents:
Input/ Output taking
Brute force method

INPUT/OUTPUT TECHNIQUES
In all programming contest, or more specifically, in all useful program, you need to read in input and process it.
However, the input data can be as nasty as possible, and this can be very troublesome to parse.
If you spent too much time in coding how to parse the input efficiently and you are using C/C++ as your programming
language, then this tip is for you. Let's see an example:
How to read the following input:

EXAMPLE 1:

122312312

The fastest way to do it is:

int main () {
while(scanf("%d",&N==1))
{
//process N…
}
}

EXAMPLE 2:

There are N lines, each lines always start with character '0' followed by '.', then unknown number of digits x, finally the
line always terminated by three dots "...".

N 0.xxxx...

The fastest way to do it is:

#include <bits/stdc++.h>
using namespace std;
char digits[100];
int main()
{
scanf("%d",&N);
for (i=0; i<N; i++)
{ scanf("0.%[0-9]...",&digits); // surprised?
printf("the digits are 0.%s\n",digits);
}
}

This is the trick that many C/C++ programmers doesn't aware of. Why we said C++ while scanf/printf is a standard C I/O
routines? This is because many C++ programmers "forcing" themselves to use cin/cout all the time, without realizing
that scanf/printf can still be used inside all C++ programs.
 Chapter 1 : BASICS OF COMPETITIVE CODING 2

EXAMPLE 3:
Mastery of programming language I/O routines will help you a lot in programming contests.
Advanced use of printf() and scanf()

Those who have forgotten the advanced use of printf() and scanf(), recall the following examples:

scanf("%[ABCDEFGHIJKLMNOPQRSTUVWXYZ]",&line); //line is a string

This scanf() function takes only uppercase letters as input to line and any other characters other than A..Z terminates the
string. Similarly the following scanf() will behave like gets()

scanf("%[^\n]",line); //line is a string

Learn the default terminating characters for scanf(). Try to read all the advanced features of scanf() and printf(). This will
help you in the long run.

Using new line with scanf()

EXAMPLE 4
If the content of a file (input.txt) is

abc def

And the following program is executed to take input from the file:

char input[100],ch;
void main(void)
{
freopen("input.txt","rb",stdin);
scanf("%s",&input);
scanf("%c",&ch);
}

The following is a slight modification to the code:

char input[100],ch;
void main(void)
{
freopen("input.txt","rb",stdin);
scanf("%s\n",&input);
scanf("%c",&ch);
}

What will be their value now? The value of ch will be '\n' for the first code and’d’ for the second code.
 Chapter 1 : BASICS OF COMPETITIVE CODING 3

EXAMPLE 6:
// fastest input output
inline int inPos()
{
int n = 0;
register char ch = inchar();
while (ch < '0' || ch > '9') ch = inchar();
while (ch >= '0' && ch <= '9')
{
n = (n << 3) + (n << 1) + (ch - '0');
ch = inchar();
}
return n;
}

int main()
{
int N, Q;
N = inPos();
Q = inPos();
return 0;
}

EXAMPLE 7:
Be careful about using gets() and scanf() together !

You should also be careful about using gets() and scanf() in the same program. Test it with the following scenario. The
code is:
scanf("%s\n",&dummy);
gets(name);

And the input file is:

ABCDEF bbbbbXXX

What do you get as the value of name?

"XXX" or "bbbbbXXX" (Here, "b" means blank or space)
 Chapter 1 : BASICS OF COMPETITIVE CODING 4

BRUTE FORCE TECHNIQUE

This is the most basic problem solving technique. Utilizing the fact that computer is actually very fast.
Complete search exploits the brute force, straight-forward, try-them-all method of finding the answer.

This method should almost always be the first algorithm/solution you consider. If this works within time and space
constraints, then do it: it's easy to code and usually easy to debug. This means you'll have more time to work on all the
hard problems, where brute force doesn't work quickly enough.

EXAMPLE 1: Party Lamps

You are given N lamps and four switches. The first switch toggles all lamps, the second the even lamps, the third the odd
lamps, and last switch toggles lamps 1,4,7,10,...

Given the number of lamps, N, the number of button presses made (up to 10,000), and the state of some of the lamps
(e.g., lamp 7 is off), output all the possible states the lamps could be in.

SOLUTION:
Naively, for each button press, you have to try 4 possibilities, for a total of 4^10000 (about 10^6020), which means
there's no way you could do complete search (this particular algorithm would exploit recursion).

Noticing that the order of the button presses does not matter gets this number down to about 10000^4 (about 10^16),
still too big to completely search (but certainly closer by a factor of over 10^6000).

However, pressing a button twice is the same as pressing the button no times, so all you really have to check is pressing
each button either 0 or 1 times.
That's only 2^4 = 16 possibilities, surely a number of iterations solvable within the time limit.

It is beautiful, isn't it? If you have this kind of reasoning ability. Many seemingly hard problems is eventually solvable
using brute force.

RECURSION
Recursion is cool. Many algorithms need to be implemented recursively. A popular combinatorial brute force algorithm,
backtracking, usually implemented recursively. After highlighting it's importance, lets study it.

Recursion is a function/procedure/method that calls itself again with a smaller range of arguments (break a problem into
simpler problems) or with different arguments (it is useless if you use recursion with the same arguments). It keeps
calling itself until something that is so simple / simpler than before (which we called base case), that can be solved easily
or until an exit condition occurs.

A recursion must stop (actually, all program must terminate). In order to do so, a valid base case or end-condition must
be reached. Improper coding will leads to stack overflow error.
You can determine whether a function recursive or not by looking at the source code. If in a function or procedure, it
calls itself again, it's recursive type.
When a method/function/procedure is called: – caller is suspended, – "state" of caller saved, – new space allocated for
variables of new method.
 Chapter 1 : BASICS OF COMPETITIVE CODING 5

Recursion is a powerful and elegant technique that can be used to solve a problem by solving a smaller problem of the
same type. Many problems in Computer Science involve recursion and some of them are naturally recursive.

If one problem can be solved in both way (recursive or iterative), then choosing iterative version is a good idea since it is
faster and doesn't consume a lot of memory. Examples: Factorial, Fibonacci, etc.

However, there are also problems that are can only be solved in recursive way or more efficient in recursive type or
when it's iterative solutions are difficult to conceptualize. Examples: Tower of Hanoi, Searching (DFS, BFS), etc.

Types of recursion

There are 2 types of recursion, Linear recursion and multiple branch (Tree) recursion.
1. Linear recursion is a recursion whose order of growth is linear (not branched). Example of Linear recursion is
Factorial, defined by fac (n)=n * fac (n-1).

2. Tree recursion will branch to more than one node each step, growing up very quickly. It provides us a flexible
ways to solve some logically difficult problem. It can be used to perform a Complete Search (To make the
computer to do the trial and error). This recursion type has a quadratic or cubic or more order of growth and
therefore, it is not suitable for solving "big" problems. It's limited to small. Examples: solving Tower of Hanoi,
Searching (DFS, BFS), Fibonacci number, etc.

Some compilers can make some type of recursion to be iterative. One example is tail recursion elimination. Tail-
recursive is a type of recursive which the recursive call is the last command in that function/procedure.

Tips on Recursion

1. Recursion is very similar to mathematical induction.

2. You first see how you can solve the base case, for n=0 or for n=1.
3. Then you assume that you know how to solve the problem of size n-1, and you look for a way of obtaining the solution
for the problem size n from the solution of size n-1.

When constructing a recursive solution, keep the following questions in mind:

1. How can you define the problem in term of a smaller problem of the same type?

2. How does each recursive call diminish the size of the problem?

3. What instance of the problem can serve as the base case?

3. As the problem size diminishes, will you reach this base case?

Sample of a very standard recursion, Factorial :

int factorial(int n)
{
if (n==0)
return 1;
else
return n*factorial(n-1);
}
 Chapter 1 : BASICS OF COMPETITIVE CODING 6

Divide and Conquer

This technique use analogy "smaller is simpler". Divide and conquer algorithms try to make problems simpler by dividing
it to sub problems that can be solved easier than the main problem and then later it combine the results to produce a
complete solution for the main problem.

Divide and Conquer algorithms:

Quick Sort, Merge Sort, Binary Search.

Divide & Conquer has 3 main steps:

1. Divide data into parts

2. Find sub-solutions for each of the parts recursively (usually)
3. Construct the final answer for the original problem from the sub-solutions

DC(P)
{
if small(P)
then
return Solve(P);
else
{
divide P into smaller instances P1,...,Pk, k>1;
Apply DC to each of these subproblems;
return combine(DC(P1),...,DC(Pk));
}
}

Binary Search, is not actually follow the pattern of the full version of Divide & Conquer, since it never combine the sub
problems solution anyway. However, lets use this example to illustrate the capability of this technique.

BINARY SEARCH ILLUSTRATION

Binary Search will help you find an item in an array. The naive version is to scan through the array one by one (sequential
search). Stopping when we found the item (success) or when we reach the end of array (failure). This is the simplest and
the most inefficient way

to find an element in an array. However, you will usually end up using this method because not every array is ordered,
you need sorting algorithm to sort them first.
Binary search algorithm is using Divide and Conquer approach to reduce search space and stop when it found the item
or when search space is empty.
Pre-requisite to use binary search is the array must be an ordered array, the most commonly used example of ordered
array for binary search is searching an item in a dictionary.
Efficiency of binary search is O(log n). This algorithm was named "binary" because it's behavior is to divide search space
into 2 (binary) smaller parts).
 Chapter 1 : BASICS OF COMPETITIVE CODING 7

Optimizing your source code (Following details would be discussed in workshops

also)
Your code must be fast. If it cannot be "fast", then it must at least "fast enough". If time limit is 1 minute and your
currently program run in 1 minute 10 seconds, you may want to tweak here and there rather than overhaul the whole
code again.

Generating vs. filtering

Programs that generate lots of possible answers and then choose the ones that are correct (imagine an 8-queen solver)
are filters. Those that hone in exactly on the correct answer without any false starts are generators. Generally, filters are
easier (faster) to code and run slower. Do the math to see if a filter is good enough or if you need to try and create a
generator.

Pre-Computation / Pre-Calculation
Sometimes it is helpful to generate tables or other data structures that enable the fastest possible lookup of a result.
This is called Pre-Computation (in which one trades space for time). One might either compile Pre-Computed data into a
program, calculate it when the program starts, or just remember results as you compute them. A program that must
translate letters from upper to lower case when they are in upper case can do a very fast table lookup that requires no
conditionals, for example. Contest problems often use prime numbers - many times it is practical to generate a long list
of primes for use elsewhere in a program.

Decomposition

While there are fewer than 20 basic algorithms used in contest problems, the challenge of combination problems that
require a combination of two algorithms for solution is daunting. Try to separate the cues from different parts of the
problem so that you can combine one algorithm with a loop or with another algorithm to solve different parts of the
problem independently. Note that sometimes you can use the same algorithm twice on different (independent!) parts of
your data to significantly improve your running time.

Symmetries
Many problems have symmetries (e.g., distance between a pair of points is often the same either way you traverse the
points). Symmetries can be 2-way, 4-way, 8-way, and more. Try to exploit symmetries to reduce execution time.
For instance, with 4-way symmetry, you solve only one fourth of the problem and then write down the four solutions
that share symmetry with the single answer (look out for self-symmetric solutions which should only be output once or
twice, of course).

Solving forward vs backward

Surprisingly, many contest problems work far better when solved backwards than when using a frontal attack. Be on the
lookout for processing data in reverse order or building an attack that looks at the data in some order or fashion other
than the obvious.

NEXT TUTORIAL : MATHEMATICS BEHIND COMPETITIVE PROGRAMMING

Contact: Pulkit Puri, pulkitpuri96@gmail.com, 7508215965