September CookOff Contest Problem Editorials

Problem Setter for the contest was David Stolp.
Problem Tester for the contest was Aleksey Tolstikov.

----------------------------------------------------------

HOTEL: Hotel Bytelandia

Several approaches exist to this problem. The simplest solution is to simply count the number of guests present at the hotel for each time from 0 to 1000, and print the maximum. A guest is present if the current time is greater than or equal to their arrival time but less than their departure time.

For a better approach, call arrivals and departures "events". Sort the 2*N events by the time at which they occur. In case of ties, place departures before arrivals. Then process the events in order, adding 1 to a count whenever an arrival occurs, and subrtacting 1 when a departure occurs, and print the maximum count.

Problem Setter's Solution
Problem Tester's Solution

----------------------------------------------------------

DIGROT: Digit Rotation

One way to perform a digit rotation is to convert the number to a string, perform a rotation on the string, then convert back to an integer. Another method is to use divisions and multiplications by 10. Although it was possible solve using a depth first search or breadth first search, the maximum value always occurs after one of the following:

Left rotations only (at most 6)
Right rotations only (at most 6)
A single left rotation followed by a single right rotation
A single right rotation followed by a single left rotation

To see why this is so, consider the similar problem where we have to perform 0 or more rotations. In this case, the answer will always have the same number of digits as the original number. Since the number of digits cannot increase as the result of a rotation, each rotation must leave the number of digits unchanged. Suppose we have some sequence of rotations that produces the maximal answer. Any consecutive rotations in different diretions must have no net effect. Thus we can remove such pairs until all rotations are in the same direction. Additionally, any D rotations in the same direction have no net effect, where D is the number of digits in N. We can remove sets of D rotations until fewer than D rotations remain. Now if there are exactly D-1 rotations, we can replace them with 1 rotation in the opposite direction. Thus at most D-2 rotations are needed, all in the same direction.

Now the original problem is equivalent to performing one rotation followed by 0 or more additional rotations. Therefore the solution will involve performing one rotation in one direction, followed by 0 or more rotations in another direction (which may be the same as the first direction). We can show that each of the 4 possible cases can be simplified to one of the 4 cases above.

To solve using a breadth first search, use a set and a queue (or, for a depth first search, use a stack). Initially, insert N into the queue. Then as long as the queue is non-empty, remove a number from it, and rotate that number in each direction. For each of the 2 resulting numbers, check if it exists in the set. If not, insert it into both the set and the queue, otherwise do nothing. When the queue is empty, the largest element in the set is the answer.

Problem Setter's Solution
Problem Tester's Solution

----------------------------------------------------------

LASTDIG: Last Digit Sum

This problem can be solved using dynamic programming, however a more sophisticated solution exists. Denote C(N) as the sum of D(N) over all values from 0 to N-1 (inclusive). Our goal is to calculate C(B+1)-C(A). Note that the first 10 values of D(N) are 0, 1, 4, 3, 8, 5, 2, 7, 6, 9. Each number from 0 to 9 appears exactly once. Also note that D(10*k + i) = (D(k)+D(i))%10, where 0≤i<10. It follows that each number from 0 to 9 will also appear exactly once in D(10*k + i) as i ranges from 0 to 9 and k is fixed. Therefore, C(10*k)=45*k for all k. This allows us to compute C(N) quickly by using C(N) = 45*N/10 if N is a multiple of 10, and C(N) = C(N-1) + D(N-1) if N is not a multiple of 10.

Problem Setter's Solution
Problem Tester's Solution

----------------------------------------------------------

TARPRACT: Target Practice

A naive DP solution to this problem solves it in O(N*2^N). Store the state of the targets in a bitmask, and for each of the possible 2^N states, simulate each of the possible outcomes from firing at each of the N targets, then choose the one with the lowest expected number of shots. Since it's possible to hit a target that's already been hit, the expected number of shots required is (1+sum(P(T)*E(T)))/(1-Q), where P(T) is the probability of hitting target T (and T hasn't been hit yet), E(T) is the expected number of additional shots needed if target T is hit, and Q is the probability of hitting a target that's already been hit or missing completely (if Q is 1, the shot is useless).

The solution can be improved by noticing that once 2 adjecent targets have been hit, the remaining targets to the left of these targets can be considered indepently of those to the right, since no single shot could ever have the potential to effect both. The number of states where no 2 adjacent targets have been hit is O(φ^N), where φ is (sqrt(5)+1)/2, the golden ratio. The total runtime is thus O(N*φ^N).

Problem Setter's Solution
Problem Tester's Solution

-----------------------------------------------------------

YASEQ: Yet Another Sequence

Let us first prove that the entire sequence consists only of N-1, N, and N+1. The proof proceeds inductively. Suppose for some i > N that the first i terms of the sequence are all N-1, N, or N+1. For all j satisfying i-N+1 < j ≤ i we have A[j] ≥ N-1 = i-(i-N+1) ≥ i-j, hence A[i] ≥ N-1. Similarly, for all j satisfying j < i-N-1 we have A[j] ≤ N+1 < i-(i-N-1) ≤ i-j, hence A[i] ≤ N+1. It follows that N-1 ≤ A[i] ≤ N+1 for all i.

We now have that A[i] depends only on A[i-N-1] and A[i-N]. Specifically:

A[i] = N if A[i-N] == N-1 and A[i-N-1] == N+1
A[i] = N+1 if A[i-N] != N-1 and A[i-N-1] == N+1
A[i] = N-1 if A[i-N] == N-1 and A[i-N-1] != N+1
A[i] = N if A[i-N] != N-1 and A[i-N-1] != N+1

Now let's consider sequences consisting only of N and N+1, and sequences consisting only of N-1 and N. For a sequence consisting only of N and N+1, we'll have A[N]=N, and then A[i+N+1]=A[i] for all i. For a sequence consisting only of N-1 and N, we'll have A[i+N]=A[i] for all i. Call the N+1 terms "pegs", and the N-1 terms "holes". Pegs are periodic with period N+1, and holes are periodic with period N. What happens when a sequence contains both pegs and holes? Simple. Every time a peg and hole collide, the peg fills the hole and they are both eliminated.

So all we have to do is figure out which pegs fill which holes and when. The process works as follows. Create a stack. Starting at the beginning of the sequence, every time a peg is found push it on the stack. Every time a hole is found, match it with the top peg from the stack (unless the stack is empty, in which case do nothing). If i is the index of the peg, and j the index of the hole, then the index x at which they collide will satisfy x = i (mod N+1) and x = j (mod N). We can use the Chinese Remainder Theorem to find that x = j*(N+1) - i*N (mod N*(N+1)).

Now to answer each query, compute the position of the peg and hole associated with the query. If there is a peg or a hole, check if it has been eliminated.

Problem Setter's Solution
Problem Tester's Solution

------------------------------------------------------------