Again a late night, and again a poor performance.
I was faster on the 250pt question this week, but I probably spent more time testing than I needed to. Still 217 is acceptable. Unfortunately, at the prior to systest phase, the top 600 lowest score is 300 and I failed to get the 500pt. So I sit in 750th, hoping for a huge number of failures in the 500pt problem that I struggled with. I definitely saw a few solutions which were greedy in nature in my room, and although I couldn’t find a counter example, greedy is usually high risk. I guess I’ll find out shortly.
Greedy solution passes… but still quite a few failures, enough for me to go up to 646th. Just 11 points from cut-off this time. R1C here I come?
Q1) Given up to 50 objects with lengths between 1 and 50 inclusive, determine the largest k where you can make k rows of length k either by using a single object or 2 objects separated by a gap of 1.
A1) Nice easy problem. The answer is obviously in the range 0-50, and its not too hard to verify possibility, so try each one descending until it works, or you reach 0. To verify, sort the objects, any object larger than k can be discarded, every object equal to k, count that up. Then perform an inward walk of those left checking for sum equal to k-1. If sum equals step both ends inwards and increase your count, if sum smaller move the bottom point up, if the sum is greater move the top point down. Continue until the points meet or cross. If the count is greater or equal to k, then its possible to make the k rows needed.
Q2) Given up to 50 tasks which take time between 1-3600 time units, determine the minimum time to complete the tasks subject to the following strange constraint. You have a single worker, each worker can only do one task. However a single worker can split into 2 workers in time t.
A2) The greedy solution is to sort in descending order and replace the 2 smallest entries with the largest of those two plus the split time. Repeat until there is only one task remaining and return its time. Very simple, but is it correct? The answer is yes.
The path I erroneously took was to try and determine the minimum time to perform the largest i tasks and have k workers left over. However I couldn’t get this to work because my formulation didn’t allow for the other tasks occurring after a split but still concurrently with another task. I actually realised this fairly early on and tried to formulate a reverse search more like the greedy solution, but I got confused, went round in a circle and started working on the same broken approach again. (Way too tired!)
‘Proof’ for greedy solution. You can treat the splitting of workers as creating a tree. Each leaf node of the tree does some work. There are no empty leaf nodes because any empty leaf node could be removed and its parent replaced with the other branch. In an optimal solution the 2 smallest items will be at the deepest level of the tree. As if they are not, then they can be switched with any non-deepest leaf node and the solution either improves or stays the same. Furthermore all deepest levels are reached at the same time point, so you can freely interchange any leaf at the deepest level without changing the total time for that tree. Hence, the two smallest nodes can be made to share a common parent. This pair of two smallest nodes and their parent can be replaced with a single leaf which takes as long as the longest of the two smallest nodes plus the split time. This results in an equivalent problem with an identical solution presuming we have started with an optimal solution for the original problem (I don’t have a strong proof of that, but it appears obvious – decomposing a node can only make it easier to arrange the tasks to achieve an optimum so if we are already optimum, we are also optimum for composition). We can now start all over again, but we have 1 less leaf node. Hence we can repeat until we only have 1 node, and the total cost is now obvious.
Q3) Given two rows of equal length of up to 16 people each with heights between 140 and 190, determine the minimum number of adjacent people swaps such that every member of the second row is larger than its corresponding member in the first row.
A3) Interesting question… the limits of only up to 16 people suggests an exponential search is feasible.
Looking at one of the passing answers, it looks like an exponential search on the minimum number of swaps to make the first k elements correct, looking at every possible subset of the k-1 swap locations. I’m not sure how this accounts for swap ordering… maybe I’ll work it out after some sleep.
So, post sleep revisit… The approach is to determine the minimum number of swaps required to have index i and smaller satisfy the criteria using i out of the available slots. The tricky bit in understanding the solutions is that they use a compact state space. If you use a bit field, with i bits removed, the fact that there are i bits removed indicates that those numbers were placed in the first i slots, in some order. So all bits set means any ordering, so that is where we start. For each set bit, we consider moving that value to the beginning. This will take a number of swaps equal to the distance between the start and the candidate, the rest of the values will retain the same order, and obviously we only do this if moving it results in a satisfiable condition. We now have a bunch of new bit fields to determine the minimum swaps for, with the bit corresponding to the moved index removed. So looking at each new state we can determine which index we are moving to by counting the number of gaps, and we can start again. However when it comes to distance to move to the new spot, we have to account for the fact that in moving an item to the left, the items to its left have all moved right 1. Conveniently we can determine this from the bit field. Each 0 bit corresponds to something which was moved, so if we pretend the 0 bits aren’t there and align right, that’s where the candidates are currently placed. So the count of set bits to the left of the candidate to move gives the number of swaps.
This recursion can be memotized over the bit field to ensure it runs fast enough. Terminal condition is the empty bit field which has a cost of 0. All that remains is to prove this approach correct…
Looking at the recursion from the inner most levels first. Obviously if all are in the right place, the cost to move them into the right place is 0. If all but 1 of the left most spots have been made correct, obviously the rightmost must stay still, and if it is in the correct spot, the cost is 0. If all but 2 of the left most spots are correct, either we swap or we don’t. If we swap the cost is 1, otherwise the cost is 0. The recursion will try both options so there is definitely no loss of generality yet. All but 3. In this scenario if the ideal scenario has the right most moving left 2, there is nothing to gain by swapping the other 2 first, it just increases the cost now and increases the search space, we can leave deciding whether to swap those until after swapping the right most across without any lower cost scenarios lost. Thus demonstrating that we do not lose generality. (Not a proof, but doesn’t look too hard to formalize.)
Now if you’ve been paying close attention you’ll notice I left something out completely. Everything above presumes that you only swap the people in the front row, or only in the back row. I can’t see a good way to demonstrate why this still leads to the correct solution, but intuitively, mixing front and back swaps serves to lose the ability to chain the swaps in order to place items in the correct spot. In order to perform the chaining you end up needing to do the corresponding front swap for a back swap or vice versa (or simply repeat the same swap again, either way it seems obvious that the number of swaps is increasing). In some scenarios mixing the swaps doesn’t make things worse, but it does not provide ways to make things better.