Greed is good,sort of

1.Implementation

Implementation problems do not rely on the knowledge of any particular data structure or algorithm. There isn’t really any way to learn this method except to practice problems.

Note: Sometimes the input may be large enough to cause an overflow. So remember to use long long (64-bit integer) instead of int (32-bit integer). It is safe to assume anything above 2∙10⁹ overflows int, and anything above 2∙10¹⁸ overflows long long int.

Problems mentioned in this episode, as well as subsequent ones, are only meant to serve as an introduction to a topic and are by no means enough to make you an expert at it (unless you are a genius). Be sure to practice more problems on the topics. You may go to Problemset on Codeforces and filter by tag and/or rating to find appropriate problems.

Also note that most codeforces problems have editorials (explanations of solutions). You can find them on the bottom right, usually labelled ‘Tutorial’. Read them if you are stuck.

2. Greedy

As the name suggests, a greedy approach is one where (greedily) picking the best option at every stage leads to the best overall outcome.

Reading material:

• Hackerearth [B]

3. Sorting

Sorting is a very important technique that is used in a lot of problems. There are many standard sorting techniques that you should know, although you will almost never have to implement them yourself. You may refer to this.
You may also read up on bubble sort, selection sort, insertion sort, merge sort, quick sort, counting sort and heap sort work and their respective time complexities (both average and worst case if they differ). Here is an optional read on why the best asymptotic time complexity for comparison based sorting algorithms is $\mathcal{O}(nlogn)$.
Merge sort in particular is important to know since some problems can be solved using some variation of it.
Another sorting algorithm worth mentioning is counting sort, which works in $\mathcal{O}(n)$.

Reading material:

• CPH Ch 3: Sorting, pg 25 - 31

It is recommended to use the built-in sorting methods because they are trusted implementations which are optimized for best performance. Further, you may save time not having to implement a sorting algorithm yourself.

C++ std::sort

In C++ the <algorithm> header file contains an implementation of a sorting algorithm (introsort) that can be called within your program as std::sort. The std::sort function works on arrays and vectors of all types. For an array $a$ of size $n$ it would be invoked as sort(a, a + n) whereas for a vector $v$ it would be invoked as sort(v.begin(), v.end()) to sort it completely.

• Sorting an array
• Sorting a vector

Further, you can sort any range $[l, r)$ $(0 \leq l \leq r \leq n)$ in a container. The syntax is sort(a + l, a + r) (for arrays), and sort(v.begin() + l, v.begin() + r) (for vectors).

Note: You can even use std::sort on strings. For a string $s$, sort(s.begin(), s.end()) would sort the characters of the string.

See also lambdas for custom comparison sorting.

This page uses math latex formatting. Download the extension to render it.

4. C++ STL

C++ STL (Standard Template Library) is a powerful set of C++ template classes to provide general-purpose classes and functions with templates that implement many popular and commonly used algorithms and data structures like vectors (dynamic arrays), lists, queues, and stacks. Out of these vectors, maps and sets are the most commonly used containers.

Reading material:

• Hackerearth blog - Click
• std::vector
  • Click
  • CPH Ch 4, pg 35 - 36
• std::set
  • Click
  • CPH Ch 4, pg 37 - 38
• std::map
  • Click
  • CPH Ch 4, pg 38 - 39
• C++ Iterators and ranges - CPH Ch 4, pg 39 - 41
• Topcoder blogs - Part 1 Part 2
• Further reading (optional)
  • std::bitset - CPH Ch 4, pg 41
  • std::deque - CPH Ch 4, pg 42
  • std::stack - CPH Ch 4, pg 42
  • std::queue - CPH Ch 4, pg 43
  • std::priority_queue - CPH Ch 4, pg 44
  • Policy-based data structures (not part of STL) - CPH Ch 4, pg 44

5.Frequency tables

Consider an array of elements. The frequency of a particular element is the number of times it occurs in the array. Calculating the frequencies of each element can be very useful to solve certain kinds of problems.

Frequency tables are usually built on arrays or vectors, but can also be built on maps (or hash maps) when the range of values is too large to fit in memory. The tradeoff is that maps have $\mathcal{O}(log n)$ lookup time, unlike arrays and vectors which have $\mathcal{O}(1)$ lookup time (Hash maps have $\mathcal{O}(1)$ lookup time on average, not in the worst case).

Reading material:

• GFG [B]

Practice

Mashups of topic relevant problems spanning a range of difficulties.

Competitive Programming Beginner Topics Part 2