Match Editorial

This was the last SRM before the Open tournament finals next week, and a number of the finalists were competing in this match to practise.

The Division 1 problems were all quite approachable, with 42 coders finishing the hard problem and 11 coders finishing all three correctly. Petr had the highest score with 1514.72 total points, including 3 successful challenges. Ying finished second with 1343.01 and Jan_Kuipers third with 1316.99.

First and second place in Division 2 were newcomers fuwenjie and janos, followed by tolkienfan in third.

The Problems

Value	250
Submission Rate	259 / 311 (83.28%)
Success Rate	111 / 259 (42.86%)
High Score	dby for 241.01 points (5 mins 31 secs)
Average Score	177.68 (for 111 correct submissions)

In this problem, a function for converting income into tax was described. Coders then had to write the inverse of this function: given an amount of tax, check if it is possible to produce this amount from some income. If it is, return that income rounded to the nearest integer.

This was fairly easy since the function was a monotonic piecewise-linear function typical of taxation systems, but still many coders handled very large or small values incorrectly, or didn't properly convert to or from floating point.

Value	500
Submission Rate	27 / 311 (8.68%)
Success Rate	11 / 27 (40.74%)
High Score	fuwenjie for 460.84 points (8 mins 25 secs)
Average Score	277.47 (for 11 correct submissions)

Value	250
Submission Rate	155 / 280 (55.36%)
Success Rate	98 / 155 (63.23%)
High Score	ploh for 242.78 points (4 mins 55 secs)
Average Score	161.38 (for 98 correct submissions)

This geometry problem reduced to some standard trigonometry and linear algebra. First we need to determine two legal flight directions which give us the optimal solution. Then if the angles of the two directions are u and v, the distance we will travel in those directions are A and B, and the destination point is (X,Y), we have the two equations:

A * cos(u) + B * cos(v) = X
A * sin(u) + B * sin(v) = Y

Inverting these gives the formulae:

A = (X * sin(v) - Y * cos(v)) / (cos(u) * sin(v) - sin(u) * cos(v))
B = (Y * cos(u) - X * sin(u)) / (cos(u) * sin(v) - sin(u) * cos(v))

And then A+B is the solution.

We can find these two directions by finding the direction of the destination from the origin, and choosing the closest legal directions clockwise and anti-clockwise from that. If the destination lies in a legal direction, we just return the distance to the destination.

A simpler solution is to try every pair of directions, and choose the minimum result from the pairs of directions that lead to a valid solution.

Another approach is geometrical. At the picture origin is marked as A, destination as D and optimal path is ABD.

Since BD is parallel to AE, angles CBD and BAE are both equal to 2 * PI / n, where n is the total number of flight directions. Knowing the angle DAC, we can find that
AD = sqrt(north² + east²)
DC = AD * sin(DAC)
BD = DC / sin(CBD)
BC = DC * ctg(CBD)
and the answer is
AB + BD = AC - BC + BD

Value	1000
Submission Rate	105 / 311 (33.76%)
Success Rate	29 / 105 (27.62%)
High Score	fuwenjie for 963.45 points (5 mins 34 secs)
Average Score	644.03 (for 29 correct submissions)

In this combinatorics problem, we must find string number n in the list of all non-empty strings consisting of the first alpha letters of the alphabet, sorted first by size and then alphabetically.

If n is between 1 and alpha, then clearly we want a one-letter string consisting of the nth letter. There are alpha-squared strings of two letters, so if n is between (alpha+1) and (alpha+alpha*alpha), then we want string number (n - alpha) of the two-letter strings.

This pattern continues, so we can easily find the length L of the required string in the following way:

FindString(N,alpha):
	L = 1
	If N <= alpha^L
		find the Nth string of length L
		Return
	Else
		N = N-alpha^L
		L = L+1

FindString(N,L,alpha):
	x = ceiling (N/alpha^(L-1))
	output the xth letter of the alphabet
	If L > 1
		FindString(N-(x-1)*alpha^(L-1),L-1,alpha)

Value	500
Submission Rate	114 / 280 (40.71%)
Success Rate	42 / 114 (36.84%)
High Score	AdrianKuegel for 398.92 points (15 mins 7 secs)
Average Score	265.68 (for 42 correct submissions)

This is a shortest path/dynamic programming problem. We want to find the minimum number of moves to take the customer's car to the exit.

The important information to determine how many more moves are required is the location of the customer's car C and the location of the empty space E. The valid moves from any position are the following:

1) Move the customer's car into the space, swapping C and E, if the car and the space are adjacent.
2) Move some other car in the 100x100 grid into the space, moving E by one square.

There are approximately 10^8 possible combinations of values of C and E, which is too many to use Dijkstra's algorithm or a breadth-first search directly on this state space.

However, once we have moved the empty space to be adjacent to the car, it is subsequently not necessary in an optimal solution for the space to be more than one row or one column away from the customer's car. So by restricting the states we consider in this way we can use a breadth-first-search algorithm.

One can also compute the answer directly, noting that it is best to move the car in alternating directions where possible, and that to begin we want to move the space to either the west or south of the car. See Jan_Kuipers's code for a good example of this.

Value	1000
Submission Rate	55 / 280 (19.64%)
Success Rate	42 / 55 (76.36%)
High Score	krijgertje for 939.34 points (7 mins 18 secs)
Average Score	694.06 (for 42 correct submissions)

How hard this problem was depends on how clever you were about it!

We can write a function to determine whether it is possible to satisfy the conditions, given an upper limit on haircut time.

To do this, we iterate through the customers in order of arrival and find the minimum and maximum times at which each customer's haircut can finish. (The possible finish times are the interval between these.) If the last customer's haircut can finish at lastExit, then we can satisfy the conditions with this upper bound on haircut time.

Using this function, we can first test if it is possible to create a schedule at all by setting the maximum to 10 hours. If it is not possible, we return -1. Next we note that if it is possible to create a schedule with a given upper bound, then it is possible with a higher bound; and if it is not possible to create a schedule with a given bound, then it is not possible with a lesser bound.

So if a schedule is possible at all, then there is some value X such that all bounds above X are possible, and all bounds below X are not possible. There must be some schedule which has maximum haircut length X, so this is the required answer. The value X can be found with a binary search on all values between 5 minutes and 10 hours.

For example, consider the case with customer entry times 3:00 and 4:00, and lastExit at 6:00. If the haircuts can be at most 2 hours long, then we can give each customer a 90 minute haircut. If the upper bound were higher, we could still give each of them a 90 minute haircut. If the upper bound were only 1 hour, then we could not finish at 6:00. If the upper bound were even lower, then it would still not be possible to finish at 6:00 since we would have less choice for the length of the haircuts. So the answer X must lie between 1 hour and 2 hours, and we can continue a binary search in this interval.

A better approach is to note that there is an optimal solution in which each haircut takes the same amount of time. Let this length be X. If the Nth-last customer arrives R minutes before lastExit, then X <= R/N. Also we must have X = R/N for some customer, or we will finish before lastExit. If both these constraints are satisfied, we can construct a schedule with maximum haircut length X.

So we take the minimum value of R/N over all customers. If this is less than 5 minutes, then no schedule is possible. Otherwise, we return this value.

See Ying's and mbee's solutions for good examples of this algorithm.