searleser97's blog

By searleser97, 4 weeks ago, ,

cpbooster

Hi Codeforces,

I wanted to share with you my latest project: cpbooster which stands for "Competitive Programming Booster". It is a cross-platform CLI tool designed to boost competitive programmer's speed during contests. The console command suits any coding environment and it’s very simple to use. Vim users can install cpbooster.vim plugin to boost their speed even more. I hope you like it!.

Usage

Note: Run cpbooster <command> --help to display help information about an specific command.

Vim Usage (Commands)

Command Description
:Test [id] Test your current code against all available testcases for it,
or just one testcase if [id] is set.
:Debug [id] Run your current code with your debugging flags,
or run it against one testcase if [id] is set.
:Create <filename> Create source file loading the corresponding
template for the file extension.
:Rtest [id] Test the last compiled version of your code.
Same as :Test but without recompiling.
:Rdebug [id] Debug the last compiled version of your code.
Sames as :Debug but without recompiling.

Features

• Automatically clone sample testcases files into an specific directory
• Create source files from a template
• Test your code against sample testcases quickly.
Supported results:
• AC (Accepted)
• TLE (Time Limit Exceeded)
• RTE (Runtime Error)
• CE (Compilation Error)
• Run code with your own debugging flags easily

For installation instructions and more details visit: https://github.com/searleser97/cpbooster

• +60

By searleser97, 4 months ago, ,

mkcpr

I would like to share a command line utility I made that helped me to build my competitive programming reference for ICPC contests. Hopefully it can help more people :D.

mkcpr is a command line utility that helps you to build your competitive programming reference PDF.

Features

• Forget about undesired line breaks by specifying the lines of code you want together in the same page with a single comment before your lines of code.
• One single command and your reference will be ready to compile
• Easy setup with a single json file
• Highly configurable

Usage

python mkcpr [CONFIG FILE PATH]


The above command will generate a Tex file, which can be compiled with any online or local Tex compiler of your preference.

Configuration File Options

{
"codeFolder" : "Code Folder Path", // Path to your actual code for reference
"templatePath" : "template.tex", // LaTex template path
"outputFilePath" : "output.tex", // path where you want the LaTex code
"excluded" : [".vscode", "__pycache__"], // folders not to consider
"columns" : 2, // number of columns in your reference
"templatePlaceHolder" : "CODE HERE", // text to replace in your template
"sortBefore" : ["Data Structures"], // files or folders will appear first
"sortAfter" : ["Extras"] // file or folders will appear at the end
}


For more details visit: https://github.com/searleser97/mkcpr

• +16

By searleser97, 9 months ago, ,

Articulation Points

Let's define what an articulation point is. We say that a vertex $V$ in a graph $G$ with $C$ connected components is an articulation point if its removal increases the number of connected components of $G$. In other words, let $C'$ be the number of connected components after removing vertex $V$, if $C' > C$ then $V$ is an articulation point.

Naive approach O(V * (V + E))

For every vertex V in the graph G do
Remove V from G
if the number of connected components increases then V is an articulation point


Tarjan's approach O(V + E)

First, we need to know that an ancestor of some node $V$ is a node $A$ that was discoverd before $V$ in a DFS traversal.

In the graph $G_1$ shown above, if we start our DFS from A and follow the path to C through B ( A -> B -> C ), then A is an ancestor of B and C in this spanning tree generated from the DFS traversal.

Example of DFS spanning trees of a graph

Now that we know the definition of ancestor let's dive into the main idea.

Idea

Let's say there is a node $V$ in some graph $G$ that can be reached by a node $U$ through some intermediate nodes (maybe non intermediate nodes) following some DFS traversal, if $V$ can also be reached by $A$ = "ancestor of $U$" without passing through $U$ then, $U$ is NOT an articulation point because it means that if we remove $U$ from $G$ we can still reach $V$ from $A$, hence, the number of connected components will remain the same.

So, we can conclude that the only 2 conditions for $U$ to be an articulation point are:

1. If all paths from $A$ to $V$ require $U$ to be in the graph.

2. If $U$ is the root of the DFS traversal with at least 2 children subgraphs disconnected from each other.

Then we can break condition #1 into 2 subconditions:

• $U$ is an articulation point if it does not have an adyacent node $V$ that can reach $A$ without requiring $U$ to be in $G$.

• $U$ is an articulation point if it is the root of some cycle in the DFS traversal.

Examples:

Here B is an articulation point because all paths from ancestors of B to C require B to be in the graph.

Here B is NOT an articulation point because there is at least one path from an ancestor of B to C which does not require B.

Here B is an articulation point since it has at least 2 children subgraphs disconnected from each other.

Implementation

Well, first thing we need is a way to know if some node $A$ is ancestor of some other node $V$, for this we can assign a discovery time to each vertex $V$ in the graph $G$ based on the DFS traversal, so that we can know which node was discovered before or after another. e.g. in $G_1$ with the traversal A -> B -> C the dicovery times for each node will be respectively 1, 2, 3; with this we know that A was discovered before C since discovery_time[A] < discovery_time[C].

