So TCO11 kind of crept up on me, wasn’t paying much attention compared to Google code jam.\u00a0 But here it is qualification rounds 1 2 3 intermixing with the schedule for GCJ Round 1.<\/p>\n
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.\u00a0 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.\u00a0 QR2 and 3 are much better times for me, although QR3 is during a work day so, hopefully I get through on QR2.<\/p>\n
Almost 1600 contestants competed in QR1 – cut off for 600th place to advance to round 1 appears to be 235 points.\u00a0 So a ‘fast’ question 1, or question 1 + challenges, or question 2 was the target.\u00a0 Only 1 Australian through this round – but given the time zone it is hardly surprising…<\/p>\n
Q1) There is a group of up to 50 people and each knows exactly how many of them are compulsive liars.\u00a0 Each makes a claim ‘there are at least n liars’, for a compulsive liar this means there are ‘less than n liars’.\u00a0 Determine the minimum number of liars, or return -1 if there is no possible correct answer.<\/strong><\/p>\n 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.\u00a0 We just need to walk through each possible liar count and determine whether it is satisfiable.<\/p>\n So what is the requirement for satisfiability?\u00a0 For a trial n, there must be n claims greater than n, and the rest must be less than or equal to n.\u00a0 This corresponds to the n liars and the N-n truth tellers.\u00a0 Trivial enough really… probably trivial enough that I would have been too slow.<\/p>\n 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.\u00a0 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.<\/p>\n Q2) Given a set of up to 50 integer music track lengths, and random selection from them (where repetition is possible)\u00a0 determine the probabilities that a given time (T) will be playing each track.<\/strong><\/p>\n 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.<\/p>\n At T=0, all probabilities are equal and it stays that way up until minimum track length.\u00a0 At that point probability of that track drops and the others go up.\u00a0 So it looks like maybe the probabilities can be linked to when tracks last ended.<\/p>\n 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.\u00a0 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.\u00a0 Counting is not a good option, probabilities are better.\u00a0 I doubt I would have realized this during the competition soon enough, so highly likely I would have failed to get through.<\/p>\n 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).\u00a0 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.\u00a0 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.)<\/p>\n 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.\u00a0 Sequence of length 1 has value 1. A letter alternation increases value by 1, a letter repetition decreases by 1.\u00a0 The sequence as evaluated left to right must never decrease below value 1.\u00a0 Further conditions, input pattern is at most 50 characters, and the final value of N is at most 100.<\/strong><\/p>\n A3) Initially looking at this question I am thinking it must be a joke…<\/p>\n Four scenarios.\u00a0 1) Question mark is on the end.\u00a0 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.\u00a0 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.\u00a0 Hardest case.\u00a0 Similar to case 2, but target to get back to isn’t empty. 4) Question mark is on its own.\u00a0 Answer is alternation starting from B until target value reached.<\/p>\n Scenario 3 is the only tricky part.\u00a0 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.\u00a0 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.<\/p>\n 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.\u00a0 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.\u00a0 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).\u00a0 A simple threshold to assume is double the maximum target, or 200 – but I suspect the true threshold is much lower.<\/p>\n So, not a joke after all…\u00a0 still I think I was more likely to solve it than question 2…<\/p>\n","protected":false},"excerpt":{"rendered":" So TCO11 kind of crept up on me, wasn’t paying much attention compared to Google code jam.\u00a0 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 … Continue reading TCO11 QR1<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[],"class_list":["post-318","post","type-post","status-publish","format-standard","hentry","category-code-competitions","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/318","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=318"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/318\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=318"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=318"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=318"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}