2
$\begingroup$

I'm actually trying to solve a task from an old OII (Italian national pre-IOI competition) in which I'm given an unweighted directed graph $G$ with $N$ vertices and $M$ edges and I'm asked to find a set of vertices $S$ which satisfies these conditions.
If we call $S^1$ the set of vertices that can be reached by crossing a single edge from any of the vertices in $S$, there can't be any vertex in both $S1$ and $S$.
Then we call $S^2$ the set of vertices that can be reached by crossing a single edge from any of the vertices in $S^1$.
The set $S$ is a solution to this problem only if every vertex in $G$ is part of at least one of the sets above.
Couldn't think of anything better than an $O(2^n)$ solution, which leads to TLE. I'm given a time limit of 3 seconds, with $N < 1000$ and $M < N(N-1)/2$.

Something I realized is that I have to consider each different connected part on it's own and some vertices simply must be part of $S$ (if there are no edges starting from another vertex that reach them), but this assumptions didn't help much.

I apologize for my english and my poor computer science knowledge, I'm sure some parts should be reformulated but I couldn't find the right words to do that.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Welcome to CS.SE! What kinds of algorithms have you already explored/tried? Can you spot any relationship to any well-known graph theory problem(s)? $\endgroup$
    – D.W. ♦
    Sep 7, 2016 at 6:19
  • $\begingroup$ Actually couldn't find any. I'm sure there is still a lot of algorithms I've never heard about, but I also think that I've already learned about the most common ones. I think that I have to use a recursive approach, but couldn't think about any trick to reduce my algorithm's complexity (something like memoization...) $\endgroup$
    – filippos
    Sep 7, 2016 at 8:45
  • $\begingroup$ I tried to explain a few things I noticed while trying to solve the problem. Btw, main goal is not to solve this problem so that I get some points on the evaluation system, but to learn how and why I can solve problems like this $\endgroup$
    – filippos
    Sep 7, 2016 at 9:07

1 Answer 1

Reset to default
3
$\begingroup$

This problem is solvable if you have studied computer science, know standard graph problems, can spot a relationship to one of them, and then diligently study what is known about algorithms for that sort of problem.

If this immediately makes you think that it sounds related to some standard, well-known graph algorithm problem (call it Problem X), then go read about what is known about algorithms for Problem X and variants of Problem X. You'll soon find an existing algorithm that can be adapted for this.

If you can't spot any relationship to any graph problem you already know, then you should spend more quality time studying an algorithms textbook. Pick a good algorithms textbook and read it through cover to cover.

Alternatively: What algorithm design paradigms do you know? For each paradigm you know of, try to find an algorithm of that type. You should be able to find one for this.

I'm not going to say more than this. It's your exercise, so you should have the joy of finding the answer on your own; I don't want to take away from that. Also, practicing problem solving on your own is the best way to strengthen your problem-solving skills. If you just read someone else's solution, you won't learn nearly as much.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ @filippos: The Algorithm Design Manual is a great algorithms textbook. The second part of the book is full of classical algorithmic problems and descriptions of different ways to attack them. It will help you a lot. $\endgroup$
    – Mario Cervera
    Sep 7, 2016 at 7:13
  • $\begingroup$ Thanks for the answer. I understand what you say and I actually do that 99% of the time. Where I can't spot a solution, I usually get at least some ideas on what kind of algorithm I need and by getting some infos on it, I can then implement it and remember it when I'll come into similar problems later on. For example, this made me also think about a modified version of minimum spanning tree (or aborescence) or eventually to something like vertex/edge cover, but none of them looked like it could help. Also, trying to explain things with more details is quite of a challenge due to my english. $\endgroup$
    – filippos
    Sep 7, 2016 at 8:56
  • $\begingroup$ @MarioCervera Thanks for the suggestion, I'll surely give it a look $\endgroup$
    – filippos
    Sep 7, 2016 at 8:57
  • 1
    $\begingroup$ The question works better if you include one approach you have tried and got almost to work. If language is the limiting factor, that's too bad, but I'm afraid we won't be able to do much for you in that case. :/ $\endgroup$
    – Raphael ♦
    Sep 7, 2016 at 9:46
  • $\begingroup$ The algorithm essentially use recursion to try any possible combination of vertices for the set $S$, until it finds one that satisfies the conditions above, with a few simple improvements such as the one described above (some nodes are always going to be part of $S$ and I don't test non "legit" $S$ sets.) $\endgroup$
    – filippos
    Sep 7, 2016 at 11:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.