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. 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. 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.
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.)
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. 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.
A1) So the enter immediately scenario is trivial, 2 + k. Its what we need to beat. This leaves k+1 scenarios, with probabilities. We can walk through these easily.
First scenario is delete everything and type it out. Probability of success is 1. Cost is m+k+1 on success. Second scenario is delete all but 1, probability of success is the probability of success for the first letter. Cost is m+k+1-(2) on success and m+k+1-(2)+k+1 on failure. 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. Just loop through them all and return the best.
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.
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. And my solution passed, so that is promising.
The approach is to sort the tasks in order of least to greatest points required to get a 2 point result. 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. The first part is obvious, the list is sorted we can just work our way up it. But how to choose that 1 task to potentially unlock some more 2 points? 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. 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. 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.
Finally you need to terminate this loop if you stop making any progress or finally get 2 points on all tasks. If the former, the problem isn’t possible, and you return as such.
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. Cars can touch bumper-to-bumper without problem, so long as the cars have same speed or the faster car is in front.
A3) So the speeds and positions and car length are all integers, but the answer is not. Using double risks incorrectly deciding that a car cannot switch lanes, but some epsilon usage is probably feasible to get it right. However since I had my Fraction class, I used it to ensure I didn’t have to worry about getting the epislons correct.
The small input size was a maximum of 6 cars, the large was a maximum of 50. In either case I expect the first step is to determine the points in time which are of interest. Sorting the cars by speed, determine the point in time where the front of a faster car meets the back of a slower car. For 6 cars, this is at most 18 points. And at each of these 18 points, there is only 2 options of interest, showing a very plausible brute force search space.
So brute force approach, you walk through the points of interest in time order, at each one there are 2 scenarios. If the two cars are in the same lane, one of them has to swap. If the 2 cars are in different lanes, either they can both swap, or they can stay where they are. This both swap case is important because future seemingly unavoidable collisions might be avoided by trying it. 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. The important bit being ensuring that you don’t swap a car when it can’t be swapped. 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. This is where I think the greatest risk from using double and epsilons would be, but fractions handle it easily.
The above brute force approach however has a problem. If two events happen simultaneously, what do you do? Indeed one of the sample inputs fails if you don’t handle this. 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. 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. 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). If you find a match the answer cannot be greater than that time point. So choose the smallest of all matches and cap any returned value from the brute force, to that. This is a bit simpler to implement, and returns the identical result.
So what about the large input? Well, the solution is in caching I am sure, but what is your key for the DP table or memotization lookup? 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. 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. 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. 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.
Or maybe a completely different approach is required, I haven’t checked anyone solutions to see.
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. When two cars are passing, they are locked, they cannot switch lanes. This locking cascades. 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. 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. 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. It also isn’t too hard to make it perform better than that.
This solution is nice, wish I had thought of it 😛