Online Round 3 March 15, 2006 Match summary Top 200 coders faced three pretty different problems this time. The easy was a classical readandcode contest, the hard required some work with probabilities, while the medium problem was a real trap for most of the coders. tomek shined as a killing challenger this night, getting 775 points during the challenge phase. 1837 points is the highest total score ever for a TopCoder tournament round, while 3516 rating points established the new all time highest rating. rem and haha finished at second and third, both about 500 points behind tomek. TopCoder legends Johd Dethridge and Petr rounded the top five. gevak's 20 successful challenges are definitely worth mentioning, since it is the new TopCoder record (tomek also broke the previous record with 19). Congratulations and good luck in Round 4 to all 100 advancers! The ProblemsLastStoneUsed as: Division One  Level One:
This problem was a variation of the classical takelastmatch problem. Position in this game is a number of stones left. First of all, each position has a determined outcome. That is, one of the players can win the game even if his opponent plays optimally (for example, 1 is always a winning position because the first player wins the game on his first move). If the first player wins a position, we say the position is winning, otherwise its losing. We are to return the number of winning positions between m and n, inclusive. A position is winning in one of the following two cases. First, the position is winning if the number of stones left is in turns  in this case the first player wins on his first move. Second, the position is winning if the first player can make the position to be losing after his first move. Since any move leads to a smaller number of stones in the box, any position depends only on positions with a smaller number of stones. Therefore, the problem can be solved by a simple DP. For each number between 1 and n, we remember whether this position is winning. See tomek's solution for a clean implementation. FamilyTreeUsed as: Division One  Level Two:
Credit for writing this beautiful problem goes to dgoodman. The problem splits into two independent parts. The first (easy) part was to determine whether parentchild dependencies form a cycle. In this case a person becomes his own descendant. To check this, create a graph with a vertice for each person and a directed edge for each parentchild pair. Find the transitive closure (FloydWarshall is fast enough) and check for every vertice whether it is accessible from itself. It was the second part what resulted in an ocean of challenges. One needs to check whether its possible to assign genders to people such that for each person his parent won't have the same gender. To do this, lets build another graph. This graph will have a vertice for each person, and two persons will be connected by an edge if and only if they have a common child (in addition, we may already have some info about person's genders). One can correctly assign genders if and only if the graph can be painted with 2 colors such that neither edge will connect vertices of the same color. This is a classical graph coloring problem, and DFS is the easiest way to solve it. Having these two parts implemented, the other part is trivial. Process input strings one by one, adding edges to graphs and checking both graphs for consistency. As soon as you find any contradiction, return the index of the last processed string. If you were able to process all inputs without any contradiction, return 1. Check rem's solution for a short and clean implementation. TakeBusUsed as: Division One  Level Three:
No surprise, the idea for this problem came to me while I was waiting at a bus stop. The main idea behind this problem was the following. If you decide to skip a bus, then you'll need to consider only buses which go faster (spend less time) than the one you skipped. To deduce this fact during the contest, the following logics might be helpful. Lets start from the simplest case with 2 buses. Let the input contain only two buses, with trip times equal to t_{A} and t_{B} (t_{A} < t_{B}). If bus A comes not later than bus B, you get it without any doubt. If the bus B comes before the bus A, you need to compare two different estimations  expected times for you to get home if you'll take the bus or you skip it. In the first case, its just t_{B}. Let T_{1} be the estimation for the second case. T_{1} is the sum of t_{A} and E_{1}  expected time to wait until the next bus A. Imagine now you've decided to skip the bus (this happens only if T_{1} < t_{B}). Then, if later the second bus will come to the stop again, you again will need to compare two estimations  t_{B} and T_{2} = t_{A} + E_{2}. But E_{2} is strictly less than E_{1}, since we waited some time and the expected time to wait for the bus A decreased. Therefore, T_{2} is strictly less than T_{1}, which is less than t_{B}. This means you are expected to get home faster if you'll wait for bus A. After the case with 2 buses, the similar approach can be used for a general case. Again, the estimated time to get home using the current (slow) bus is the same at any moment of time, but the estimated time in case we'll wait for a faster one decreases with time. Now we are ready to code a DPsolution. The state for our solution is a pair of integers. The first integer in the state represents the time elapsed since we came to the stop, and the second stands for the fastest bus we skipped (of course, we'll need to sort buses by their trip times at the very first line of our solution). See tomek's solution for a clean DP algorithm. Another approach was to go backwards from the end, computing the estimations from the last to the first. This allows you to compute the estimation for the ith moment knowing the estimation for the (i+1)th one. See bladerunner's solution for a reference. 
