CCppCodingCollection [Competitive Coding]

This Repository contains majority of the programs that I have created on my local system so far. Most of the codes are solutions of various competitive challenges and practice problems on CodeChef, Hackerrank, Hackerearth, Codeforces and LeetCode etc.

Platform	Profile Link	Codes Link
HackerEarth	Profile	Codes
CodeChef	Profile	Codes
CodeForces	Profile	Codes
LeetCode	Profile	Codes
GeeksForGeeks	Profile	Codes

VS Code Config Shortcuts

CTRL + SHIFT + B => BUILD THE PROGRAM TAKING INPUT FROM input.txt, AND DISPLAY OUTPUT AT output.txt, CHECKING DIFFERENCE FROM solution.txt AND CORRESPONDINGLY UPDATING difference.txt

CTRL + SHIFT + V => PREVIEW MARKDOWN

SOME INTERESTING CODE SNIPPETS:

// Directly take input in a Vector of size n:
VI v(n);
for (int &i : v)
    cin >> i;

// Sort Vector in Descending order:
sort(all(v), greater<int>());

// Loop through elements of Vector
for(auto el: v)
cout<<el;

// Traverse through all the permutations in the array
int i, n = 8, p[8] = {0, 1, 2, 3, 4, 5, 6, 7};
do {
    // 'p' takes the value of all the permutations possible.
}
while (next_permutation(p, p + n));

// Sort Structure with multiple rules
struct Student
{
    string name;
    int math;
    int phy;
    int total;
}

bool compareTwoStudents(Student a, Student b)
{
    if (a.total != b.total)
        return a.total > b.total;

    if (a.math != b.math)
        return a.math > b.math;

    return a.phy > b.phy;
}

Student a[];
sort(a, a + 5, compareTwoStudents);

NOTES:

From Competitive Programming 3 - Steven Halim, Felix Halim

• Tips to be Competitive

  • Tip 1: Type Code Faster!
  • Tip 2: Quickly Identify Problem Types
  • Tip 3: Do Algorithm Analysis
  • Tip 4: Master Programming Languages
  • Tip 5: Master the Art of Testing Code
  • Tip 6: Practice and More Practice

• Modern computers are quite fast and can process 5 up to ≈ 100M (or 10⁸ ; 1M = 1, 000, 000) operations in a few seconds. You can use this information to determine if your algorithm will run in time. For example, if the maximum input size n is 100K (or 105 ; 1K = 1, 000), and your current algorithm has a time complexity of O(n²), common sense (or your calculator) will inform you that (100K)² or 1010 is a very large number that indicates that your algo- rithm will require (on the order of) hundreds of seconds to run. You will thus need to devise a faster (and also correct) algorithm to solve the problem. Suppose you find one that runs with a time complexity of O(n log₂ n). Now, your calculator will inform you that 105 log₂ 105 is just 1.7 × 106 and common sense dictates that the algorithm (which should now run in under a second) will likely be able to pass the time limit.

• Familiarity with these bounds:

  • 2¹⁰ = 1024 ≈ 10³, 2²⁰ = 1048576 ≈ 10⁶ .
  • 32-bit signed integers (int) and 64-bit signed integers (long long) have upper limits of 2^{31 −1} ≈ 2 ×10⁹ (safe for up to ≈ 9 decimal digits) and 2^{63 −1} ≈ 9 ×10¹⁸ (safe for up to ≈ 18 decimal digits) respectively.
  • Unsigned integers can be used if only non-negative numbers are required. 32-bit unsigned integers (unsigned int) and 64-bit unsigned integers (unsigned long long) have upper limits of 2^{32 − 1} ≈ 4 × 10⁹ and 2^{64 − 1} ≈ 1.8 × 10¹⁹ respectively.
  • If you need to store integers ≥ 2⁶⁴, use the Big Integer technique.
  • There are n! permutations and 2ⁿ subsets (or combinations) of n elements.
  • The best time complexity of a comparison-based sorting algorithm is Ω(n log₂ n).
  • Usually, O(n log₂ n) algorithms are sufficient to solve most contest problems.
  • The largest input size for typical programming contest problems must be < 1M.
  • A typical year 2013 CPU can process 100M = 10⁸ operations in a few seconds.

• The Ad Hoc problems are problems that ‘cannot be classified anywhere else’ since each problem description and its corresponding solution are ‘unique’. Many Ad Hoc problems are easy

