ritik_patel05's blog

By ritik_patel05, history, 4 years ago, In English

Hello, codeforces!

I don't know how helpful will this be to anyone, but I thought it would be nice to share it. Before reading this blog, you should be familiar with the concept of Bridges in a graph.

What it can do

  1. Find minimum number of edges to add in a graph, so that there are no bridges.
  2. Add a single edge to minimize the number of bridges in a graph.
  3. Given a graph, and queries in from A B C D: For the current query add an edge between nodes numbered A and B(note that this operation is temporary and only for the current query). Now, output the maximum number of bridge edges occuring on any path between C and D.

What is Bridge Tree of a graph?

One of the formal terms often used to describe Bridge tree is decomposing graph into 2-edge connected components and making a tree of it.

2-edge connected component in simple terms is a set of vertices grouped together into a component, such that if we remove any edge from that component, that component still remains connected. In short, it's a component which doesn't have any bridges in it.

So, how can we make bridge tree of a graph?

In Bridge Tree we will have => Nodes as:-> 2-edge connected components. and, edges as:-> Bridge connecting two different components.

Example, Consider we have a graph. (Red line edge is a bridge)

Graph0

It's Bridge Tree would be,

Graph1

How to implement

  1. Find bridges in the graph and mark them.
Code
  1. Remove the bridge from the graph.
  2. Run dfs/dsu or bfs whichever way you prefer to group one components and give vertices the component id in which they belong. (Note: Remove bridge means: while traversing make sure not to cross the bridge, so we can group vertices of one component)
Code
  1. Traverse every edge, if it is a bridge, connect the two components via an edge.
Code

Alternative Implementation:

There is also alternative implementation using dfs and queues(bfs) mentioned in this blog which is also on this same topic. Link

Honestly, i think using just dfs to find components is intuitively to me and easy to code. You can use any approach you like.

Full Code:

Code Link

Code

Thanks to

I already found this blog about Bridge tree on quora(Link) but I found implementation hard to interpret. Also, thanks to Algorithms Live Channel on Youtube which really helped me to clear concepts on Bridge Finding and forming 2 edge connected component tree of a graph and biconnected components in general.

Problems

  1. 652E , Submission using Above implementation.
  2. H-Bridges, Submission using above implementation.
  3. 178-B3
  4. Sherlock and Queries on the Graph- HackerRank
  5. 1000-E
  6. 732-F
  7. 6044-Unique Path-ICPC Live Archive
  8. 700-C

If you have any doubts regarding explanation, you can ask in comments. Also, if you have solved problems related to it, please share it here, I will update the Problems section.

Have a great day!

Full text and comments »

  • Vote: I like it
  • +41
  • Vote: I do not like it

By ritik_patel05, history, 4 years ago, In English

I have been trying to solve this problem, but I am not able to find any good approach.

Problem: Problem Link

To view the problem and submit maybe, you have to first join the group:

Group Link

After joining the group, you can view and submit the problem.

Here I am attaching the text of problem.

Problem Text

Thank you very much for your time and for helping me.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By ritik_patel05, history, 5 years ago, In English

Problem : HELPR2D2 — Help R2-D2!

Solution : Link

Approach : I stored in each leaf node K(Volume left to use) and in the parent node, I summed up the volume of children's node. For querying, I try to go as much left as I can and update the volume used. I cross-checked with several cases. But cannot find where it's going wrong on submission.

If someone has solved this question, I really appreciate your help. Thank you!

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it

By ritik_patel05, history, 5 years ago, In English

Problem: https://codeforces.me/contest/4/problem/D

Solution: https://codeforces.me/contest/4/submission/73546246

What I am doing is first sorting indexes with given height and width in increasing order. Then I am making a recursive function to calculate longest chain. Whenever I reach an index, I have 2 options either include or don't include it.

I have been trying to find for long why am I getting the wrong answer. But I have no clue.

It would be great if someone could point out my error in thinking.

Thank you :)

Full text and comments »

  • Vote: I like it
  • +3
  • Vote: I do not like it

By ritik_patel05, history, 5 years ago, In English

Problem : https://codeforces.me/contest/1288/problem/C

My solution: https://codeforces.me/contest/1288/submission/68821660

Can anyone tell while I calculate dp[pos][i][j], I am using O(n*n) to calculate for each pair. Can I optimize by using some precalculated sum array, as we do in 1D case to get the sum for a particular range in an array?

In my code, I have written this, //to calculate dp[pos][i][j] //using dp[pos — 1][previ][prevj]

How can I do this in O(1) to fit in timelimit?

I am thinking about this optimization for a long time, but I got to nowhere.

It would be great if there is any way to do it.

Thank you :)

Have a great day!

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By ritik_patel05, history, 5 years ago, In English

Problem : https://atcoder.jp/contests/abc148/tasks/abc148_f

How did you solved this problem? It would be better if you can give your intuition along with your approach.

Thank you.

Full text and comments »

  • Vote: I like it
  • +14
  • Vote: I do not like it