Computers can only do a limited number of operations in a given time, usually about a billion operations per second. Here, by an individual operation, we mean addition, multiplication, assigning a value to a variable, etc. Hence, if we want our algorithm to finish executing in a second or so, then we need to make sure that the total number of operations we are asking it to do is less than 1 billion.
Estimating the exact run-time of an algorithm without implementing and executing it is very tough since it depends on so many factors - including the programming language being used, the compiler, the hardware of the computer itself, and more. Instead, what we'd like to do most of the time, is to estimate the run-time approximately.
Rate of growth
In algorithms, we focus on estimating the execution ...
Floyd Warshall algorithm is an All-Pairs shortest path algorithm. This means it calculates the value of the shortest path between each pair of nodes in a graph.
The most important questions are:
1: What are the main differences between Floyd Warshall and Dijkstra?
Floyd Warshall algorithm is a Dynamic Programming based algorithm. The technique used in this algorithm is known as Matrix Chain Multiplication. A shortest path between 2 nodes in a graph would be a chain of nodes.
Floyd Warshall algorithm runs in O(V^3) where V is the number of nodes in our graph.
Since there isn't a more efficient implementation for sparse graphs, other shortest path algorithms are often better suited for sparse graphs.
2: Why don't we make Dijkstra from each node in our ...
Initially, we need each source shortest path in a matrix(already given to us). Now with each new road built how will you update this distance matrix? (You need not run a Floyd Warshall for the new updation. As this would cause a TLE).
Now we introduce a new road a---b. With this new road, either Distance[i][j] remains unchanged or Distance[i][j] should be reduced. Distance[i][j] will only reduce further if the new path i, v1, v2, ..., vn, j which includes the road a---b(or b---a), makes the new path lesser than Distance[i][j].
Motivation: Given an array of N integers. You have to answer some queries in form (l, r, k). To answer this query you have to print the number of integers less than k in the sub-array array[l .... r].
You should be able to solve the problem in O(log^2 n) per query at least. How? You can use Merge Sort Trees.
Now what is a Merge Sort Tree? Merge Sort Tree is actually a Segment Tree but each node contains a vector. If the range of the node is [l,r] then the vector will contain the elements of array[l...r] but in sorted order.
To solve the above problem we can make a Merge Sort Tree first and go into relevant segments and binary search on the vector that was stored in those nodes to count how many numbers are less than k. This will give O(log^2 n)
I think O(nlog^2 n ) is not an acceptable time limit for this problem. It is only meant to be solved in O(nlog n). I tried writing it using merge sort tree but was getting TLE even with fast io. You can solve it using BIT or persistent segment tree in nlogn time.
Suffix arrays are a data structure which allow for efficient string matching and other operations. In this tutorial, we will describe what they are and why they are useful. We will also describe algorithms for generating suffix arrays, starting with a trivial one and moving onto faster ones. Lets get started.
What are suffix arrays?
Consider any string, say s = "random". It is customary to include a symbol at the end which is smaller than any character. Let us include '$', which is smaller than any Latin character in ASCII, so s = "random$".
Consider all suffixes of this string, and name the suffix that starts at the i-th position as z_i.
Problem: You are given a grid of size n \times 2 and n tiles of size 2 \times 1. In how many different ways can you tile the grid such that the entire grid is covered and no tiles overlap. (The tiles look identical to each other. Two ways of tiling are different based on whether the tiles are placed horizontally or vertically).
Example: There are 3 possible ways of tiling a 3 \times 2 grid.