So, again I didn’t need to compete, which was good because my weekend was already very very busy… 2 easy questions this week, with 750th place scoring almost 628 points. This time about 230 people got all 3 problems out in time.
Q1) Remove duplicate letters from a string, leaving the first instance.
A1) Even with the length limit of up to 1000 letters only the really silly O(N^3) solution would run too slow. Simple boolean array for seen and add characters to a list if they haven’t been seen yet then convert character list to string for return. O(N) – very simple.
Q2) Count the number of multiples of 3 (but not 15) and 5 (but not 15) and 15 in a large range.
A2) There is always 1 multiple of 15 and 4 of 3 but not 15 and 2 of 5 but not 15 in the range n=15k to n=15k+14. Thus take the modulus of the start and end in order to move them up and down to a 15k and 15m-1 value respectively, then hand code the start/end sections and add the results to m-k, 4(m-k) and 2(m-k).
Q3) Given a random walk of length n, what is the expectation value for the number of distinct locations it steps on, including the starting location.
A3) So with n up to 500, there are 2^500 different random walks possible, so brute force isn’t going to work. The best of my initial guesses was to do this as a recursion on the average width after k more steps with current location x and a to b already painted, averaging on either the walk left or right. This gives O(N^4) which is too slow and way too much memory, but the actual location x doesn’t matter, instead a and b can be normalized as distance to left edge and distance to right edge. This gives O(N^3), which is feasible for run time, but the memoization table would exceed memory limits. Even using some symmetry like if distance to left is greater than right we can flip them without loss of generality, I am pretty sure memory usage cannot be made to fit.
But this does give me another idea. If we could get rid of one of left and right, O(N^2) space would be easy to fit. This leads to the idea that memoize over remaining steps and current width where the current location is at one edge. In this scenario the recursion would have 2 possibilities. 50% chance of growing width by one and reducing remaining step count by 1 and some other chance of not changing the width, but reducing the step count by k. This requires the computation of the number of ways to choose a random walk which stays strictly in a given width starting from the edge of that use up all remaining steps, or lesser steps which end up at one of the edges of the width. Using precomputed combinatorics tables, I think this can be calculated in O(N) time, giving the result needed, but the details are more complicated than I think I could have worked out in competition.
Turns out that I really got lost on this one, because there is a much simpler solution if I had of stuck on back where I started. The simple O(N^3) space and time solution can be made to work by using a dynamic programming approach instead of recursion with memoization. In this case you can use two O(N^2) size arrays and switch between them to calculate each number of steps remaining, since the recursion always decrements steps remaining by exactly one. The final generated table contains the answer needed.