Same here

I think this is going to be unrated.

Same for me, thank topcoder for a great experience. Hope the round will be unrated.

Same here. I hope this is going to be unrated.

I faced on the same issue :(

I coded solution for 1000-point problem before finish, and couldn't compile/submit it until the end of a contest. Too bad :(

I think I know how to reduce it to min-cut problem, although I didn't manage to fix all problems by the end of the contest. Anyway, here it goes:

For every node in the original graph we'll create its own chain of nodes 0...100. Let's call these nodes nn[v][i] where v is the recipe from the original graph. Node i in this chain will be responsible for answering the question "is it true that we finish this recipe preparation at time X <= i?" (I'll call this predicate p[i]). We can add edges from i to i-1 of infinite capacity to make sure that if p[i] is true, then p[i + 1] is also true. Also, we can add an edge of infinite capacity from the source S to all nodes i < prep_time[v] and also add an edge from node 100 in the chain to T of infinite capacity.

To satisfy topological sorting constraints, for each dependency (v, u) we can add edges of infinite capacity between nn[v][i] and nn[u][j] where (j - i = preptime[v]).

Now, min-cut in the described graph will give us some ordering which would satisfy the correctness constraints, although it's not going to minimize the staleness.

Let's take a look at a pair of nodes (v, u) with dependency v->u. Let fin[i] be the time where we finish preparing node i, st[i] be the start of preparation which is equal to fin[i] - preptime[i]. Then, for (v, u) we'll need to add (st[v] - fin[u])² to the total staleness. This can be expressed in the following form: (st[v] - fin[u])² = st[v]² + fin[u]² - 2·st[v]·fin[u]. Note that st[v]² and fin[u]² don't depend on the pair (v,u) so they can be easily incorporated into our graph if we add edges between nn[v][i] and nn[v][i + 1] of corresponding weights, multiplied by in-degree or out-degree.

Now, let's add edges of capacity 2 between all pairs of nodes nn[v][i] and nn[u][j] for each dependency (v, u). Let's assume we've found the min-cut and let's only look at the edges that intersect it. If node v is finished at time i, then there'll be a cut between nn[v][i] and nn[v][i + 1]. Similarly, let's assume node u is finished at time j so there's a cut between nn[u][j] and nn[u][j + 1]. Then, all edges from nn[v][i'] (i' ≤ i) to nn[u][j'] (j' ≥ j) will belong to the cut, which means we'll add smth like 2·fin[v]·(100 - fin[u]) = 200·fin[v] - 2·fin[v]·fin[u] to the overall answer which is almost what we need. We'd still need to subtract 200·fin[v] from the answer, and also we'd need to convert 2·fin[v]·fin[u] into 2·fin[v]·st[u] = 2·fin[v]·fin[u] - 2·fin[v]·preptime[u], however that can be done quite easily by adding carefully chosen edges.

Now, if we find a min-cut in this graph, it'll give us the minimum total staleness.

You can pretend all tasks are instant by subtracting time[i] from start[i+1], then binary search the answer using greedy. Which turns out to be

Div 2 500 can be solved with a binary search over the answer. You need to guess the answer value and check if all the task can be done using this time gap. If it is possible then you need to decrease your search range otherwise you need to increase your search range.

BTW, there is no need to implement binary search. The limit is low, so linear search would do. Complexity will be rangesize(10^6) * sizeofarray(50).

It means the round can't be rated because of failure with compiling solutions in the second half of it.

Great blog! Added to main post so people can find it easier.

Or just group them by (x+y)%8.