So TCO11 kind of crept up on me, wasn’t paying much attention compared to Google code jam. But here it is qualification rounds 1 2 3 intermixing with the schedule for GCJ Round 1.
I was thinking of entering this round, probably would have been tricky to get through though, QR1 is not usually agreeable to my skill balance. I signed up for it, but by the time it hit midnight here I decided that I was too tired to stay up another 2 hours until the competition started. QR2 and 3 are much better times for me, although QR3 is during a work day so, hopefully I get through on QR2.
Almost 1600 contestants competed in QR1 – cut off for 600th place to advance to round 1 appears to be 235 points. So a ‘fast’ question 1, or question 1 + challenges, or question 2 was the target. Only 1 Australian through this round – but given the time zone it is hardly surprising…
Q1) There is a group of up to 50 people and each knows exactly how many of them are compulsive liars. Each makes a claim ‘there are at least n liars’, for a compulsive liar this means there are ‘less than n liars’. Determine the minimum number of liars, or return -1 if there is no possible correct answer.
A1) So this isn’t a difficult question, although there might be 2^50 possible scenarios for consideration they can easily be excluded in bulk, and exact scenario is not required. We just need to walk through each possible liar count and determine whether it is satisfiable.
So what is the requirement for satisfiability? For a trial n, there must be n claims greater than n, and the rest must be less than or equal to n. This corresponds to the n liars and the N-n truth tellers. Trivial enough really… probably trivial enough that I would have been too slow.
Some corner cutting options which are totally pointless and just serve to make your answer more complicated include counting the 0 and 1 entries – as those cannot be liars, and counting the N and greater entries – as those must be liars, then performing the walk in between. If the range had of been larger, sorting entries would allow for an O(n log n) implementation rather than O(n^2) – but it was just pointless in this small input size scenario.
Q2) Given a set of up to 50 integer music track lengths, and random selection from them (where repetition is possible) determine the probabilities that a given time (T) will be playing each track.
A2) Looks like an interesting question on the surface… seems like it calls for dynamic programming, but with T being up to 80000, need to be careful not to invoke O(T^2) on the DP array population.
At T=0, all probabilities are equal and it stays that way up until minimum track length. At that point probability of that track drops and the others go up. So it looks like maybe the probabilities can be linked to when tracks last ended.
At this point in my investigations into the solution I went down a long path of counting the number of ways to be ending a given song at time T. This was a problem in 2 ways. 1) It produced Huge numbers which were just too large to handle, and 2) it was useless because it didn’t account for the probability of the starting point of each song. Counting is not a good option, probabilities are better. I doubt I would have realized this during the competition soon enough, so highly likely I would have failed to get through.
So the correct approach is to ask “what is the probability that a song can start playing at time t?” This is even easier than the counting question. P(0) = 1. P(t) = Sum(P(t-ti)/N). The probability is the sum of the probability at the previous potential start time for each song divided by the number of song options for playing at that time. From there the answer is just the sum for each track over each possible start time that would have it still playing at the finish time. (Remembering to divide by the number of tracks that could have started playing at that time.)
Q3) Given a pattern of ‘B’, ‘W’ and ‘?’, where there is always exactly 1 question mark and 0 or more of the other characters, determine the shortest and lexicographically minimal replacement of ‘?’ which makes the sequence have a value of N, using the following rules. Sequence of length 1 has value 1. A letter alternation increases value by 1, a letter repetition decreases by 1. The sequence as evaluated left to right must never decrease below value 1. Further conditions, input pattern is at most 50 characters, and the final value of N is at most 100.
A3) Initially looking at this question I am thinking it must be a joke…
Four scenarios. 1) Question mark is on the end. Evaluate the pattern start for viability, and then proceed from evaluation end value to target value with directness – empty, alternates, or continuous repeats. 2) Question mark is on the start. Slightly more tricky, Check for empty, or add alternating on the front until it works (if it is going to at all). 3) Question mark is in the middle. Hardest case. Similar to case 2, but target to get back to isn’t empty. 4) Question mark is on its own. Answer is alternation starting from B until target value reached.
Scenario 3 is the only tricky part. Given a start and end character, and a target end value and a given start, without ever going below 0, what is the lexicographically smallest approach that yields the correct result. I suspect this could be done using a list of maybe a dozen or so scenarios which are simply thought through for the optimal strategy, but it can also be turned into a recursion, but one which needs to be evaluated in a fashion which is greedy so as to avoid considering solutions which are known to be way too long.
So with a known start character and start value, we can look at it as a shortest path to specific value ending in specific character. Adding a character the new state is determined by the old value, the old last character, and the new last character, with the outputs being the new last character and new value. If the assumption is made that the value never needs to exceed a certain threshold in order to achieve the shortest path, this state space is limited and easily fully explored (only two possible transitions from each spot, which we only need to consider if we find a better answer for that position). A simple threshold to assume is double the maximum target, or 200 – but I suspect the true threshold is much lower.
So, not a joke after all… still I think I was more likely to solve it than question 2…