Drop some interesting algorithm problems

[u/Homaderuvas]

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 .

[u/beeskness420]

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.

[u/beeskness420 → u/beeskness420]

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.

[u/CerealConMiel → u/beeskness420]

For the first problem, is the answer the number of strongly connected components minus 1?

[u/beeskness420 → u/CerealConMiel]

Not always no, that does give an easy upperbound.

[u/Magdaki]

Given a sequence of symbolic data produced by some process, infer a grammatical computational model (ideally the simplest) that produces the data.

If you find anything, then let me know and we'll publish a paper together.

[u/Humble-Captain3418 → u/Magdaki]

Can you elaborate this problem a little further? Especially what "grammatical computational model" means. I should be fine reading literature on the matter, too.

[u/Magdaki → u/Humble-Captain3418]

Suppose you have some process that produces data, i.e. a generative process. You've replaced the data with a sequence of symbols in a problem specific representational way. The question is: is some underlying grammar that describes the developmental sequence and if so what is it?

For example:

ABA
ABABBBABA
ABABBBABABBBBBBBBBABABBBABA

The grammar (in this case an L-system) that describes this developmental sequence is A -> ABA and B -> BBB.

For deterministic cases, there's already good algorithms for inferring this, although they could be improved (I have a paper being written right now on just such an improvement). The really challenging case is when there are errors in the strings, missing strings, or non-determinism.

E.g.

ABA
ABBABBBABA
ABABBBBABABBBBBBBAABABBBAA

This is much harder. My RAs and I are currently working on this type of problem. We recently also cracked the non-visual problem too (same paper as above). That's a bit hard to describe so don't worry about it.

This is my core research area.

Even trying to reproduce my work on this without looking it up would be good algorithms practice.

By the way, the solution need not be an L-system. Recently (well ok a few years ago), my research group branched out into other types of grammatical inference. So feel free to pick something else too. The core of it is given some data produced by (or believed to be produced by) some type of grammar, infer the grammar.

[u/Humble-Captain3418 → u/Magdaki]

I am kind of curious, wouldn't both cases be matched by A->ABA and B->BB?

[u/Magdaki → u/Humble-Captain3418]

Unless I made a typo, it shouldn't.

[u/AbleActuary5795 → u/Magdaki]

I assume the interesting part is identifying the minimal grammar that contains exactly all (or some error-free subset) of the outputs of the original system. Does the non-determinism come into play where some particular rules only occur with a given frequency? 

W.r.t. errors, for any sufficiently large sample of system outputs of size n, you could construct G* as your initial minimal grammar. You can then identify the rules that are only used for k<<n items in the sampled output, eliminate those rules and construct the refined G**. Repeat until no rules are removed.

[u/Achrus → u/Magdaki]

Really interesting work! I love this kind of stuff. Is this strictly for context free grammars? Also, will mapping the sequence to the grammar always result in “compression” of the sequence?

My immediate thoughts went to using an MLM to infer the higher order structure like for proteins or the Chinese character problem. To handle errors At least. Or like a fuzzy, hierarchical BPE where you could set bounds on expected error rates and how lossy the “compression” is.

[u/Magdaki → u/Achrus]

No, I do inference of context free & sensitive, stochastic, parametric, and graph grammars currently. Always branching out.

In fact, I'm writing a theory paper in a "newish" grammar formalism that will be useful for general purpose inference. If I ever get the time to work on it. Which is never. It has been half done now for 1.5 years. LOL

[u/cc672012]

Check out projecteuler

[u/cc672012 → u/cc672012]

Also cryptopals for something similar but cryptography related stuff

[u/Homaderuvas → u/cc672012]

Thanks for this I never heard cryptopal

[u/Homaderuvas → u/cc672012]

I did complete most of problem on project Euler for the last 3 years

[u/Disastrous-Doubt-909]

I adapted this from a maths problem

You are given an integer N and an array A containing exactly N + 1 integers.

Count the number of pairs of indices (i, j) such that:

0 ≤ i < j < N + 1

(A[i] - A[j]) is divisible by N.

Two elements with the same value are considered different if they occur at different indices.

Choose N large enough that an O(N²) brute-force solution will not pass.