Now this is more like it… 44th! (Sure the time of this round was pretty bad for all of europe, but still…)<\/p>\n
I finished the first 2 problems in about an hour, leaving 90 minutes for the 3rd problem.\u00a0 However, I could not see how to formulate the DP (or greedy) to pass the large input after a good long while thinking, so I decided to just do the brute-force possible small input.\u00a0 Even the small input had its corner cases, but my Fraction class came to my rescue once again and after realising a stupid mistake on my first submission, I got a correct on my second attempt.<\/p>\n
Luckily I didn’t make any mistakes in the large input for the first two problems, as failing the second of the two would have dropped my score below the 1000th place cut-off, even with my submission of the 3rd problem small input. (Points were 10,10 15,18 17,30 and the pass cut-off was 53 points in a time of 2h 15 or better.)<\/p>\n
Q1) Given that you are typing a k character string, and you have typed m characters, and each of those characters has an individual probability of being correct (which is provided) but every character you type from now on will be correct, what is the expected number of keystrokes to get your password correct if you choose the best strategy.\u00a0 You can press delete 0 or more times to clear some of the existing characters and then fill in the rest and have to press the enter key each time you submit. Alternatively you can press enter immediately and start again.<\/strong><\/p>\n A1) So the enter immediately scenario is trivial, 2 + k.\u00a0 Its what we need to beat.\u00a0 This leaves k+1 scenarios, with probabilities.\u00a0 We can walk through these easily.<\/p>\n First scenario is delete everything and type it out.\u00a0 Probability of success is 1.\u00a0 Cost is m+k+1 on success.\u00a0 Second scenario is delete all but 1, probability of success is the probability of success for the first letter.\u00a0 Cost is m+k+1-(2) on success and m+k+1-(2)+k+1 on failure.\u00a0 Next scenario is the same, but the number in brackets is 4 (2 more than before) and probability of success is multiple of the first 2 probabilities.\u00a0 Just loop through them all and return the best.<\/p>\n Q2) Given a list of tasks which you get either 2 or 1 points depending on how good your best effort is, and a minimum number of points before you are capable of performing a 1 or 2 point effort (where this minimum is specified individually for every task and point outcome), determine the minimum number of task attempts required to get a 2 point effort on every task.<\/strong><\/p>\n A2) It took me a little bit of thinking before I worked out exactly how, but this seemed like a problem with a greedy solution.\u00a0 And my solution passed, so that is promising.<\/p>\n The approach is to sort the tasks in order of least to greatest points required to get a 2 point result.\u00a0 Then you take turns performing all tasks you are capable of getting 2 points on, then 1 task that you can get 1 point on.\u00a0 The first part is obvious, the list is sorted we can just work our way up it.\u00a0 But how to choose that 1 task to potentially unlock some more 2 points?\u00a0 The greedy approach is to say that you want to choose the task which is hardest to get 2 points on, its the one you are going to try last, so we maximise the opportunity to get 2 points in a single go.\u00a0 So, just walk the sorted list from the other end, choosing the first task which you haven’t already scored 1 point or more, and are capable of scoring 1 point on.\u00a0 You don’t have to worry about checking whether you can score 2 points, because you already greedily took all of those before you started your search for a potential 1 point task.<\/p>\n Finally you need to terminate this loop if you stop making any progress or finally get 2 points on all tasks.\u00a0 If the former, the problem isn’t possible, and you return as such.<\/p>\n Q3) Given a 2 lane road with cars initially in 1 lane or the other, and having initial speed and initial rear-bumper position relative to some start line, determine the maximum time before a car has to change speed to avoid a collision, presuming instantaneous car lane switches and a car length of 5 metres.\u00a0 Cars can touch bumper-to-bumper without problem, so long as the cars have same speed or the faster car is in front.<\/strong><\/p>\n A3) So the speeds and positions and car length are all integers, but the answer is not.\u00a0 Using double risks incorrectly deciding that a car cannot switch lanes, but some epsilon usage is probably feasible to get it right.\u00a0 However since I had my Fraction class, I used it to ensure I didn’t have to worry about getting the epislons correct.<\/p>\n The small input size was a maximum of 6 cars, the large was a maximum of 50.\u00a0 In either case I expect the first step is to determine the points in time which are of interest.\u00a0 Sorting the cars by speed, determine the point in time where the front of a faster car meets the back of a slower car.\u00a0 For 6 cars, this is at most 18 points.\u00a0 And at each of these 18 points, there is only 2 options of interest, showing a very plausible brute force search space.<\/p>\n So brute force approach, you walk through the points of interest in time order, at each one there are 2 scenarios.\u00a0 If the two cars are in the same lane, one of them has to swap.\u00a0 If the 2 cars are in different lanes, either they can both swap, or they can stay where they are.\u00a0 This both swap case is important because future seemingly unavoidable collisions might be avoided by trying it.\u00a0 Recursively search swapping car lanes and moving on to next interesting point in time, and undoing the swaps when the recursion returns, is not too complicated at all.\u00a0 The important bit being ensuring that you don’t swap a car when it can’t be swapped.\u00a0 This is easy enough, you just consider each car, move it to the point in time under consideration check if it is in the target lane and would overlap the target car position.\u00a0 This is where I think the greatest risk from using double and epsilons would be, but fractions handle it easily.<\/p>\n The above brute force approach however has a problem.\u00a0 If two events happen simultaneously, what do you do?\u00a0 Indeed one of the sample inputs fails if you don’t handle this.\u00a0 Thinking about how it can fail you come to the conclusion that it is where there are 3 cars which are in bumper alignment at once.\u00a0 In this case the recursion will decide to move the one moveable car, but then further down the recursion, it moves it back, inadvertently returning to where you were, but not reconsidering the scenario.\u00a0 One solution is to change the recursion to handle this, and you probably could, but I found it simpler to instead walk every pair of points of interest up front, and determine if they were at the same time and if so whether they shared the same fast or slow car (I only handled same slow car in my first submission… oops).\u00a0 If you find a match the answer cannot be greater than that time point.\u00a0 So choose the smallest of all matches and cap any returned value from the brute force, to that.\u00a0 This is a bit simpler to implement, and returns the identical result.<\/p>\n So what about the large input?\u00a0 Well, the solution is in caching I am sure, but what is your key for the DP table or memotization lookup?\u00a0 Since we are moving cars between lanes, and there are up to 50 cars, the naive cache ends up with 1225*2^50 slots (1225 being the maximum number of points of interest) and not being very sparse.\u00a0 Just as the competition ended I realised that at any point you only need to consider the cars which are involved in future points of interest.\u00a0 Defining what that actually means, obviously includes both cars at the point, but also up to 2 more cars which might be blocking the ability to switch lanes.\u00a0 But I don’t know if this reduces the search space enough, but it should be very significant at the leaves, and even before the leaves I think the actual state usage will probably be pretty sparse and so it might be possible.<\/p>\n Or maybe a completely different approach is required, I haven’t checked anyone solutions to see.<\/p>\n Contest analysis is up – and they do indeed use a quite different approach for solving the large input. Looks like the trick is to gather the cars together into groups.\u00a0 When two cars are passing, they are locked, they cannot switch lanes.\u00a0 This locking cascades.\u00a0 If you track both events regarding 2 cars travelling at different speeds meet and pass, you can work out when to split or join these groups.\u00a0 When they aren’t in a group, they are free to change at will, so the only way you can get a collision is if the two groups join and they are both fixed, which is to say they started the simulation locked. Fixed is contagious, but when a group size returns down to one it loses its fixed state.\u00a0 So we just need to consider the N^2 events, updating the joined status and returning the time if we get an unsolvable collision. Each update can easily be performed in O(N^2) which with N=50 brings the total running time quite high, but still feasible.\u00a0 It also isn’t too hard to make it perform better than that.<\/p>\n This solution is nice, wish I had thought of it \ud83d\ude1b<\/p>\n","protected":false},"excerpt":{"rendered":" Now this is more like it… 44th! (Sure the time of this round was pretty bad for all of europe, but still…) I finished the first 2 problems in about an hour, leaving 90 minutes for the 3rd problem.\u00a0 However, I could not see how to formulate the DP (or greedy) to pass the large … Continue reading GCJ12 R1A<\/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],"tags":[],"class_list":["post-525","post","type-post","status-publish","format-standard","hentry","category-code-competitions"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/525","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=525"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/525\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=525"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=525"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=525"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}