Notes and Exercises made during the International Collegiate
Programming Contest (ICPC) México Summer Camp 2022
Explore the docs »
Report Bug
·
Request Feature
Table of Contents
Time Complexity:
This type of search is used to find an element in a sorted array. It is a binary search, because it is divided in two parts: the first part is the array from the beginning to the middle, and the second part is the array from the middle to the end.
typedef long long lli;
lli find(vector<lli>&v, lli x){
lli l = 0, r = v.size() - 1;
while(r-l > 1){
lli mid = (l+r)/2;
if(v[mid] == x) return mid;
else if(v[mid] < x) l = mid;
else r = mid;
}
if(v[l] == x) return l;
if(v[r] == x) return r;
return -1;
}Time Complexity:
typedef long long lli;
lli find(vector<lli>&v, lli x){
lli c = 0;
for(lli p = v.size(); p; p/=2)
while(c+p < v.size() && v[c+p] < x) c += p;
if(v[c] == x) return c;
return -1;
}This type of search is better suited for finding integers in a sorted array.
A vector can be seen as a function. Binary searches work over any monotonic function. In other words, the vector we use must be ordered.
 |
 |
 |
It is a type of search that is used to find the maximum or minimum of a unimodal function. It is a ternary search, because it is divided in three parts.
typedef long long lli;
lli find(vector<lli> &v){
lli l = 0, r = v.size() -1;
while(r-l>2){
lli m1 = l + (r-l)/3;
lli m2 = r - (r-l)/3;
if(v[m1]<v[m2]) r = m2;
else l = m1;
}
lli ans = NULL;
for(lli i = l; i <= r; i++)
ans = min(ans, v[i]);
return ans;
}
Adding these lines to your code will make it faster:
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);Warning: When using the lines above, you must also use the '\n'
directive instead of endl.
The use of templates in competitive programming is very important, because it allows you to use the same code for different types of problems. As well as, optimizing the amount of code you need to write.
An example template is located in the template.cpp file.
We have an array of n numbers. We want to know the sum of all positive numbers in the array.
int main(){ _
lli n, x, tot=0; cin >> n;
fore(i, 0, n) cin >> x, tot += max(0LL, x);
cout << tot << ENDL;
return 0;
}When using float’s, you must use the fixed directive to make sure
that the output is not rounded. You can use the setprecision directive
to set the number of decimal places.
cout << setprecision(10) << fixed << floatValue << ‘\n’;Because float’s are not accurate, you can use the following functions
in order to compare them:
typedef long double ld;
bool geq(ld a, ld b){return a-b >= eps;} // a >= b
bool leq(ld a, ld b){return b-a >= eps;} // a <= b
bool ge(ld a, ld b){return a-b > eps;} // a > b
bool le(ld a, ld b){return b-a > eps;} // a < b
bool eq(ld a, ld b){return abs(a-b) <= eps;} // a == b
bool neq(ld a, ld b){return abs(a-b) > eps;} // a != beps or epsilon is a small number that is used to compare
floating-point numbers. Most of the time, it is
Whenever you’re writing constants, you should specify the type of the constant.
For example, if you want to write a constant that is a long long, you
can use the following:
1000000LL;When you need to write a floating-point number, you can use the following:
double a = 1.0 / 3.0;They allow us to store elements in a FIFO (First In First Out) or LIFO
(Last In First Out) manner. They are implemented using the std::queue
and std::stack classes. They support insertion, removal and
consultation of elements on top or front.
queue<int> myQueue;
stack<int> myStack;
myQueue.push(2);
cout << myQueue.front() << endl;
myQueue.pop();
myStack.push(2);
cout << myStack.top() << endl;
myStack.pop();- Data storage of unique sorted elements in
$O\log \left(n\right)$ time. - Insertion, deletion and lookup of elements in
$O\log \left(n\right)$ time. - You can get the size of the set in
$O\left(1\right)$ time.
set<int> mySet;
mySet.insert(2);
mySet.insert(2);
mySet.insert(3);
cout << mySet.size() << endl;
cout << mySet.count(2) << endl;A map is a data structure that stores elements in a key-value pair.
- Allows you to insert, remove and lookup elements in
$O\log\left(n\right)$ time.
map<string,int> myMap;
myMap["a"] = 1;
cout << myMap["a"] << endl;
cout << myMap.size() << endl;
cout << myMap.count("b") << endl;sort(myVector.begin(), myVector.end());
int x = 5;
int posLowerX = lower_bound(myVector.begin(), myVector.end(), x) - myVector.begin();
int posUpperX = upper_bound(myVector.begin(), myVector.end(), x) - myVector.begin();
bool exist = binary_search(myVector.begin(), myVector.end(), x);- Cycle: A cycle is a path that starts and ends at the same node.
- Connected: A graph is connected if there is a path between any two nodes.
- Tree: A tree is a connected graph with no cycles.
- It is represented by a 2D array with the of
$N_{nodes} \times N_{nodes}$ - In the position
$(i,j)$ of the array, we store the weight of the edge$(i,j)$ - It consumes
$O(N^2)$ space, which is a lot. - It is faster when consulting a specific connection.
int main(){_
lli nodes, edges, a, b; cin >> nodes >> edges;
vector<vector<bool>> adjMatrix(nodes, vector<bool>(nodes, false));
fore(i, 0, edges){
cin >> a >> b;
adjMatrix[a][b] = adjMatrix[b][a] = true;
}
return 0;
}- It uses a matrix where each row
$x$ of the matrix contains the list of the nodes that are connected to$x$ . - It uses dynamic memory allocation, to only store the connections that are necessary.
- It is slower to consult a specific connection, but faster to consult the entire graph.
- Consumes
$O(N+E)$ space, where$N$ is the number of nodes and$E$ is the number of edges.
int main(){_
lli nodes, edges, a, b; cin >> nodes >> edges;
vector<vector<int>> adjList(nodes);
fore(i, 0, edges){
cin >> a >> b;
adjList[a].push_back(b);
adjList[b].push_back(a);
}DFS is a recursive depth-first search algorithm. It is used to traverse a graph.
void dfs(int currNode){
visited[currNode] = true;
for(int nextNode : adjList[currNode]){
if(!visited[nextNode]){
dfs(nextNode);
}
}
}BFS is an iterative breadth-first search algorithm. It is used to traverse a graph.
queue<int> bfs;
bfs.push(0);
visited[0] = true;
while(!bfs.empty()){
int currNode = bfs.front();
bfs.pop();
for(int nextNode : adjList[currNode]){
if(!visited[nextNode]){
bfs.push(nextNode);
visited[nextNode] = true;
}
}
}Single-source shortest path algorithm. Dijkstra’s algorithm finds the shortest path from a source node to all other nodes in a graph.
It is based on having all edges that are connected to node
- Of all the nodes that haven’t been visited, find the one with the lowest distance that we can reach.
- Calculate new distances with the new node.
vector<int> dijkstra(int source, int nodes){
vector<int> dist(nodes, -1);
dist[source] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.push({0, source});
while(!pq.empty()){
pair<int,int> currNode = pq.top();
pq.pop();
if(dist[currNode.second] != currNode.first){
continue;
}
for(auto edge: adjList[currNode.second]){
int newDist = edge.second + currNode.first;
if(dist[edge.first] == -1 || dist[edge.first] > newDist){
dist[edge.first] = newDist;
pq.push({newDist, edge.first});
}
}
}
return dist;
}A number
A number is prime if it is divisible by only 1 and itself.
| Number | isPrime |
|---|---|
| 1 | false |
| 2 | true |
| 3 | true |
The sieve of Eratosthenes is a simple algorithm for finding all prime numbers up to a given number. It works by iterating over all numbers from 2 to the given number, and marking each number that is divisible by a number that has already been marked as non-prime.
long long n;
vector<bool> sieve(n, true);
vector<long long> makeSieve(){
sieve[0] = sieve[1] = false;
for(long long i = 2; i * i < n; ++i){
if(!sieve[i]) continue;
for(long long j = i * i; j < n; j += i){
sieve[j] = false;
}S
}
vector<long long> primes;
for(long long i = 2; i < n; ++i){
if(sieve[i]){
primes.push_back(i);
}
}
return primes;
}All numbers have a unique representation as a multiplication of prime numbers.
vi decomposition(int x){
vi prime_representation;
for(auto p: primes){
while(x % p == 0){
prime_representation.push_back(p);
x /= p;
}
}
if(x > 1){
prime_representation.push_back(x);
}
return prime_representation;
}When a number is written as a product of prime numbers, the total number of divisors is:
void makeSieve(int n){
vi sieve(n);
fore(i,0,n) sieve[i] = i;
for(int i = 2; i * i < n; ++i){
if(sieve[i] != i){
continue;
}
for(int j = i * 2; j < n; j += i){
sieve[j] = i;
}
}
}void makeSieve(int n){
vi sieve(n, 2);
sieve[0] = 0;
sieve[1] = 1;
for (int i = 2; i < n; ++i){
for(int j = i * 2; j < n; j+=i){
++sieve[j];
}
}
}void makeSieve(int n){
vi sieve(n, 1);
sieve[0] = 0;
for (int i = 2; i < n; ++i){
for (int j = i; j < n; j += i){
sige[j] += i;
}
}
}The greatest common divisor between two numbers is the largest number that divides both of them.
int gcd(int a, int b){
if (b == 0) return a;
return gcd(b, a % b);
}The least common multiplier between two numbers is the smallest number that can be divided by both of them.
It is a data structure that is used to store a set of strings, based on their prefixes.
Given the list of strings:
- camp
- icpc
- casa
- caso
We can build their trie:
graph LR
r((root)) --> c((c))
r((root)) --> i((i))
c((c)) --> a((a))
a((a)) --> s((s))
a((a)) --> m((m))
s((s)) --> o((o))
s((s)) --> a2((a))
m((m)) --> p((p))
i((i)) --> c2((c))
c2((c)) --> p2((p))
p2((p)) --> c3((c))
A trie has the property of having the strings sorted implicitly when building itself.
struct Node{
map<char, long long> next;
bool end = false;
}
vector<Node> trie;
long long currNode = 0;
long long newNode(){
trie.push_back(Node());
return currNode++;
}void add(string& s){
long long pt = 0;
for(long long i = 0; i < s.size(); i++){
if(!trie[pt].next.count(s[i])){
trie[pt].next[s[i]] = newNode();
}
pt = trie[pt].next[s[i]];
}
trie[pt].end = true;
}void remove(string& s){
long long pt = 0;
for(long long i = 0; i < s.size(); i++){
pt = trie[pt].next[s[i]];
}
trie[pt].end = false;
}void dfs(long long pt, string s =""){
if(trie[pt].end){
cout << s << endl;
}
for(auto i: trie[pt].next){
s.push_back(i.first);
dfs(i.second, s);
s.pop_back();
}
}Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.
If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!
- Fork the Project
- Create your Feature Branch (
git checkout -b feature/AmazingFeature) - Commit your Changes (
git commit -m 'Add some AmazingFeature') - Push to the Branch (
git push origin feature/AmazingFeature) - Open a Pull Request