Top 1000 advanced which looks to be solving question 1 completely and question 2 small in < 1:50. For safety add in the question 3 small input. In fact you could drop question 1 large. All 3 small inputs was sufficient to advance.
Q1) Given a fraction, determine if it can be created by repeated pairwise averaging of 2^40 values which are either 0 or 1. If so, determine the best case depth of a value of 1 in that averaging. (Best case being closest to the final value.)
A1) Odd little question, but actually quite simple. Difference between small and large input was that the large could involve 64 bit numbers, and you needed to implement a GCD to reduce the fraction to minimal components, but otherwise still quite simple.
The solution comes that because repeated pairwise averaging is identical to just averaging all the values at once, the fraction must be of the form n/2^40. So if the base of the fraction is a power of 2, the fraction can be created. This is where the GCD comes in for the large input, without reducing to the minimal form, the base could be a multiple of a power of 2, and also of some other number, which can be factored out of the numerator.
For calculating the depth, it is obvious that if you consider the n/2^40 form you have n 1’s at the top level. To keep a 1 as long as possible you shift them all to one side. Thus the depth will be 40 – the floor of log 2 of n. Another way of looking at it is that if the fraction >= 1/2 a parent can be a 1, >= 1/4 a grand parent, and so on. So the depth is equal to the number of times you can double the fraction before it is greater than or equal to 1.
Q2) Given sequences of characters, determine how many ways the sequences can be ordered such that the concatenation has every case of any given letter being in a single contiguous grouping. Return result modulo 1 billion and 7.
A2) Small input there are 10! orderings to try, so it can just be brute forced. Large input there are up to 100 sequences, so something smarter is needed.
The approach I would have gone with is categorizing the inputs. If a sequence contains just the one character some number of times, we call that a ‘repeater’ (even if it is just a single character). If a sequence starts with some number instances of a letter, we say it starts with that letter. Similarly for ending. Any characters between a start and end and the sequence also gets categorized as having those characters in the middle.
From there a bunch of impossible scenarios can be detected straight off the bat. Only 1 sequence can start with any given letter, excluding repeaters. Same for ending. No 2 sequences can have the same characters in the middle, unless they are both repeaters. A single sequence can’t have the same character in the middle multiple times, unless they are contiguous. (I note now that the problem can be somewhat simplified by removing all contiguous duplications from the input sequences. They don’t change the problem and just complicate detecting invalid scenarios.)
Next the inputs need to be grouped. A starter and an ender of the same letter (and the repeaters) must be in the same group. When gathering a group, you can follow the starter to an ender, and then to a starter, and to an ender and so on, and vice-versa, to get a full group. However if you detect a cycle, this is also impossible.
The final part is to calculate the number of orderings. If there are n groups, those groups can be selected to form n! orderings. Each group has only one ordering, unless it has repeaters. Each letter in a group which has k repeaters, contributes k! orderings. All these factorials must be multiplied together, continually using the modulo 1 billion and 7 as required and use 64 bit integers to avoid overflow.
Q3) Given a NxM grid of points connected by horizontal and vertical lines, determine the minimum number of covered points required to enclose at least K locations. Enclosing is defined by either being covered or being unable to connect to the edge of the grid without going through a covered point.
A3) The small input has N*M less than or equal to 20. This actually limits a lot of the possible scenarios, but it does allow a brute force of whether each point is covered or not.
The large input has N*M <= 1000, which gives a lot greater possibilities for tricky corner cases, but does easily allow for a O(N*M*(N + M)) time algorithm. (Examples of this can be found in the solutions to download.)
So this problem has a few things to it, which makes it a bit tricky. First of all the problem is actually slightly simpler with an infinite grid. In this scenario we can ask ‘what is the largest area that can be enclosed with n stones and not have to worry about whether the ideal shape runs into the edge of the grid or not. So if n = 4k, the ideal shape is a diamond pattern. Proving this may be non-trivial in practice, but it makes a lot of sense. In such a shape any attempt to increase the area by moving a stone, forces all the other stones to move, just moving the shape. If n = 4k+2 the ideal shape has 2 options, either a diamond with 2 longer opposite sides, or take the 4k ideal and duplicate 2 of its vertical or horizontal extremes, kind of making a blunted diamond.
## # # ##
When I was first thinking about this problem I made the mistake of not considering 4k+1 and 4k+3 correctly. Looking at the case of k=1 led me to conclude that these could only cover one extra position in terms of area compared to the one stone less case. Instead the ideal scenarios look more like this:
## # # # # # # # # # # #
The general pattern that can be derived is that there are 4 diagonal lines, which either meet at a point or a blunted point. 4k is a perfect diamond shape, 4k+1 one diagonal line moves outwards, causing 2 blunts. 4k+2 moves out two diagonal lines, if they are adjacent then there are 2 blunts on opposite corners, if they are opposite it is all points, but the diamond is stretched. 4k+3 moves out 3 diagonal lines, resulting in 2 adjacent blunted points on a stretched diamond.
## # # # # #
So, how does this interact with the the borders? Well it turns out that so long as you choose adjacent case for 4k+2 (or maybe even if not?), simply truncating positions to fit inside the box is as good as you can do. I don’t have a good proof, but once the shape is too big, the edges have to be connected, so you get runs across the edge, and minimizing stones becomes cutting diagonals across the corners, which ends up being the same as squishing the ideal shape into the available space.
So the O(N*M*(N+M)) solution is to try every area less than or equal to N*M, and cut off corners incrementally until they no longer touch the edge. Since every area is tried, the ideal scenarios that don’t touch the edges of the full NxM grid are all tried because they are all touch the sides of some size rectangle. Taking turns cutting the corners off one by one goes through the 4k, 4k-1, 4k-2, 4k-3, 4(k-1) sequence, pushing the diagonal lines inwards incrementally. The best solution of all tried is returned.
A more interesting (but same running time solution) is to consider ‘can it be solved in n stones’ and then depending on the modulus the formula for the 4 boundary diagonal lines can be formulated, knowing the border will be a total of n stones, the area can then be calculated by walking over every point and checking whether it is inside the 4 diagonal lines. The solution I saw using this approach tested cutting off corners in both orientations of the NxM grid, but I suspect that with a little thought it could be reduced to only testing one of those 2 orientations.
This approach leads to an O(N+M) solution. Since the worst case answer is 2N+2M-4, you can walk upwards towards that value checking each n until one works. If you can calculate the covered area in O(1) time, this is O(N+M). This is much more complicated piece of code, but by calculating the intersection points of the 4 boundary lines with each other you can calculate a reduced area (if the shape isn’t already going to touch the edges) and then the number of empty points in the corners of this possibly reduced area can be calculated by k(k+1)/2 where k is the index (counting based on 0 from the corner) of the first filled in point along the edge, which is found by calculating the intersection of the diagonal line with the edge. The sum of these 4 corner cut-offs is subtracted from the the total area to give the number of enclosed points. There are 4 diagonal line pair intersections and then 4 diagonal line with a edge intersection calculations involved, all of which are simple formula solves (although the blunted corners result in the ‘intersection’ of the 2 lines being somewhere between points where you can place a stone, this is easily special cased) which can be done in O(1) time, for a total of O(1) time to calculate the covered area.
Special cases. If the desired area is 4 or less, no need to do any work, the number of stones required equals the area. This is also the case if the minimum of N and M is <= 2, since there is no way to surround a square in such a narrow space. Also not obvious in the discussion above is when the desired area is >= N*M-3. In this case the amount cut off a corner is 0 in some cases, which still works, it is just a bit unexpected considering all the use of diagonals in my description.