So I went in topcoder 2012 R1A and wow was I slow… Easy questions, and I only implemented solutions for 2 out of 3 them with 3 minutes to spare.
724th before system tests, cut-off is top 600. After system tests 655th. A single challenge would have gotten me through, and I was staring at an incorrect java solution for the 250 for a while but someone challenged it faster. So I shall be back next week, which will almost certainly be much easier with 600 of the top people going through this week.
Q1) Given a game where points are given out 1, 1, 0.5, 0.5, 0.25, 0.25 … and list of peoples turns which may not be in the correct order, determine who could have possibly won outright (no draws). (Max 8 turns.)
A1) This question caught me badly, I immediately presumed that there was an order of play, and the turns were just shuffled to be confusing. This lead me to a simple solution which was completely wrong, which I ‘corrected’ twice before finally realising (looking at the final sample where 1 person had 3 turns and 1 person only had 1) that I had completely misread the question.
So, throw everything away, start again. Simulate the game for every permutation of the given turns and collect the distinct set of winners. C++ coders used next_permutation to great effect. I just wrote the brute force. Still even if I had have read the question correctly, I wasn’t writing code fast.
Q2) Determine the number of fractions a/b where a < b, a is co-prime with b and a*b equals one of the factorials less than or equal to N!. (Max 250 for N)
A2) Took a moment for my brain to get started here as well, I momentarily went off on a side track of counting the number of fractions less than 1/k which have a*b = m!, but realized pretty quickly that there was no way that was going to help me avoid counting the scenarios where a and b are not co-prime. A bit more thinking and I realized that I could count all co-prime fractions a/b without restriction of a < b much more easily. And since there are no factorials which are square numbers (ignoring 1, which we can) the answer is exactly half that. So how do we count these? Well break k! factorial into its prime factors and their powers, obviously if a, b are co-prime, then no prime factor is shared, so all we need to do is count how many ways we can divide the distinct prime factors into 2 groups (including cases where the groups are empty, since we can always make a or b 1).
Here I had a moment of stupidity. How many ways can you divide N items into 2 groups… well that’s the sum of n choose k for all k, 0 to n – and choose can be implemented using a pascals triangle cache for high speed. Err… Wait a second… or I could have just raised 2 to the power N… But too late, already implemented and tested, so submitted it shall be.
But again, it took me way too long.
Q3) Given a set of light switches which can control multiple lights, and each light is controlled by up to 2 switches and the list of exactly which light each switch toggles, and an initial state of lights, determine the minimum (non-negative?!?) number of switch uses required to turn all lights off. (Max 50 lights)
A3) This problem is so easy, I wish I had of had time to look at it. Since each light is controlled by at most 2 switches, switches can be in 3 states. Useless (because they aren’t used anywhere), Defined (because they are the only switch for each light they switch) and Joined (because either the two switches must be the same or opposite by the connecting light).
Collect all joined switches into clumps. For each clump, try toggle or not for a single switch, the rest of the switches become defined. If all lights turn off, determine how many toggles that matched to and choose the smallest if both toggling and not-toggling works. Add all clumps together, add in the defined and ignore the useless… and you are done.
Well, except I didn’t mention all the failure scenarios. A ‘Defined’ switch could have no solution if the lights it is defined for do not start in the same state. Also neither state for a clump may result in all lights off. Finally there could be a light which is not referenced by any switch and is not already off.
So in the final analysis it looks like if I hadn’t of misread the first question, there is a decent chance I would have saved enough time to get me the 40 points I needed to get through, and potentially even have been making good progress on the 3rd question when time ran out.