aryan12's blog

By aryan12, history, 16 months ago, In English

Hello everyone,

We hope you are doing well. We are here to announce that we are now opening sign-ups for UFDS 2024. The program is designed to train students for ZCO, INOI and IOITC.

The following students (and mentors) were all a part of UFDS 2023:

  • All 4 students selected for IOI.
  • All 6 students who represented India at the APIO. They won 2 gold and 2 bronze medals.
  • 1 student reached IOI 2023 with just 10 months of Competitive Programming experience.
  • 9 out of the 10 students who got gold in INOI.

The server also surrounds you with like-minded people, so everyone can help each other.

If you join the program, we will help you by:

  • Setting contests to improve your skills
  • Compiling useful practice problem sets to introduce you to a variety of different techniques
  • Selecting problems to practice with
  • Providing hints to solve problems in practice
  • Discussing problems after a contest
  • Recommending similar problems (if you’d like to reinforce a trick/observation)
  • Providing debugging assistance
  • Finding tutorials for classical techniques
  • Hosting sessions to teach/discuss classical techniques
  • Hosting sessions to teach/discuss specific problems

Most importantly, joining the server gives you access to sample ZCO and INOI sets for you to practice on. The majority of participants rate this as the most important element of their preparation.

This program is only applicable to students eligible for ICO. If you think you'd benefit from the mentorship, feel free to apply at our form here.

Links to the previous mentoring programs:

Regards,

UFDS 2024 Mentoring Team.

kshitij_sodani, socho, smjleo, Dominater069, inventiontime, PoPularPlusPlus, aryan12.

Full text and comments »

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

By aryan12, 3 years ago, In English

Before the tutorial, I would like to thank shiven, socho and animeshf for their valuable comments and for improving the tutorial.

Definition of Bridges

Bridges are those edges in a graph, which upon removal from the graph will make it disconnected.

Pre-Requisites

Finding the bridges in a graph.

Introduction

The idea of a bridge tree is to shrink the maximal components without a bridge into one node, leaving only the bridges of the original graph as the edges in the bridge tree.

In the above image, the bridges of the graph are marked in red. They are the edges between the nodes $$$(3, 4)$$$ and $$$(3, 9)$$$. The maximal components without a bridge are $$$[1, 2, 3]$$$, $$$[4, 5, 6, 7, 8]$$$, $$$[9, 10, 11,12]$$$.

Thus, the bridge tree of the graph will become as follows:

The bridge tree only has $$$3$$$ nodes. The nodes $$$[1, 2, 3]$$$ in the original graph have been shrunk to node $$$1$$$, nodes $$$[4, 5, 6, 7, 8]$$$ have been shrunk to node $$$2$$$, and the nodes $$$[9, 10, 11, 12]$$$ have been shrunk to node $$$3$$$.

Note: Throughout the tutorial, we assume that the given graph is undirected, unweighted and connected.

Properties of the bridge tree

All the bridges of the original graph are represented as edges in the bridge tree.

Proof

The bridge tree is connected if the original graph is connected.

Proof

The bridge tree does not contain any cycles.

Proof

The bridge tree will contain $$$\le N$$$ nodes, where $$$N$$$ is the number of nodes in the original graph.

Proof

The bridge tree will contain $$$\le N - 1$$$ edges, where $$$N$$$ is the number of nodes in the original graph.

Proof

Pseudocode for making the bridge tree

dfs(int node, int component_number) {
    component[node] = component_number //All nodes with the same component number will be shrunk into one node in the bridge tree. This is because we aren't traversing a bridge, and thus, "shrinking" the components without a bridge to one node in the bridge tree.
    vis[node] = true //so that we don't visit this again.
    for every adjacent edge such that the edge is not a bridge {
        next = other endpoint of the edge
        if vis[next] = true: continue //already visited this node.
        dfs(next, component_number);
    }     
}

main() {
    Find all the bridges in the graph //check the pre-requisites section of this blog for this
    for i in 1, 2, 3, ..., n and vis[i] = false { 
        call dfs(i, unique_component_number) //ensure the component number is unique. A simple way to do it is just by incrementing it by 1 whenever you are calling the dfs function.
    }

The time complexity of making the bridge tree

In this section, $$$N$$$ stands for the number of nodes and $$$M$$$ stands for the number of edges in the original graph. The bridges in the graph can be found in $$$O(N + M)$$$. The time complexity for the DFS function is $$$O(N + M)$$$. Note that we can store the ID of the edge alongside the adjacent node in the adjacency list. We can have an array isBridge, and mark isBridge[edge] = true for every edge which is a bridge. During the DFS, just check if the current edge is marked as a bridge using its stored ID.

Thus the total time complexity will be $$$O((N + M) + (N + M))$$$, which is equivalent to $$$O(N + M)$$$.

Sample problem

We are going to solve this problem.

Let us understand the statement first.

There is a connected, unweighted, undirected graph with $$$N$$$ nodes and $$$M$$$ edges.

According to the statement, for some fixed starting node $$$s$$$ and ending node $$$t$$$, your friend will place a boss in each passage such that it is impossible to travel from $$$s$$$ to $$$t$$$ without using this passage. The word impossible tells us that the bosses can only be placed on bridges.

Why only on bridges?

Solution

Since we are only concerned regarding the bridges of the graph, we can compress all the maximal components without a bridge into a single node to get the bridge tree of the graph. The bridge tree of the first sample input is depicted below.

You can see that the nodes $$$[1, 2, 3]$$$ in the original graph are shrunk to node $$$1$$$ in the bridge tree. Similarly, node $$$[4]$$$ is shrunk to node $$$2$$$ and node $$$[5]$$$ is shrunk to node $$$3$$$.

This makes the original problem a lot easier. The only thing left is to choose a path from one node in the bridge tree to the other so that the number of edges (bridges in the original graph) along the way is maximum. This can be solved by finding the diameter of a tree.

You can find my solution here.

Extra Exercise

Can you answer queries of the form find the number of bosses we need to place between fixed $$$s$$$ and $$$t$$$?

Other Problems

  1. 652E, My solution
  2. 555E, My solution
  3. 231E

Feel free to suggest any other problems! I'll add them to this section.

Full text and comments »

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

By aryan12, history, 3 years ago, In English

Hey there!

Today while working on a problem on Polygon, I was randomly logged out of it multiple times. I always attach my session to my IP Address while logging into Polygon.

Everyone knows that logging in back every minute or so is very annoying. I would be really grateful to know a workaround for this, or this issue is fixed MikeMirzayanov.

Thank you.

Full text and comments »

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