here is a competitive programming question:
You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For convenience, we assume the tasks are numbered from 1 to 4. Suppose that task 4 depends on both task 2 and task 3, and task 2 depends on task 1. One possible sequence in which we can complete the given tasks is [3,1,2,4] - in this sequence, no task is attempted before any of the other tasks that it depends on. The sequence [3,2,1,4] would not be allowed because task 2 depends on task 1 but task 2 is scheduled before task 1. In this example, you can check that there exactly three possible sequences compatible with the dependencies: [3,1,2,4], [1,2,3,4] and [1,3,2,4]. In each of the cases below, you have N tasks numbered 1 to N with some dependencies between the tasks. You have to calculate the number of ways you can reorder all N tasks into a sequence that does not violate any dependencies.
[Task, Dependency(s)] : [1, NA], [2,1], [3,2], [4,1], [5,4], [6, 3 and 5], [7,6], [8,7], [9,6], [10, 8 and 9].
I inferred the following:
- Any sequence will always start with 1, since it has no dependencies.
- 6 will always be in the 6th position of any sequence.
- 10 will always be at the last position.
Then, by trial and error, and listing all possibilities for the two separate parts of the sequence (1 _ _ _ _ 6 and 6 _ _ _ 10), I got 6x3 = 18 possibilities. However, for a larger set of data, these deductions would not be easy. What is the way to calculate this logically and find the number of possibilities, and how can this be integrated into a program?
(I have tried to represent the question as clearly as possible, but you can visit this link to view the question (Q. No 4): http://www.iarcs.org.in/inoi/2013/zio2013/zio2013-qpaper.pdf)
I am a high school student preparing for a programming competition, and I haven't taken many courses on algorithm design, so this might be a trivial question - please excuse me!