Baltic Olympiad in Informatics 2024 (BOI 2024) Jobs

Problem Statement 

Maximize the sum of profits for a subset of jobs S:

max _{S⊆{1,...,n}} ∑_{i ∈ S} x_i

such that if job i is picked, then job p(i) is also picked:

i ∈ S → p(i) ∈ S

and there exists an order σ for the jobs in S in which no debt is incurred for all prefixes of the order:

∃ σ ( s + ∑^k_j=1 x_σ(j) ≥ 0,   k = 1, ..., |S| )

Without the second constraint, the answer is simply just y(0), where y(i) = x(i) + max(0, y(first child job of job i)) + max(0, y(second child job of job i)) + … + max(0, y(last child job of job i)). That can easily be computed bottom-up since p(i) < i. This case is equivalent to the case of having enough initial euros to foot any possible intermediate debt: s = 10^18. Note, that x(0) = s and p(0) = 0: job 0 is a dummy job whose profit is the initial balance.

The final job picks will form a single connected component rooted at job 0 because of the first constraint: if job i is picked, then job p(i) is picked. So, picking a job is akin to merging that job with its parent. This is easy if both x(i), x(p(i)) > 0, but not  if x(i) > 0 and x(p(i)) < 0. So, you have to remember the minimum "cost to take" the new merged job that has profit x(i) + x(p(i)). You'd also need to remember the connected components across merges. Both can be done with auxiliary memory, e.g. cost_to_take(i) and a union-find data structure (U(i), find, merge).

 

How do you go about merging jobs to construct the solution then? Do you construct in a top-down manner by growing the solution at its' edges? I found that direction to be a "red herring", and all my attempts for such a job-merging strategy broke down for this example:

6 0

4 0

-3 

-1 2

-1 2

3 3

3 4

 

If x(i) > 0 and job p(i) is picked, then job i will certainly be picked. Further, if x(i) > 0 and cost_to_take(i)≤x(p(i)), then job i will certainly be picked if job p(i) is picked. There's more of these, but notice that these are true all across the job tree. It turns out that performing such job merges all across the tree greedily gives the answer.

 

The greedy job-merging solution is to merge the job that is least expensive to take and has positive profit with its parent job, i.e. out of all the jobs with x(i) > 0, take the one with the smallest cost_to_take(i) and merge it to its parent. I won't go into the actual casework for job-merging as it can be seen in the solution. Here's an additional description of the greedy algorithm. Also, there's a small catch for merging with the zeroth job.

Here's the code for my solution.

Additional observation and questions:

There's a greedy solution to this problem, but I did not reach it from this starting point (the optimization program). Is there some structure in this optimization program that I am missing? I suspect that there is and that exploiting it makes the greedy solution very apparent. But, I have not spotted it. I am wondering about this because there's lots of other optimization problems with greedy solutions, e.g. huffman coding (minimize expected codeword length), basis pursuit (maximize sparsity of signal decomposition), ... 

 

Possible bottom-up dynamic programming solution:

Let z(i, k) = maximum profit attainable if you take job i and have k euros initially. This is enough for a bottom-up dynamic programming solution (convince yourself of this). I could not put together an implementation for it though; someone else supposedly did. One interesting thing to note is that if the job subtree rooted at job i is replaced with another job tree that has the exact same z(i,k) profile, then the problem is unchanged. So, z(i,k) carries all information needed about a job tree for this problem.