• If our array needs only to contain Boolean values (1/true and 0/false), we can use an alternative data structure other than an array—a C++ STL bitset. The bitset supports useful operations like reset(), set(), the [] operator and test().

• The difference between these two data structures is simple: the C++ STL map (and Java TreeMap) stores (key → data) pairs whereas the C++ STL set (and Java TreeSet) only stores the key. For most (contest) problems, we use a map (to really map information) instead of a set (a set is only useful for efficiently determining the existence of a certain key).

• The heap is another way to organize data in a tree. The (Binary) Heap is also a binary tree like the BST, except that it must be a complete 14 tree. Complete binary trees can be stored efficiently in a compact 1-indexed array of size n + 1, which is often preferred to an explicit tree representation. For example, the array A = {N/A, 90, 19, 36, 17, 3, 25, 1, 2, 7} is the compact array representation of Figure 2.3 with index 0 ignored. One can navigate from a certain index (vertex) i to its parent, left child, and right child by using simple index manipulation: i/2, 2 × i, and 2 × i + 1, respectively. These index manipulations can be made faster using bit manipulation techniques (see Section 2.2): i >> 1, i << 1, and (i << 1) + 1, respectively.

• There is no notion of a ‘search’ in the Heap (unlike BSTs). The Heap instead allows for the fast extraction (deletion) of the maximum element: ExtractMax() and insertion of new items: Insert(v)—both of which can be easily achieved by in a O(log n)

• The implementation of priority queue is available in the C++ STL queue library (or Java PriorityQueue). Priority Queues are an important component in algorithms like Prim’s (and Kruskal’s) algorithms for the Minimum Spanning Tree (MST) problem (see Section 4.3), Dijkstra’s algorithm for the Single-Source Shortest Paths (SSSP) problem (see Section 4.4.3), and the A* Search algorithm

• Four problem solving paradigms commonly used to attack prob- lems in programming contests, namely Complete Search (a.k.a Brute Force), Divide and Conquer, the Greedy approach, and Dynamic Programming.

Abbreviations

A* : A Star
ACM : Assoc of Computing Machinery
AC : Accepted
APSP : All-Pairs Shortest Paths
AVL : Adelson-Velskii Landis (BST)
BNF : Backus Naur Form
BFS : Breadth First Search
BI : Big Integer
BIT : Binary Indexed Tree
BST : Binary Search Tree
CC : Coin Change
CCW : Counter ClockWise
CF : Cumulative Frequency
CH : Convex Hull
CS : Computer Science
CW : ClockWise
DAG : Directed Acyclic Graph
DAT : Direct Addressing Table
D&C : Divide and Conquer
DFS : Depth First Search
DLS : Depth Limited Search
DP : Dynamic Programming
DS : Data Structure
ED : Edit Distance
FIFO : First In First Out
FT : Fenwick Tree
GCD : Greatest Common Divisor
ICPC : Intl Collegiate Prog Contest
IDS : Iterative Deepening Search
IDA* : Iterative Deepening A Star
IOI : Intl Olympiad in Informatics
IPSC : Internet Problem Solving Contest
LA : Live Archive
LCA : Lowest Common Ancestor
LCM : Least Common Multiple
LCP : Longest Common Prefix
LCS1 : Longest Common Subsequence
LCS2 : Longest Common Substring
LIFO : Last In First Out
LIS : Longest Increasing Subsequence
LRS : Longest Repeated Substring
LSB : Least Significant Bit
MCBM : Max Cardinality Bip Matching
MCM : Matrix Chain Multiplication
MCMF : Min-Cost Max-Flow
MIS : Maximum Independent Set
MLE : Memory Limit Exceeded
MPC : Minimum Path Cover
MSB : Most Significant Bit
MSSP : Multi-Sources Shortest Paths
MST : Minimum Spanning Tree
MWIS : Max Weighted Independent Set
MVC : Minimum Vertex Cover
OJ : Online Judge
PE : Presentation Error
RB : Red-Black (BST)
RMQ : Range Min (or Max) Query
RSQ : Range Sum Query
RTE : Run Time Error
SSSP : Single-Source Shortest Paths
SA : Suffix Array
SPOJ : Sphere Online Judge
ST : Suffix Tree
STL : Standard Template Library
TLE : Time Limit Exceeded
USACO : USA Computing Olympiad
UVa : University of Valladolid
WA : Wrong Answer
WF : World Finals