1. Up/down CounterHenge

We'll show that the amortized cost of an increment or decrement can be set to 2. Let the potential function Φ(s) equal the number of nonzero stones in s, where s is a sequence of 1,0,-1 values as in the description if the problem.

Now consider an increment that takes s to s'. Let k be the number of ones at the end of s (possibly 0). Each of these ones gets change to a zero in s', reducing the potential function by k. In addition, the (k+1)-th least significant stone changes from a minus to a zero (reducing the potential function by 1) or from a zero to a one (increasing the potential function by 1). We also pay k+1 to move all the stones. So we have

• Φ(s') - Φ(s) + cost ≤ -k + 1 + (k+1) = 2,

which is our desired amortized cost for an increment.

The analysis for decrements is completely symmetric with the role of -1 and +1 reversed. So we get an amortized cost of 2 for a decrement as well.

2. A solitaire game

1. Let's cheat and assume that all the cards have n-1 on them; any upper bound we prove for this case will apply to the case in the problem, and since half the cards have at least (n-1)/2, it's likely that the bound will be within a constant factor of the real upper bound. If we are counting off n-1 face-up cards and there are m face-up cards, we pass over at most n cards total for every m face-up cards we count. This gives us a cost for one turn of the game of O(n*(n-1)/m) = O(n²/m). Summing over all m gives a cost of O(n² ∑_{m=1 to n-1} 1/m) = O(n² H_n-1) = O(n² log n).

2. We'll use an OrderStatisticsTree; we'll also assume that the OrderStatisticsTree implementation allows us to compute the number of elements m in O(1) time. At each step of the game we keep only the remaining face-up cards in the tree, along with an index that tells us which card to remove next. To play a turn starting with the i-th card, we first find the i-th card (in O(log n) time), observe its value k, delete it (again in O(log n) time), and then set the index to (i+k-1) mod m, where m is the new number of face-up cards in the tree. Repeating this process at most n-1 times reaches the star card in O(n log n) time.

3. If the number on each card is at most k, then we can play the game in the following way: starting at position one, count off and mark cards as turned over according to the naive algorithm until you reach the end of the row of cards. At this point a fraction of at least 1/k of the cards are face down. Copy the face-up cards into a new array in time O(n), and apply the same algorithm to the new array, starting at whatever position we reach with the unused count from the previous step. The recurrence for this problem is T(n) = O(n) + T(n(1-1/k)), which has solution T(n) = O(n) for constant k.