r/computerscience • u/Homaderuvas • 16h ago

Help Drop some interesting algorithm problems

Hi guys please kindly share some interesting algorithm problems in the comment section. I did solve many algorithm problems on platforms like codeforces, atcoder, luogu and code chef etc.. looking for some unique ones that are quite challenging and interesting at the same time but kindly don't share open problems .

4 Upvotes

61% Upvoted

19 comments sorted by

View all comments

3

u/beeskness420 13h ago

You are given a directed graph (possibly edge weighted) that is not strongly connected. What is the smallest set of edges you need to make bidirectional to make the graph strongly connected? Find a polytime algorithm or prove no such algorithm exists.

Let's call such a set of edges a "repair set" how many edge disjoint repair sets can you find?

For a graph G and a set of vertices S, if we delete S from G in general we get a disconnected graph. We call a component odd if it has an odd number of vertices. Find S such that the resulting graph has the maximum number of odd sized components.

2

u/beeskness420 13h ago

Some more for fun. Given an array of integers find the longest subsequence that first strictly increases amd then strictly decreases. Give a list of matrices of various sizes find the minimum cost way to insert parethesise such that the total cost ia minimized, where the cost of multiplying an pxq matrix with a qxr matrix is given by pqr.