pabloskimg's blog

By pabloskimg, history, 5 weeks ago, In English,

There are $$$N$$$ jobs, each job $$$i$$$ has a single prerequisite job $$$P_i$$$ that must be done before, except for a global root job which has no prerequisite. Each job takes $$$T_i$$$ time to be finished, and if a job is finished at time $$$t$$$ it contributes with a penalty of $$$t * U_i$$$, where $$$U_i$$$ is the i-th job's penalty coefficient. What is the minimum penalty for finishing all jobs?

Constraints: $$$N <= 2 * 10^5$$$, everything is integer and non-negative

Notes:

  • only a single task can be performed at a time (there is no concurrent work / task parallelism)
  • the tasks DAG looks like a rooted tree

Any ideas on how to solve this? I was thinking of performing some kind of backtracking over all possible topological orderings of the DAG + some kind of extremely heavy pruning, but I haven't figured out yet a good pruning strategy to avoid exponential time. I also thought of using DP, but then I need to use bitmasks to keep track of unvisited nodes, which leads to exponential time.

 
 
 
 
  • Vote: I like it
  • -33
  • Vote: I do not like it

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

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

»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

This is a task from on going IOI 2019 official practice contest.

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

I didn't know the contest was running right now. My bad. Good question but wrong timing?