So I didn’t have to do this round either, but it had some nice questions.
Q1) Given an acyclic directed graph determine whether there are any pairs of nodes with multiple paths between them.
A1) So the obvious approach is to depth first search starting from each node, and if any DFS ever sees the same node twice there is multiple paths. This is O(N^2) since you have to run DFS over and over. Given constraints that will be fast enough, but certainly isn’t optimal. One sub-optimal improvement is to only run the DFS from nodes that have no nodes pointing to it. I think the optimal approach is to compare the sum of edges to the number of nodes If it contains no multiple paths the number of edges will equal the number of nodes – 1. (But my graph theory is a bit rusty, but I think that criterion applies in this case.)
Q2) Given a car which has a maximum positive acceleration (spontaneous reductions in velocity are fine) and a lead car which cannot be passed, if the lead car travels at constant velocity between known points at known times, what is the earliest the first car can get to the end of the road. Answer the same scenario for multiple different maximum accelerations.
A2) This question is a ‘simple’ simulation, checking for quadratic equations crossing linear equations of motion to know when the lead car is limiting the first car. The large input is 2000 known points of time and 250 different maximum accelerations, and there are up to 100 test cases, but even so I don’t see there being a performance problem using brute force.
Update: Actually it isn’t as simple as I make out above, the most obvious approach is in fact incorrect, which is possibly why this question was the least commonly answered, and not just that the question text was presented in a way which seemed to maximise confusion. If you try to move as quickly as possible at all times, you will in many scenarios end up slower then optimal. The thing to optimise is not your forward position at each point in time, but instead your velocity at the time when the lead car increases speed. If you catch up to the lead car you are guaranteed to be doing the same speed, when if you waited at the start, you could be travelling faster. In fact the optimal strategy is to delay start for as long as needed, to maximise your use of acceleration to ensure you are always fast, but never hit the lead car.
Checked the solutions, I see brute force simulation. The simulation can be simplified to tracking the maximum difference in arrival time at a point of the lead car and the time the other car would have gotten there if the lead car was not a problem. Then just adding this to the minimum travel time for the car. But that isn’t significantly faster then the full simulation – the only question is whether you could get accuracy issues accumulating rounding error over 2000 segments doing the full simulation.
One other sneaky point is that the places and times for the lead car may include points beyond the ‘end of the road’, they need to be truncated appropriately to get it right.
Q3) There are two sequences of elements, which are very long, but only change element types at most 100 times, so there are very long runs of elements. You start by taking the first element from both sequences, and proceed by either pairing matching item and taking 1 new from each sequence, or by throwing one item away and taking the next item in that sequence. What is the maximum number of pairings you can perform?
A3) At first glance this appears to be a classic dynamic programming question, but it is not quite so trivial. The trivial DP on index in each sequence, won’t perform usefully since the sequences are up to 10^18 elements long, and a DP purely on the segments isn’t going to work since one segment from the first sequence might match against 4 segments in the right sequence in the optimal solution.
So what can we do? Well I think what we want is something in between. Do a cached recursion based on index, but use acceleration to avoid the 10^36 running time that brings. So no array cache, this will need a dictionary cache. To simplify the logic the recursion parameters will be current segment and offset into the segment, since raw offsets will require searching the list to determine the segment details, which will likely cause performance to suffer by too much.
So what do I mean by ‘acceleration’? We need some strategies that deal with a lot of elements in bulk, and do so in a consistent manner which doesn’t lose the optimal solution. First up is if the current segments match, we will pair, we will never throw away, so we can accelerate forwards on both sequences to the end of whichever of the two segments has the least remaining. If they don’t match there are 3 options, throw away every element of the left segment, or every element of the right segment, or both segments. This later scenario can be ignored as it will be found by the other two unless it results in mandatory matching of elements, in which case it wasn’t the optimal solution anyway. The reasoning here is that throwing away part of a segment now, is the same as not throwing them away and then throwing away the leftovers after doing some matching, just a different order of operations with the same outcome.
The running time of this algorithm isn’t immediately obvious, but I think it is no worse than O(N^4) where N is the number of changes in the sequences, which should be good enough. You can even remove the first assumption that you always pair if available, although I think it is fine. Update: Actually it might be O(N^6) which would be a problem, for two reasons, one it would be too slow and two it would use more ram than my machine has available. I did see a solution which passed which used a very similar approach, so I think the theoretical scenario I am thinking of may be practically impossible and the solution space is actually very sparse. Specifically if you do include the greedy match assumption, it probably makes it very difficult to break.
Another approach I found looking at solutions is to use the explicit DP on the segments, but to handle matching segments in a special manner. Rather than storing an index into the segment to handle partial segments, realise that in order to use that segment to match against multiple other segments on the other side, you have to throw away any non-matching segments in between. So whenever you have matching segments, you can try O(N^2) scenarios to skip both sides ahead gaining whatever matches of that type in the area skipped. By trailing all these scenarios, you still get full coverage. This solution is clearly O(N^4) which is likely a bit faster than my first solution, and definitely uses less memory for the cache.