User salarwang27

From Codeforces, Pierre Elliott Trudeau H.S., Olympiads School

About

Salar Wang '23

Spaces --> Tabs --> Spaces

TODO:

First I'm grinding DM::OJ for some Algorithm and Data Structure knowledge, then I will migrate to Codeforces to train my ad-hoc skills.

Binary search is actually pretty hard :(

Codeforces Binary Search EDU

Delimiter

vector<string> split(string s, char delimiter) {
    vector<string> tokens;
    string token;
    istringstream tokenStream(s);
    while(getline(tokenStream, token, delimiter)) {
        tokens.push_back(token);
    }
    return tokens;
}

Struct Sorting

Please watch out with using friend bool operator<(T &a, T &b). This code will produce the following with the Sample Input.

#include <bits/stdc++.h>
using namespace std;
struct Edge {
    int w;
    friend bool operator<(const Edge &a, const Edge &b) {
        return a.w > b.w;
    }
};

int main() {
    int n;
    scanf("%i", &n);
    vector<Edge> v(n);
    priority_queue<Edge> q;
    for(auto &x : v) {
        scanf("%i", &x.w);
        q.push(x);
    }
    printf("Priority Queue: ");
    while(!q.empty()) {
        auto cur = q.top(); q.pop();
        printf("%i ", cur.w);
    }
    printf("\nSorting: ");
    sort(begin(v), end(v));
    for(auto &x : v) {
        printf("%i ", x.w);
    }
    return 0;
}

Sample Input

20
51 11 21 79 36 61 9 61 39 85 37 30 37 40 79 16 95 72 24 51

Sample Output

Priority Queue: 9 11 16 21 24 30 36 37 37 39 40 51 51 61 61 72 79 79 85 95
Sorting: 95 85 79 79 72 61 61 51 51 40 39 37 37 36 30 24 21 16 11 9

Dijkstra's Algorithm

A little tip

priority_queue<pii, vector<pii>, greater<>> q;
q.push({d_s, s});
while(!q.empty()) {
    auto cur = q.top(); q.pop(); // DO NOT USE auto &cur IT DOES NOT WORK
}

DMOPC '14 Exam Time P4 - Exam Delay

The reason it's ans * 60 * 1 / 3 is because (1) we convert from hours to minutes and (2) the speed is $75\%$ ~75\%~ or $3 / 4$ ~3 / 4~ the regular speed. Thus when find time by dividing the distance by the speed we multiply by the reciprocal so by $4 / 3$ ~4 / 3~. $4 / 3 * time$ ~4 / 3 * time~ is the final time. To get the amount delayed we do $4 / 3 * time - time$ ~4 / 3 * time - time~ - subtract $4 / 3$ ~4 / 3~ by $1$ ~1~ and we get $1 / 3$ ~1 / 3~. Thus the delayed amount is $time * 60 * 1 / 3$ ~time * 60 * 1 / 3~.
Make sure to store the answer before printing it in scanf("%i\n", ans);

WC '15 Contest 1 S3 - Contest Sites

A few cases we consider after running Dijkstra's from cities $1$ ~1~ and $2$ ~2~. Watch out for the edge case where $C_i = 0$ ~C_i = 0~ and check if both distances from $dist(1, i)$ ~dist(1, i)~ and $dist(2, i)$ ~dist(2, i)~ are $\infty$ ~\infty~. You don't want to stop and print -1 since there's no one there to not go, so we do not print -1 if $C_i = 0$ ~C_i = 0~ and $dist(1, i) = dist(2, i) = \infty$ ~dist(1, i) = dist(2, i) = \infty~.

Mostly Talking

This is pretty similar to Convex Hull where you can use multi-dimension distance array where in Convex Hull its dist[total dist][hull taken] while in Mostly Talking its simply dist[total dist][true/false called Cindy]

CCC '10 S4 - Animal Farm

The construction of the edge list for Kruskal's can be thought of as the following: For every connection ( $corner_1$ ~corner_1~ ↔ $edge$ ~edge~ ↔ $corner_2$ ~corner_2~) we can store this connection in a 2D array of vector pairs (vector<pair<int, int>> dual[1005][1005]) where $dual[i][j]$ ~dual[i][j]~ represents a list of $\{pen, cost_{edge}\}$ ~\{pen, cost_{edge}\}~ pairs divided by the edge formed by corners $i$ ~i~ and $j$ ~j~. Thus, when a $dual[i][j]$ ~dual[i][j]~ contains 2 pens (int(dual[i][j].size()) == 2) we can add the $pen$ ~pen~ and $cost_{edge}$ ~cost_{edge}~ to our edge list. Then, run Kruskal's on the current edge list and store the result. Reset the edge list, and add all $dual[i][j]$ ~dual[i][j]~ such that they are connecting to the outside of the barn/they only connect one pen (int(dual[i][j].size()) == 1) since the animals can meet outside the barn. Run Kruskal's on the edge list with the newly added edges and store the result. Take the minimum of the two results and print your answer! :)

DMPG '15 S6 - Apples to Oranges

This question essentially pertains to the idea of a negative cycle. So, in order to detect said "negative cycle" we need to use an algorithm like Bellman-Ford. However, instead of using our classic relaxation formula of $dist(v) = min(dist(v), dist(u) + w)$ ~dist(v) = min(dist(v), dist(u) + w)~ we actually do $dist(v) = max(dist(v), dist(u) * w)$ ~dist(v) = max(dist(v), dist(u) * w)~. We multiply because we attempt to exchange all fruits of type $u$ ~u~ to fruits of type $v$ ~v~. Thus, instead of the initial $dist$ ~dist~ array containing $\infty$ ~\infty~, it contains $0s$ ~0s~. Using Bellman-Ford if we attempt to relax the fruit APPLES more than $N$ ~N~ times, we know there is a cycle and thus can print YA otherwise NAW.

TLE '16 Contest 1 P4 - Microwaves Again!

For this problem we will first find all-pairs shortest path using an algorithm such as Floyd-Warshall's. Once we have precomputed all-pairs of shortest paths, we can create another matrix that determines whether the shortest path from $i$ ~i~ to $j$ ~j~ is less than or equal to $k$ ~k~ for all $i$ ~i~ and $j$ ~j~. We can use a vector of bitsets and set the $j^{th}$ ~j^{th}~ bit to mark it as visitable (dist is less than or equal to $k$ ~k~). We can then brute force all combinations of 3 different rooms to perform the Atomic Blast and for a specific combination, we will "flatten" the bitsets of all 3 rooms to determine all rooms visitable from those 3 rooms. We can them simply run a loop to determine the total number of microwaves destroyed by adding the number of microwaves at each room to a sum if the bit is set at that room. Print the maximum of all sums.

DMOPC '16 Contest 2 P4 - Zeros

We can observe the monotonic property of the number of zeros has with a factorial. Thus, since the number of trailing zeros is monotonic, we can perform binary search. In order to find the number of numbers that contain $[a, b]$ ~[a, b]~ trailing zeros, we simply need to find the first number with $>= a$ ~>= a~ trailing zeros and the first number with $> b$ ~> b~ trailing zeros (since we want to include all numbers that have $b$ ~b~ trailing zeros). We can find the number of trailing zeros that a $N!$ ~N!~ has by counting the number of factors of $5$ ~5~s that are contained within the range $[1, N]$ ~[1, N]~. This can be done by taking the $\sum_{n=1}^{\infty} {\left \lfloor \frac{N}{5^i} \right \rfloor}$ , in other words, counting the number of factors of $5$ ~5~, $25$ ~25~ (since a number can include two $5$ ~5~s), $125$ ~125~, etc... We can stop taking the sum when $5^i$ ~5^i~ is greater than $x$ ~x~. Perform a simple binary search to find the first $N_1$ ~N_1~ with $>= a$ ~>= a~ trailing zeros and the first $N_2$ ~N_2~ with $> b$ ~> b~ trailing zeros. The result will be $N_2 - N_1$ ~N_2 - N_1~. Remember the range of the binary search starts at $1$ ~1~ since, the problem defines $1$ ~1~ as the start of the natural numbers.

WC '15 Finals S2 - Hydration

For this problem, we should notice that the amount of time it takes for a set of cows to finish is the maximum number of cows at a trough. Furthermore, we should notice that if all cows can finish drinking water in $m$ ~m~ seconds, then they can also do so in $m + 1$ ~m + 1~ seconds. Thus, let $f(x)$ ~f(x)~ represent whether the cows can finish drinking in $x$ ~x~ seconds. The function will be binary and will look something like $0000...0001111...1111$ ~0000...0001111...1111~. Notice that it is monotonic, and thus we can perform binary search to find the first instance of $1$ ~1~/the minimum time, $x$ ~x~, it takes for the cows to finish hydrating. To check whether the cows can finish drinking within $x$ ~x~ seconds, sort the cows and the troughs by height. We can greedily assign troughs. Assign the cow $i$ ~i~ with the minimum trough $j$ ~j~ such that the number of cows at trough $j$ ~j~ does not exceed $x$ ~x~ and it is a valid trough that the cow $i$ ~i~ can drink from. Once we process all the cows and notice that $i < N$ ~i < N~ (there are still cows to process) and $j >= M$ ~j >= M~ (there are no more troughs left), then $f(x)$ ~f(x)~ for that instance will be equal to $0$ ~0~. Change the search range accordingly.

CCC '10 S3 - Firehose

For this problem, we require binary search. We will binary search on the minimum length used $m$ ~m~. This can be observed since similar to the previous question where if we can place $K$ ~K~ fire hydrants with minimum length $m$ ~m~, then we can also place $K$ ~K~ fire hydrants with minimum length $m+1$ ~m+1~. Thus the function $f(m)$ ~f(m)~ will once again look something like $000...000111...111$ ~000...000111...111~. Thus we must find the first instance of $1$ ~1~, the minimum length where $K$ ~K~ fire hydrants can be placed. Now the question remains, how do we know if we can place $K$ ~K~ fire hydrants such that the max distance between any house is at most $m$ ~m~? Well, we know that it is always better to place a fire hydrant between 2 houses, and we also know that the maximum length between any two houses should be $m$ ~m~ (the mid value from binary search). First, we will sort the houses by length. Then, we will note a "pivot" house, $i$ ~i~, and loop through all the other houses, $j$ ~j~. When the distance between the pivot house, $i$ ~i~, and the house current house in the iteration, $j$ ~j~, (either way around the circle) is greater than $\frac{m}{2}$ ~\frac{m}{2}~, then we should place a fire hydrant between house $j$ ~j~ and $j-1$ ~j-1~. Once we placed all fire hydrants, check if this value is $\leq K$ ~\leq K~ or $> K$ ~> K~, and move the bounds of our search range accordingly -- If it is $\leq K$ ~\leq K~ there may be some values better on the left, and if it is $> K$ ~> K~, we need to increase the minimum distance between the houses and the fire hydrants, so look right. Additionally, we should start the first pivot house at all houses from $0$ ~0~ to $N$ ~N~.

Dijkstra's $O((V+E)logV)$ ~O((V+E)logV)~ implementation

#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5 + 5;
using pii = pair<int, int>;
vector<pii> adj[MN];
int dist[MN];
int main() {
    int N, M, S, T;
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v, w);
        adj[v].emplace_back(u, w);
    }
    cin >> S >> T;
    priority_queue<pii, vector<pii>, greater<>> pq;
    memset(dist, 0x3f, sizeof dist);
    pq.push({0, S});
    dist[S] = 0;
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        int u = cur.second;
        for (auto & [v, w] : adj[u]) {
            int d = dist[u] + w;
            if (d < dist[v]) {
                dist[v] = d;
                pq.push({d, v});
            }
        }
    }
    cout << dist[T] << endl;
    return 0;
}

