Screencast and challenging

For those of you who don't follow the TopCoder forums - I've been screencasting my SRM experiences, in a hopeless assumption that people might find it interesting.

Read more

SRM 419 easy problem: http://77.41.63.3/topcoder/screencast/srm419/easy.wmv

SRM 419 challenge phase: http://77.41.63.3/topcoder/screencast/srm419/challenge.wmv

Recollection of events for the first part of the challenge phase:

00:40 into the video - open the code, read it
01:53 - spot a bug: the coder doesn't distinguish "player X will win" from "only player X or nobody can win". Start thinking about the challenge case.
02:40 - how should the challenge case work? The first player should have two options; in one of them, the situation "only player 1 or nobody can win" should arise, so that the code mistakes by thinking that person 1 has a forced win and chooses that move; but in reality, there should be another move that allows some other person to win. The problem statement lets us build practically any graph for the game, so we can choose arbitrary number of stones removed for those two moves; let's say that those moves take 1 and 2 stones, and let's say the initial amount of stones is 5 (hopefully that will be enough).
02:50 - one of the cases should make other person win; let's make it so that the second player wins instantly by taking 3 stones from 3.
02:56 - and we should have two variants (either player 1 wins or nobody wins) in the second case; so that gives us two possible moves again; not to overlap with the existing positions, let's make them 2 and 3 from 4.
02:59 - one of them should lead to "nobody wins" situation, so we leave position with 2 stones with no jumps. Position with 1 stone should have the first person win, so assuming we have only 2 players, that position should have a winning move: 1.
03:15 - so is this gonna work? No, it isn't; player 1 should still be able to win after both initial moves, otherwise even without a forced win he should choose only one of them according to the problem statement. So we should modify the "3" position to allow the first player to win. But how?
03:24 - we'll need a couple more positions to achieve this; let's insert them.
03:39 - we'll need to adjust existing jumps; but...
04:08 - we can't achieve the current goal with only two players, as we should have a position when player 1 AND some other player can win; if some other player is player 2, then he will certainly win if given the choice; thus, player 2 should choose whether player 1 or player 3 can win. But, first of all, now that we have 3 players, we should alter the "player 1 or nobody wins" position. For player 1 to win, we now need two extra moves after player 2's move. We achieve that by having position 2 have one move to position 1, and position 3 having no moves; Player 2 now has two moves, 3 and 4, from position 6 - the first one leads to a draw, and the second leads to two more moves performed and player 1 winning.
04:52 - and how do we make player 2 choose whether player 1 or player 3 wins in the other case? He should choose whether there're 1 or 2 moves left; luckily, we already have such positions, so we just create appropriate moves from position 5: move 3 that leads to position 2 and player 1 winning, and move 4 that leads to position 1 and player 3 winning.
05:10 - re-verifying the case shows that everything should work; challenge phase is short and others may challenge this as well, so let's not re-verify once again and click "OK".
05:15 - enter two more numbers required and challenge!
05:17 - successful! And the expected and actual results are what I expected them to be, so the case should be OK. Cool, let's look if the others have made the same mistake.

SRM 420:

Streaming: http://77.41.63.3/topcoder/screencast/srm420/stream.html. I believe you need at least Flash 9 to view that.
Download: http://77.41.63.3/topcoder/screencast/srm420/srm420.avi or http://77.41.63.3/topcoder/screencast/srm420/srm420.mov or (when my server goes down)http://narod.ru/disk/2954156000/srm420.avi.html (this is in Russian, but the only thing you need to do is to solve the CAPTCHA just above the green button, and then press the green button; there might also be a checkbox on Firefox and IE asking to install a toolbar - uncheck it). The file is 55M.

If you have problems viewing, please tell - I'm still trying to figure out the right setup for this.