Jam 2012 Round 1A

Posted on 12th May 2015

Wrapping up with these... The final problem was rather hard, and in the end was an exercise in profiling... As ever, links to: Official Contest Analysis and my code on GitHub.

Problem A, Password Problem: You have typed A characters of your password, and the probability you typed letter i correctly is \( p_i \), for i=1,...,A. You can press backspace from 0 to A times and type again, or just give up and retype. All your typing will from now on be 100% accurate, and pressing enter counts as a keypress. For each strategy compute the expected number of keypresses needed (if you get the password wrong, you'll have to retype it) and return the lowest expected number of keypresses needed. Your password is B characters in total.

It's best to draw a table. The "give up now" option always takes B+2 keypresses.

| | 1st error at 1 | 1st error at 2 | ... | 1st error at A | All okay | | Strategy | \( p = 1-p_1 \) | \( p = p_1(1-p_2) \) | ... | \( p = p_1\cdots p_{A-1} (1-p_A) \) | \( p = \prod p_i \) | | Backspace 0 times | B-A+1+B+1 | B-A+1+B+1 | ... | B-A+1+B+1 | B-A+1 | | Backspace 1 time | B-A+1+B+1+2 | B-A+1+B+1+2 | ... | B-A+1+2 | B-A+1+2 | | ... | | Backspace A-1 times | A+B-1+B+1 | A+B-1 | ... | A+B-1 |A+B-1 | | Backspace A times | A+B+1 | A+B+1 | ... | A+B+1 |A+B+1 |

The naive way to compute this takes \(O(A)\) to compute each probability, and \(O(A^2)\) for the table, so \(O(A^3)\) overall, which is too slow. However, there is an obvious diagonal pattern to the table which leads to an obvious \( O(A) \) algorithm. It's easiest just to read the code: a.py.

Problem B, Kingdom Rush: Have games 1...N and each game requires \( a_i\) stars to play at level 1 and \( b_i \geq a_i \) stars to play at level 2.

  • Playing at level 1 gives you one extra star;
  • Playing at level 2, if you have already plays at level 1, gives you one extra star;
  • Playing at level 2 for the first time gives you two extra stars.

If you start with 0 stars, can you play all games to level 2 eventually? If so, what is the minimum number of levels you need to play?

An "almost greedy" algorithm works. If you can play a game at level 2, then there is no reason not to play it (you must do so eventually, and playing only puts you in a stronger position, as you'll have more stars). Otherwise, can you play a level 1 game? If not, the task is impossible. If so, we might have a choice (which I initially missed). Heuristically, play the game with the largest \( b_i \) as this will be "hardest" to play later. Can we make this rigourous?

  • We can play the level 2 games in order from easiest to hardest.
  • We want to avoid playing a level 1 game for which we might be able to play the level 2 version of directly, at some point in the future.
  • But then clearly the smallest \( b_i \) will be played first, so save these if possible.

Problem C, Cruise Control: On a dual carriageway, you are given a load of cars with initial positions, fixed constant speeds, and each 5 units long. They can switch lanes instantly so long as another car is not blocking them. Can the cars continue driving forever, or if not, for how long can they drive before a collision is certain?

Solution: This took me ages, but I'm glad to see the official contest analysis also says that this problem is hard. What killed me in the end was that Python is very slow, especially the Fraction class.

  • Cars can continue as they are until the point just before one car starts to overtake another: then we need to make sure they actually can overtake by changing lanes.
  • So calculate all these "action points" in time. Here I used Fraction so I could test things like "The distance between two cars is exactly 5 units" without dealing with floating point issues.
  • Then the "lane assignment problem" can be thought of as a graph colouring problem. The nodes are the cars, and cars are neighbours if they overlap, or will shortly overlap due to overtaking. Cars which are already adjacent cannot change lanes, so we can "colour" their nodes with "left" or "right" according to their current lane. Cars which have no neighbours can be either, but I'm in the UK, so force them to the "left" (later this'll stop expoential growth of cases to consider).
  • The remaining cars can be assigned to either lane, but we must do this "consistently", so that neighbouring cars are in different lanes. My algorithm to do this was to consider each "unassigned" car in turn: if all neighbours are in one lane, then we must choose the other lane; if neighbours use both lanes, then we cannot solve.
  • But there is third alternative: we can use either lane (which'll probably then force some later choices one way or the other).
  • So I keep a list of tentative solutions, and carry these forward. So a breadth-first search.
  • See the contest analysis for fancier solutions.
  • This was still too slow in Python, and after some investigation, the slow part turned out to be the use of the Fraction class. Even after factoring this out and running it once per "time event", my solution was still too slow. Digging into the code, the slow part seems to be the gcd calls each time a new Fraction object is created. Instead, I hard-coded the two tests I needed ( abs(a-b)<5 and a == b-5 ) and immediately the script runs in 2 minutes instead of over 8. See an IPython Notebook for details.

What we learn: - Even for quick coding, I like object oriented thinking, and writing a self-contained class is a good idea. - Profile! The Fraction class was so slow that this dwafted other considerations, and implementing some hacks solved this more quickly than finessing the rest of the implementation.

Categories
Recent posts