Not sure whether attendance for 1B was higher or the problems easier, but the cut-off for getting through was a much higher score… 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 work if the parent directory exists, a list of current directories, and a list of directories required, determine how many command calls are required. Constraints are up to 100 existing paths, 100 desired paths and each path at most 100 characters (and hence at most 50 deep)
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. 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. Do need to be careful you don’t try and add the empty string, but otherwise trivial.
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.
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. If the number of points which can reach it based on own velocity is less than N, we can fail immediately.
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. Then the cost is the number of non-reachables to the right of each of those N points, as summed for each point. 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. This greedy approach seems sound, I’ll just check someone’s solution… yeap it is sound. I now can see why you had to solve 2 problems to get through…
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.
A3) A math problem… and by far the hardest problem. Constraints are N is 25 or smaller, or 500 or smaller for the large. Quite a few got out the small constraint, but not so many for the large.
That being said, it isn’t really that hard of a problem. Its a dynamic program over sets of length k, which end with m and satisfy the input constraint given m. 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. With N of 500, that is 125million steps, so each step itself better be quick. So we’ll need a closer look to be sure.
Recursion shall be defined as the sum over each shorter length with m equal to the current k. 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. A direct approach results in that being O(difference in lengths) which is worst case O(N), which is nowhere near fast enough. 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). The important bit here is that the value of n choose k might be huge and the problem requires results modulo 100003. 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…). Net result is a couple of hundred million multiplications and additions and modulos. The same lookup table can be used to answer all 100 inputs, so 8minutes is plenty of time. 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. 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.