I got a successful challenge this round, don’t know how long it has been since that last happened… 347th before systests, I managed to move up to 292nd afterwards. Quite a few failures in the second question, wish they had been in my room so I could have challenged them too… 😛
My TopCoder rating is now up to 1836, almost a personal best… (although still quite a ways short of where I want it…)
This is the second time I’ve scored as well as was needed for a t-shirt in previous years (292nd is a virtual 342nd after you allow for the 50 already through – although I got a higher score today than 3 of the 11 who bothered to compete in the parallel round for advancers). If I make it 3 from 3 and don’t win a t-shirt I’ll be rather disappointed – and I didn’t even sneak a completely invalid solution past the system tests this time 😛
Q1) Given the numbers 1-N which are placed in some order where you only know where some of them are, what is the minimum number of picks of spots to guarantee you reach a target value. (Target value is large.)
A1) I think this problem is relatively greedy. First up there are either 2 things you are going to do, pick the highest known value, or rotate through all the unknown values. It never helps to choose an unknown value over and over, because it could be the minimum of the unknowns. So I can see 3 strategies. 1) You simply use the highest value forever. 2) You simply rotate through the unknowns forever, presuming you get the smallest of the unknowns on your last rotation. 3) You rotate through the unknowns for as many full cycles as possible, then use the highest known value until finished, because the last cycle as partial, might have a lower worst case average than the highest known.
So try each of the 3 scenarios, and choose the best. Handling corner cases like no unknowns or all unknown.
Q2) Given items of known weight, and the following game, determine the outcome if both players play optimally. Each turn players can move a specific number of items from their pile to the opponents pile, these numbers are provided. If their pile doesn’t contain that many items, all items are moved. The first turn however is player 1 chooses which of the starting set of items (also provided) is placed into player 2’s pile. Assume that the aim of the game is to maximise the weight of your opponents pile minus the weight of yours, and in equal situations both players aim to maximise the total weight. Items have a large weight range.
A2) I managed to solve this problem, but I didn’t get my implementation written in time. This was also the problem I managed to get a successful challenge on.
First up is to realise that the game is entirely greedy and easily determined after the first player chooses the initial items. At any point in the game you will always give your heaviest items to the opponent, there can be no benefit in giving the lighter ones. So you can take a list of indexes for a virtual sorted array and simulate the game to see which indexes end up in each players pile. Now player 1 has to maximise their score, and for equals maximise the total weight, by assigning individual items to these indexes in sorted order.
So start by sorting the provided items by weight- it is now a fairly standard DP on maximising a valuation of selecting an ordered subset. However there is a small complication that some indexes cause negative value, and others positive. But it doesn’t actually change the DP structure, you just want to build a lookup table of index to whether it is positive or negative multiplier.
Small tip I got from one of the solutions in my room was to make the DP table member type a custom class indicating the piles and write a custom comparator to compare the difference, or sum if equal. This means you don’t have to reconstruct the piles from scratch after you have finished your DP like I was going to have to.
Q3) Given numbers of the form a*x+b from x=1 to x=n, concatenated in their minimal length binary representation, how many times does the sequence change from 1 to 0 or vice-versa. b and n are both huge, a, not quite so much.
A3) This was only rated at 900 points, but I have no clue how that makes any sense…
The last digit is going to have a trivial sequence, so tracking how the concatenation affects the result isn’t too crazy, but tracking the internal changes is still going to be problematic. Definitely going to be some pattern, but it isn’t going to be trivial.
Looks like the correct approach is to process the multiples in sections of powers of 2, but from there it gets complicated and I definitely need some sleep.