Match Editorial

Top 200 coders faced three pretty different problems this time. The easy was a classical read-and-code 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 Problems

Value	200
Submission Rate	192 / 194 (98.97%)
Success Rate	171 / 192 (89.06%)
High Score	antimatter for 199.45 points (1 mins 29 secs)
Average Score	182.33 (for 171 correct submissions)

This problem was a variation of the classical take-last-match 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.

Value	500
Submission Rate	178 / 194 (91.75%)
Success Rate	16 / 178 (8.99%)
High Score	AdrianKuegel for 350.25 points (20 mins 31 secs)
Average Score	237.77 (for 16 correct submissions)

Credit for writing this beautiful problem goes to dgoodman.

The problem splits into two independent parts. The first (easy) part was to determine whether parent-child 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 parent-child pair. Find the transitive closure (Floyd-Warshall 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.

Value	1000
Submission Rate	66 / 194 (34.02%)
Success Rate	35 / 66 (53.03%)
High Score	sjelkjd for 815.45 points (14 mins 11 secs)
Average Score	620.59 (for 35 correct submissions)

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₁ be the estimation for the second case. T₁ is the sum of t_A and E₁ - expected time to wait until the next bus A. Imagine now you've decided to skip the bus (this happens only if T₁ < 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₂ = t_A + E₂. But E₂ is strictly less than E₁, since we waited some time and the expected time to wait for the bus A decreased. Therefore, T₂ is strictly less than T₁, 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 DP-solution. 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.