yesnomaybe's blog

Need help in task scheduling problem. Please help!
By yesnomaybe, history, 5 years ago, In English

Need help in solving the following Codechef problem :

https://discussed.codechef.com/questions/95355/task-scheduling-problem-or-graph-problem-need-help?sort=oldest

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by yesnomaybe (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by yesnomaybe (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can interpret the tasks as nodes in a graph. There is a directed edge (because of the index restriction) $$$v \rightarrow u$$$ if $$$u$$$ can be completed immediately after $$$v$$$. Since there are $$$10^3$$$ tasks, the maximum number of edges is around $$$10^6$$$, which is fine.

The problem can be understood as "choosing the minimum number of directed paths such that you visit each vertex exactly once". I have seen this problem here and the only editorial I know of is this YouTube video.

→ Reply