>(I'm not sure how to prove it, but it seems to pass all tests).

Isn't that risky? Especially in competitions with challenges.

The second solution uses critical path, looks like a well researched method so it's probably proven somewhere already.

Strange solution for div1 hard that passes all systests: http://ideone.com/knlGNZ

Basically, generate all paths from vertex with indegree 0 to a vertex with outdegree 0, then solve a linear program inside a binary search to find the answer.

Seems to pass all system tests in at most 14ms (!), but I didn't have much confidence in this during the contest so I missed submitting by a few minutes :p.

For div2 Med : It is possible to determine the winner of the game in O(1).Some case analysis needed . My solution : Link

In div1 med of referenced implementation I found this code:

if (k >= 4) {
    k = (k % 2) + 4;
}

How this can be proven/inferred without generating any sprague grundy values? Is mentioned hint about it?

A better approach in such situations is to manually set the no. of iterations ( >= 300 is fine)

Suppose [L; R] is the search range and P is the number of digits after floating point you should calculate.
log2(R - L + 1)  +  log2(10^P)  + C will be enough for C <= 5.
In today's 250p you could just set the number of iterations to 1024 and fit into the TL comfortably.

I also used epsilon and passed. You just have to make sure that it's not too small; since the required precision is 10^- 6, I set it at 10^- 7. And the initial max. R at 10⁶.

I don't trust in the epsilon as the stop condition anymore :(

It cost my team a problem in the ACM ICPC Latin America Regional contest of this year (a ternary search with dijkstra), and now this xD

Thanks guys!

What is at least one reason not to use epsilon as stop condition, what caused a problem here? I was used to perform constant number of iterations, however recently I got 2 TLEs in 2 different problems within few days, because I set that constant a bit too high and after changing this to epsilon condition it passed, so now I think that eps condition is a safer way. However we should be aware that epsilon condition is applicable if value we are searching for is exactly what we want to output, I mean such thing will be bad:

"Print result with error not larger than 10^- 6."

double l = 0, r = 1e6;
while (r - l > 1e-7) {
  (...)
}
cout<<f(l)<<endl;

because maybe it doesn't hold that

I haven't coded it yet, so not 100% sure if it will work, but this is the best I could come up with.

We can easily figure out the path (sequence of nodes) required for each train.

Then we can figure out at what time, which nodes need to be in what state, eg(node 2, R).

If we figure out all possible changes required to all possible nodes, and sort it by time, and then make the change at the top of the sorted list, followed by all possible changes, such that the same node is not changed twice (i.e stop changing node k, if it's ith iteration is different from it's first iteration in the list, and don't change it in this action) , in the same action, deleting the changed items from the list.

Repeat till empty list, the number of times we had to iterate is the answer.

I couldn't code this during the contest (ran out of time). Will try coding this after classes today.

Look at some specific node. For each train that passes through this node you will get an information "at time t[i]+epsilon the switch needs to point in the direction dir[i]".

For example, you can obtain the information (3,left), (5,left), (12,right), (15,right), (33,left).

Then, this particular node needs to be flipped twice: once in the interval (5,12] from left to right and once in (15,33] from right back to left. This is possible if and only if there is an action during each of these intervals.

So, now you have a collection of intervals and you want to cover all of them using as few actions as possible. To do this, just notice that it never hurts to perform the actions as late as possible. For example, if your intervals are ( l[i], r[i] ], it makes no sense to perform the first action sooner than at min(r[i]). This allows us to solve it greedily: always find min(r[i]) among intervals that don't contain any actions yet.