Now we need to know if some vertex $U$ is an articulation point. So, for that we will check the following conditions:

1. If there is NO way to get to a node $V$ with strictly smaller discovery time than the discovery time of $U$ following the DFS traversal, then $U$ is an articulation point. (it has to be strictly because if it is equal it means that $U$ is the root of a cycle in the DFS traversal which means that $U$ is still an articulation point).

2. If $U$ is the root of the DFS tree and it has at least 2 children subgraphs disconnected from each other, then $U$ is an articulation point.

So, for implementation details, we will think of it as if for every node $U$ we have to find the node $V$ with the least discovery time that can be reached from $U$ following some DFS traversal path which does not require to pass through any already visited nodes, and let's call this node $low$.

Then, we can know that $U$ is an articulation point if the following condition is satisfied: discovery_time[U] <= low[V] ( $V$ in this case represents an adjacent node of $U$ ). To implement this, in each node $V$ we will store some identifier of its corresponding node $low$ found, this identifier will be the corresponding $low's$ discovery time because it helps us to know when the node $low$ was discovered, hence it helps us to know by which node we can discover $U$ first.

C++ Code

// adj[u] = adjacent nodes of u
// ap = AP = articulation points
// p = parent
// disc[u] = discovery time of u
// low[u] = 'low' node of u

int dfsAP(int u, int p) {
int children = 0;
low[u] = disc[u] = ++Time;
for (int& v : adj[u]) {
if (v == p) continue; // we don't want to go back through the same path.
// if we go back is because we found another way back
if (!disc[v]) { // if V has not been discovered before
children++;
dfsAP(v, u); // recursive DFS call
if (disc[u] <= low[v]) // condition #1
ap[u] = 1;
low[u] = min(low[u], low[v]); // low[v] might be an ancestor of u
} else // if v was already discovered means that we found an ancestor
low[u] = min(low[u], disc[v]); // finds the ancestor with the least discovery time
}
return children;
}

void AP() {
ap = low = disc = vector<int>(adj.size());
Time = 0;
for (int u = 0; u < adj.size(); u++)
if (!disc[u])
ap[u] = dfsAP(u, u) > 1; // condition #2
}


Bridges

Let's define what a bridge is. We say that an edge $UV$ in a graph $G$ with $C$ connected components is a bridge if its removal increases the number of connected components of $G$. In other words, let $C'$ be number of connected components after removing edge $UV$, if $C' > C$ then the edge $UV$ is a bridge.

The idea an implementation is exactly the same as for articulation points except for one thing, to say that the edge $UV$ is a bridge, the condition to satisfy is: discovery_time[U] < low[V] instead of discovery_time[U] <= low[V]. Notice that the only change was comparing strictly lesser instead of lesser of equal.

But why is this ?

If discovery_time[U] is equal to low[V] it means that there is a path from $V$ that goes back to $U$ ( $V$ in this case represents an adjacent node of $U$ ), or in other words we can just say that we found a cycle rooted in $U$. For articulation points if we remove $U$ from the graph it will increase the number of connected components, but in the case of bridges if we remove the edge $UV$ the number of connected components will remain the same. For bridges we need to be sure that the edge $UV$ is not involved in any cycle. A way to be sure of this is just to check that low[V] is strictly greater than discovery_time[U].

In the graph shown above the edge $AB$ is a bridge because low[B] is strictly greater than disc[A]. The edge $BC$ is not a bridge because low[C] is equal to disc[B].

C++ Code

// br = bridges, p = parent

vector<pair<int, int>> br;

int dfsBR(int u, int p) {
low[u] = disc[u] = ++Time;
for (int& v : adj[u]) {
if (v == p) continue; // we don't want to go back through the same path.
// if we go back is because we found another way back
if (!disc[v]) { // if V has not been discovered before
dfsBR(v, u);  // recursive DFS call
if (disc[u] < low[v]) // condition to find a bridge
br.push_back({u, v});
low[u] = min(low[u], low[v]); // low[v] might be an ancestor of u
} else // if v was already discovered means that we found an ancestor
low[u] = min(low[u], disc[v]); // finds the ancestor with the least discovery time
}
}

void BR() {
Time = 0;
for (int u = 0; u < adj.size(); u++)
if (!disc[u])
dfsBR(u, u)
}


FAQ

• Why low[u] = min(low[u], disc[v]) instead of low[u] = min(low[u], low[v]) ?

Let's consider node C in the graph above, in the DFS traversal the nodes after C are: D and E, when the DFS traversal reaches E we find C again, if we take its $low$ time, low[E] will be equal to disc[A] but at this point, when we return back to C in the DFS we will be omitting the fact that $U$ is the root of a cycle (which makes it an articulation point) and we will be saying that there is a path from E to some ancestor of C (in this case A) which does not require C and such path does not exist in the graph, therefore the algorithm will say that C is NOT an articulation point which is totally false since the only way to reach D and E is passing through C.

Problems

315 Network (Points)

610 Street Directions (Bridges)