The easy problem in this round featured a well-known, but still beautiful, trick. You were given N points on a plane, and needed to count how many triangles with vertices in those points contain point (0, 0) inside them. This is of course very easy to do in O(N3), but this problem required a O(N2) solution. Many contestants went a step further and solved it in O(NlogN) - can you see that improvement?
One of those problems, problem I, went like this: you were given three polynomials f(x), g(x) and h(x), defined over Z/2Z (remainders modulo 2), each polynomial's power was at most 4000, and needed to compute another polynomial: f(g(x)) mod h(x). Polynomials over Z/2Z are just sequences of bits, and thus it's not hard to see how to use bitwise operations to perform this task in O(N3/logN). However one had to find one more speedup and solve the problem in O(N3/log2N) - and I think this is a very instructive problem to teach those speedups, so I encourage you to look for that solution.
Finally, let's go back to NEERC's problem E from the last week's summary. To remind, it was centered around the Rock-paper-scissors game. You were given a description of a finite-state machine where each state has one move associated with it (rock, paper or scissors), and three transitions corresponding to three possible moves of the opponent. The initial state of that machine was unknown. You had to create another finite-state machine in the same format that would beat the first machine at least 99% times in the long run, irrespective of the first machine's initial state.
Suppose we know the initial state of the first machine. Then beating it 100% of the time is very easy: we create a machine with the same number of states as the first machine, each state has the winning move for the corresponding state of the first machine (rock for scissors etc), and we actually care about just one transition out of three for each state: the one that happens when we win - we should transition to the state corresponding to the state the first machine transitions when it loses.
But we don't know the initial state. Let's assume the initial state is state 1, and build the above always-winning machine. What will happen if the initial state was in fact state 2? Well, since we know the first machine, we can emulate the process. One of the two things can happen: either we still win 100% of the time (this can happen, for example, if states 1 and 2 of the first machine are isomorphic), or we lose at some point. When we lose, our machine reaches a transition that we haven't yet defined. What we can do now is to add another N states to our machine with the same transitions between them that lead to always winning if we're in the right state, and direct the "losing" transition we just encountered to the appropriate state of those N, so that we would lose just once if the initial state was state 2.
We can now do the same with state 3, with a small difference: when we lose, it might happen that we lose for the first time in the same way as we did with state 2. In this case the "losing" transition is already defined, and we can't override it for state 3. In this case we should continue playing until we lose again (or make sure we never lose anymore, in which case we're fine), and this time we would be using the second set of N states and thus the first losing transition will be undefined and we'll be able to add another N states to take caret of initial state 3 of the first machine.
Doing the same for all states of the first machine, we obtain a finite state machine that has at most O(N2) states and loses at most N-1 times for any initial state of the first machine, where N is the number of states of the first machine.
There are still several questions that I don't know the answer for. Is it possible to build a machine with less than O(N2) states? If not, then what's an example first machine that requires so many states?
Finally, let me describe a slightly different solution to the contest problem that was used by many teams at the NEERC. Since it's easy to construct the finite state machine that always wins if we know the initial state, let's simply do the following: whenever we lose, let's just jump to a random state. Then sooner or later we'll jump to the appropriate state by luck and will keep winning ever since. Of course, the finite state machines don't allow random jumps. If we pick a random but specific jump for each losing transition, this will not be good enough, since those jumps might form a loop quite easily. To combat that, let's make several copies of the winning machine, for example N copies to have the same O(N2) states as the previous solution did, and assign different random jumps for losing transitions out of each copy. This way the chance of accidentally forming a loop from losing transitions is much lower, and we'll most likely randomly reach the correct state at some point.
This raises another question which I don't know the answer for: is it possible to actually estimate how likely is this solution to pass?
Thanks for reading, and see you next week!
0 komentar:
Post a Comment