So I didn’t have to do this round either, but it had some nice questions.<\/p>\n
Q1) Given an acyclic directed graph determine whether there are any pairs of nodes with multiple paths between them.<\/strong><\/p>\n 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.\u00a0 This is O(N^2) since you have to run DFS over and over.\u00a0 Given constraints that will be fast enough, but certainly isn’t optimal.\u00a0 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\u00a0 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.)<\/p>\n 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.\u00a0 Answer the same scenario for multiple different maximum accelerations.<\/strong><\/p>\n 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.\u00a0 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.<\/p>\n Update:<\/em> 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.\u00a0 If you try to move as quickly as possible at all times, you will in many scenarios end up slower then optimal.\u00a0 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.\u00a0 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.\u00a0 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.<\/p>\n Checked the solutions, I see brute force simulation.\u00a0 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.\u00a0 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.<\/p>\n 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.<\/p>\n 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.\u00a0 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.\u00a0 What is the maximum number of pairings you can perform?<\/strong><\/p>\n A3) At first glance this appears to be a classic dynamic programming question, but it is not quite so trivial.\u00a0 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.<\/p>\n So what can we do?\u00a0 Well I think what we want is something in between.\u00a0 Do a cached recursion based on index, but use acceleration to avoid the 10^36 running time that brings.\u00a0 So no array cache, this will need a dictionary cache.\u00a0 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.<\/p>\n So what do I mean by ‘acceleration’?\u00a0 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.\u00a0 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.\u00a0 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.\u00a0 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.\u00a0 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.<\/p>\n 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.\u00a0 You can even remove the first assumption that you always pair if available, although I think it is fine. Update:<\/em> 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.\u00a0 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.<\/p>\n 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.\u00a0 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.\u00a0 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.\u00a0 By trailing all these scenarios, you still get full coverage.\u00a0 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.<\/p>\n","protected":false},"excerpt":{"rendered":" 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 … Continue reading GCJ12 R1C<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3],"tags":[],"class_list":["post-542","post","type-post","status-publish","format-standard","hentry","category-code-competitions"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/542","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=542"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/542\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=542"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=542"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=542"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}