TCO 10 Qual 3

I didn't register in that round so I missed all 3 qual rounds of this year's TCO. But it doesn't hurt to work on the problems in practice room.

p250: Simple problem asking to calc the right bottom number given the top row and left column. The catch is, "return 0 if the bottom right cannot be determined". But this never happes !

p500: Some music jargons. If you read the problem, you know how to solve it.

p1000: The only interesting problem. Given 1000x1000 board, a robot will execute a program made of U, D, L, R, meaning up,down,left,right by one unit. It starts at position (xpos,ypos), and given the program, it will draw the line by executing the program. The problem asks how many pieces will the line cut the board. topleft is (0,0), bottom right is (1000,1000).

After a while I figured out it is a graph connectivity problem. But to actually implement it there are several challenges. To work out the implicit graph needs careful management of the diff in x,y of the two cells separated by that step of robot move. Finally you need to do a BFS or DFS to count number of connected components. But DFS quickly goes segmentation fault because stack overflow. Note each 1x1 cell is a vertex and there are 10^6 of them. A simple BFS with queue implementation will do it.