Top Recent Blog Posts
By HunterXD, history, 2 days ago,

Today i received a message from (relita9302) a unrated account who said that i could be a tester if i sent a key to another codeforces account (crowdforces), thing that i did, big mistake, i found out that when you sent that key you get some Near reward or something, i don't know about Crypto.

Clearly is a scam and probably more fake accounts will appear, so if you receive a similar message from a stranger, please be careful to NOT answer and report.

PD: English is not my primary language, sorry if i made some mistakes

UPD: It's quite concerning that a lot of you guys recevied similar messages, even people creating fake accounts to get cryptos.

I also noticed that the messages i received got deleted (not sure if that account got deleted or just the messages), but it was exactly the same as striver_07 received.

And i have a question for the people who know about Near: the account that the scammer got is actually linked with my account and will affect future contests? I have been in cf three years and i really don't want to lose this account, rather for an emotional attachment.

Special thanks to MikeMirzayanov for adding a highly noticeable warning, and all the users that make cf a better place.

• +165

By Shiroha_F14, history, 7 hours ago,

Hello. This is my first post and English is not my first language, so please forgive my poor wording.

I received a message just a moment ago. I read this but this message made me confused.

Is this message just a scam? Or really I'm suspected? What is the meaning of this message?

I want to think this is one of a kind of something meaningless...

UPD : Thank you for answers! I'm going to keep a lookout.

• +19

By maroonrk, history, 18 hours ago,

We will hold AtCoder Regular Contest 133.

The point values will be 300-500-500-700-800-1100.

We are looking forward to your participation!

• +99

By aryan12, 8 hours ago,

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.

## 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);
}
}

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

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

• +64

By guptaji30, history, 46 hours ago,

Given an array, arr[] of integers. The task is to sort the elements of the given array in the increasing order of their modulo with 3 maintaining the order of their appearance.

Expect time complexity O(N) and the interviewer said that it can be done in only one/two traversal(s)(sorry I don't remember it clearly, it was quite sometime ago).

Expected space complexity O(1).

• +5

By awoo, history, 4 days ago, translation,

1626A - Equidistant Letters

Idea: BledDest

Tutorial
Solution (awoo)

1626B - Minor Reduction

Idea: BledDest

Tutorial
Solution (awoo)

1626C - Monsters And Spells

Idea: BledDest

Tutorial
Solution (awoo)

1626D - Martial Arts Tournament

Idea: BledDest

Tutorial
Solution (awoo)

1626E - Black and White Tree

Idea: BledDest

Tutorial
Solution (BledDest)

1626F - A Random Code Problem

Idea: BledDest

Tutorial
Solution (BledDest)

• +115

By new2022, history, 3 days ago,

Hello Everyone!
We would like to invite you all to participate in the SPYBITS2022 CONTEST-1 aka the Spybits Number Theory Contest, under the banner of Udyam'22, IIT (BHU) Varanasi. The contest will be held on 28th Jan 2022 at 20:00 IST.

Udyam is the annual technical fest of the Department of Electronics Engineering, Indian Institute of Technology (BHU),Varanasi. To know more about Udyam, please visit the official website of Udyam'22.

Spybits Number Theory Contest is the first round of the SPYBITS event, in which your Number Theory knowledge is tested along with your programming skills. This contest is open to everyone, so you can appear in the contest even if you haven't registered for the SPYBITS event.

All the problems have been prepared by XORring-Samurai, Lazy_Propagater and me, new2022.

We would like to thank sudoSieg and adikrsingh for testing all the problems.

You will get 2 hours to solve 7 problems, all the problems will be majorly based on number theory. The scoring will be of ICPC style, you can learn more about it from the contest page.

I hope you guys will like the problems, Good Luck everyone!

P.S.

In the 'Upcoming Coding contests' section of Codechef, you can see a contest with code SNTC2021 (if you mark 'show all contests') scheduled on 31st May 2022, kindly ignore it for the time being, it is the consequence of a mess created by me, we will see how to fix it later.
Thank You.

• +73

By rivalq, history, 40 hours ago,

COPS is organizing an intra-college multistage competitive programming tournament! The theme for the tournament is based on ‘Squid Games’.

Qualification round of the tournament will held on Saturday, Jan 22, 2022 at 17:00

You will be given a total of 6 problems to be solved in 2 hours. The contest is ICPC-style. Each problem has 1 point. The penalty for a problem equals the time taken (in minutes) to solve the problem from the start of the contest + 20 ×  number of rejected solutions. The total penalty equals the sum of penalties for solved problems.

The problems are not sorted in the order of difficulty, so do give a read to each of the problems.

The contest has been prepared by loud_mouth, CoderAnshu, mallick630, _kira_1008, _whoAreYou, saraff_sunny

There are also prizes worth of 3k (in Rupees) for the tournament winners.

Hope you'll find the problems interesting.

See you on the leaderboard, Good luck!!

• +33

By Topcoder_Updates, history, 9 hours ago,

Topcoder Rookie SRM 9 is scheduled to start at 12:00 UTC-5 on Jan 22, 2022.

Registration is now open for the SRM in the Arena or Applet and closes at 11:55 UTC-5 .The coding phase will start at 12:05 UTC-5, so make sure that you are all ready to go. Click here to see what time it starts in your area.

The Rookie SRMs are open to everyone and has some special prizes. It will only be rated for members who:

• Have never competed in Rated Algorithm Contests OR

• Have competed in equal to or less than 5 rounds OR

• If their current rating is less than 800 rating points.

Prizes:

Topcoder T-shirt for Top 20

*Prizes are only for members who are eligible to be rated

Best of luck!
- The Topcoder Team

Please take a look at our How to Compete guide to understand Topcoder Algorithm rounds better.

Some Important Links:: Match Results (match results, rating changes, challenges, individual test case results), Problem Archive, Problem Writing, Algorithm Rankings, Editorials and Older Editorials(SRM 710 and before),

• +24

By SoMuchDrama, 2 days ago,

Hi Codeforces,

My friends and I want to make competitive programming streams more amusing. We will try to solve easy and medium-level problems being in a non-standard environment. For example, each our wrong attempt will be brutally punished. Still, the main purpose of this stream is, of course, donations educational.

Stream participants: Alexponomarev7, SoMuchDrama, special unrated guests for challenges: drum and guitar songs, some prepared jokes and drinks, and more.

The stream will take place this Thursday, 21:00 MSK, click to see the time in your location.

See you on the stream (twitch link)