Dijkstra's $O(V^2)$ ~O(V^2)~ implementation

#include <bits/stdc++.h>
using namespace std;
const int MN = 1e5 + 5;
using pii = pair<int, int>;
int adj[MN][MN];
int dist[MN];
bool vis[MN];
int main() {
    int N, M, S, T;
    cin >> N >> M;
    for (int i = 0; i < M; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u][v] = adj[v][u] = w;
    }
    cin >> S >> T;
    memset(dist, 0x3f, sizeof dist);
    dist[S] = 0;
    for (int it = 0; it < N; ++it) { // just iterate N times
        int u = 0;
        for (int i = 1; i <= N; ++i) { // find unvisited node with smallest dist
            if (!vis[i] && dist[i] < dist[u]) {
                u = i;
            }
        }
        vis[u] = true;
        for (int v = 1; v <= N; ++v) {
            int d = dist[u] + adj[u][v];
            if (!vis[v] && d < dist[v]) {
                dist[v] = d;
            }
        }
    }
    cout << dist[T] << endl;
    return 0;
}

Problems to re-do:

Interesting Problems:

TLE '15 P5 - Prefix Sum Array (20/100)
A Coin Game - I really like this problem because it still uses BFS but makes the nodes into a state (which coins are on which stack). Pretty cool!

To-do list (12/29):

Review ✔️
Math ✔️
PSDA ✔️
Graph ✔️
BFS/DFS ✔️
Dijkstra ✔️
Prim's ✔️ (This is a pretty stupid algorithm)
Disjoint Set & Kruskal's ✔️
SPFA & Floyd Warshall ✔️
Binary Search ✔️ (Continue practicing binary search on CF)
Greedy 🟡 (I'll do some more on CF)
Dynamic Programming ✔️
Knapsack ✔️
LIS ✔️
String DP ✔️
Interval DP ✔️
Bitmask DP ✔️
Geometry ✔️
Polygon ✔️
Linesweep
Segment Tree
Lazy Propagation
Binary Indexed Tree
Splay Tree
Tarjan SCC
Heavy-Light Decomposition
Max flow
Bipartite Matching
Strings

56543baadad9454cbe86288dbd2e081ef12cb29a5c5bc8b89be64991b2cd91e8

Sun
Mon
Tues
Wed
Thurs
Fri
Sat