So I am a bit late with this write up, I completely forgot about it…
Cutoff for the top 1000 which advance to round 2, was problem A small/large and problem B small with 45minutes spare.
Q1) Determine the number of subsequences which contain n (or more) consecutive consonants in a given string.
A1) Small input here is trivial, with a small maximum size you can use the brute force O(N^3) approach of considering each starting point, each end point, and checking each scenario for maximum consecutive consonants. Large input is size 10^6, so we need to do better than O(N^3/2) in order to run in time.
In practice it is actually not too hard to implement a solution in O(N) runtime – although given the answer can be proportional to O(N^2) we still need to remember to use 64bit integers. The solution is to use a walking range of length n, you keep track of how many consonants in a row at the end of the range, first by just counting them, then as it walks forwards, adding 1 if the new location is a consonant, and subtracting 1 if the count was previously equal to n. Each time the current number of consecutive consonants is n, add (length-n-current_starting_index+1)*(current_starting_index-last_successful_starting_index) where you initially set last_successful_starting_index to -1 and update it to equal the current_starting_index each time this calculating is performed and the total incremented. The use of last_successful_starting_index here avoids double counting when there are multiple cases where the number of consecutive consonants is n.
Q2) Given you can only move along 2D grid in horizontal/vertical direction and each movement has a length of 1,2,3,4… determine a list of NESW instructions to get to any specific point from the origin. Point is guaranteed to be reachable, and you should return the minimum length path.
A3) Small input was an interesting variation, you didn’t have to print the shortest path, it just had to be less than 500 moves, which makes the problem trivial as any consecutive pair of moves can be made opposing to have a delta of 1 in whatever direction you want, allowing you to step your way from 0,0 to x,0 to x,y, and since x,y are both less than 100, you will get there in less than 400 moves.
Large input however is not so forgiving, the result has to be the shortest path. I had a few thoughts regarding a greedy approach where you do something like NENENENENNNN to get as close as possible (assuming the target is in the NE quadrant) and then use repeated approaches of ssssswswswswswsnenenenennnnnnnn type to converge even closer. But I don’t see any way to guarantee that that is ideal. My second thoughts was that maybe we can ignore the whole 2 dimensional nature of the problem for a bit, if instead of trying to get from 0,0 to x,y we tried to get from 0 to abs(x)+abs(y) we could end up with a sequence of EWWEEEWEW which appropriate use of replacement with NS can get us to abs(x),abs(y) instead. Which can then be trivially flipped to get to the actual x,y.
This 1D version of the problem seems like it might be simpler. Reading a solution it actually is definitely simpler. Find how many steps it takes to go past the target. Now we go backwards, starting at the destination, subtracting each value off in reverse, if we go negative, we add the next one back on instead. Ultimately you can see that it must converge to 0. Now how do we convert this sequence into one that works with 2D? Using the same number of steps, we subtract off the largest absolute value out of x and y at each step. This doesn’t converge to 0 quite so obviously, but apparently it does all the same.
Q3) Given a bunch of tribes which have a ‘length’ and move along a line and occasionally attack towards the other side of the line, and succeed if any part of the wall isn’t at least height s (which is potentially different for each team, and changes as time progresses), determine how many time they succeed if at the end of each day the wall is raised to the minimum height that would have stopped any attack made that day (if it isn’t already higher).
A3) The small data set is a trivial simulation – you only need an array which covers from -200 to 200, and to order the maximum 100 events correctly and handle them happening simultaneously correctly.
The large input is a bit more tricky. 1000 tribes, each with up to 1000 attacks gives up to 1 million events, so if we are still doing pure simulation, we need do better than simulating each unit of the length of the tribe, since that is up to 10^6 and it moves up to 10^5 each move, giving a 10^8 space range and a 10^12 operation count. I think using an interval tree will do the job, especially since the ranges are disjoint. We need to handle splitting and merging, the former for correctness, the merging to avoid catastrophic performance. I think with merging, each operating may match at worst 1000 height ranges – giving a 10^9 operation count, which is huge, but with only 20 test cases, maybe plausible.
Looking at a solution, I think I needed to make the interval tree a bit more fancy otherwise it wouldn’t be fast enough, but the alternative is easier to implement than a full interval tree. They don’t use explicit merging or an actual tree implementation, instead they create a list where the first element represents the entire set of distinct start/end locations for attacks, the second the first half of those locations, the third the second half, the 4th the first quater, a bit like a common binary heap implementation. For each node they have 2 values, ‘whole’ and ‘min’. ‘whole’ is used to shortcut when an attack area covers a large section – so if an entire node is covered, we don’t have to update all of its children, we just update the ‘whole’ entry, and from then on we use the higher of whole and min of the two children when looking at the tree to find the minimum height in a range, since min may not have been updated because of whole. This ‘whole’ strategy obviates the need for merging, because it ensures n log n regardless (where n is the number of events) which is trivially fast enough.