Not sure whether attendance for 1B was higher or the problems easier, but the cut-off for getting through was a much higher score…\u00a0 Unlike my round where solving any single problem with a decent time was sufficient, this round you needed at least 2.<\/p>\n
Q1) Given a command for making new directories, which will only work if the parent directory exists, a list of current directories, and a list of directories required, determine how many command calls are required.\u00a0 Constraints are up to 100 existing paths, 100 desired paths and each path at most 100 characters (and hence at most 50 deep)<\/p>\n
A1) This problem makes R1A Q1 almost look tricky – just maintain a dictionary of existing paths and for each new path add\/trim\/add\/trim until the add fails – and count each add.\u00a0 The constraints are so small that the cost of generating alot of garbage strings isn’t even a problem – so no need for any kind of optimisation.\u00a0 Do need to be careful you don’t try and add the empty string, but otherwise trivial.<\/p>\n
Q2) Given a set of ‘points’ at different locations, and their velocities, and the position of some goal, and a restriction that in order for one point to pass another requires a ‘cost’ of 1, what is the minimum cost to have at least N points at the goal by time T.<\/p>\n
A2) Okay, so this one is an actual problem… We can start by considering for each point, whether it can reach the goal based on its own velocity. If not we can kind of ignore those points.\u00a0 If the number of points which can reach it based on own velocity is less than N, we can fail immediately.<\/p>\n
At this point I would think that the right most N points which can reach the destination in time will be the ones we want.\u00a0 Then the cost is the number of non-reachables to the right of each of those N points, as summed for each point.\u00a0 If we were to choose a point which is more left, it would have to pass more non-reachables to get to the goal in time, increasing the cost.\u00a0 This greedy approach seems sound, I’ll just check someone’s solution… yeap it is sound.\u00a0 I now can see why you had to solve 2 problems to get through…<\/p>\n
Q3) Given a set of numbers 2 to N, determine the number of subsets which contain N and its rank (ordered inclusive position 1-based), its rank’s rank, its rank’s rank’s rank, and so on until you get to the first element in the set.<\/p>\n
A3) A math problem… and by far the hardest problem.\u00a0 Constraints are N is 25 or smaller, or 500 or smaller for the large.\u00a0 Quite a few got out the small constraint, but not so many for the large.<\/p>\n
That being said, it isn’t really that hard of a problem.\u00a0 Its a dynamic program over sets of length k, which end with m and satisfy the input constraint given m.\u00a0 Both k and m are limited to being less than or equal to N, and the recursion is going to have to consider each shorter length, so O(N^3) is in play.\u00a0 With N of 500, that is 125million steps, so each step itself better be quick.\u00a0 So we’ll need a closer look to be sure.<\/p>\n
Recursion shall be defined as the sum over each shorter length with m equal to the current k.\u00a0 However each of those sum components need to be counted by the number of possible ways to choose the difference in lengths -1 extra numbers which are greater than k and less than m.\u00a0 A direct approach results in that being O(difference in lengths) which is worst case O(N), which is nowhere near fast enough.\u00a0 However all of the possible choose calculations can be precalculated in O(N^3) (or O(N^2) if you cache factorials and inverses mod p).\u00a0 The important bit here is that the value of n choose k might be huge and the problem requires results modulo 100003.\u00a0 Using TMD.Algo this will not be a problem, as I have an efficient n choose k mod p implementation already done and 100003 is prime (see, implementing stuff useful for last years GCJ, also useful for this year…).\u00a0 Net result is a couple of hundred million multiplications\u00a0 and additions and modulos.\u00a0 The same lookup table can be used to answer all 100 inputs, so 8minutes is plenty of time.\u00a0 In fact that last realisation is one I would have been at risk of missing during the contest, or I would have said I would have gotten all 3 problems out for sure if I was in this round.\u00a0 Without reusing the table, the time constraint might be an issue, possibly depends on how fast your computer is… the look up tables will be close to fitting into cache on a good processor, but even then it might not be enough.<\/p>\n","protected":false},"excerpt":{"rendered":"
Not sure whether attendance for 1B was higher or the problems easier, but the cut-off for getting through was a much higher score…\u00a0 Unlike my round where solving any single problem with a decent time was sufficient, this round you needed at least 2. Q1) Given a command for making new directories, which will only … Continue reading GCJ10 R1B<\/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-149","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\/149","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=149"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/149\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=149"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=149"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=149"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}