Discussion on: Daily Coding Puzzles - Oct 29th - Nov 2nd

So I was curious since this solution didn't seem correct, and tried to run this through the codejam grader, and it seems like it isn't correct.

I had some fun with this problem, though (it entertained some part of a plane ride), and came up with a nice concise solution:

#!/usr/bin/python
from collections import defaultdict


def left_range(x):
    return x//2 - (1 if x%2 == 0 else 0)


def right_range(x):
    return x//2


def best_toilet(n, k):
    assert n >= 1
    assert 1 <= k <= n

    k -= 1
    ranges = defaultdict(lambda: 0)
    ranges[n] = 1
    while True:
        r = max(ranges.keys())
        quant = ranges[r]
        if k >= quant:
            k -= quant
            del ranges[r]
            ranges[left_range(r)] += quant
            ranges[right_range(r)] += quant
        else:
            break

    m = max(ranges.keys())
    return (left_range(m), right_range(m))


def main():
    t = int(input().strip())
    for i in range(t):
        n, k = (int(val) for val in input().strip().split(' '))
        min_dist, max_dist = best_toilet(n, k)
        print("Case #%d: %d %d" % (i+1, max_dist, min_dist))


if __name__ == "__main__":
    main()

A few insights here:

1. When picking a stall, instead of considering two pieces, Rs, Ls, of state, all you need to know is the size of groups of free stalls. You always pick the middle stall of the largest group of sequential free stalls (in case of ties, you pick the leftmost group, in case the size is even, you pick the half-left stall).
2. Order doesn't matter - the problem doesn't ask for which stall the Kth person is going to pick, it asks indirectly for the size of the group (given the size of the group you can easily compute max(Ls, Rs) and min(Ls, Rs).
3. You can group stall groups by size - so this is a little trickier, but you can consider the choices of stalls as a binary tree (the solution above seemed to be going in that direction). Each choice corresponds to a group of stalls. At each level of the binary tree, you'll have a lot of repeated group sizes. In particular, each level of the binary tree has at most 2 different group sizes (I'll leave this as an exercise for you to prove). So, instead of splitting each group one at a time, since order doesn't matter, we can split all groups of the same time in one step, and just add groups for the next level.

At the end you get a nice concise O(log(K)) runtime and O(1) space solution.

Here's an example of how this works by manually solving N=1000 and K=100:

You start with a group of size 1000 for free stalls, so your group size -> number of groups maps looks like this:

Step 1:
1000 -> 1
k = 100

You split 1000 into two groups, one of 499, and one of size 500, and this represents the choice of 1 person, since there is 1 group of size 1000. So now our state looks like:

Step 2:
500 -> 1
499 -> 1
k = 99

Now you split 500 into 249 and 250:

Step 3:
499 -> 1
249 -> 1
250 -> 1
k = 98

Now I'll just draw the next steps, without explaining:

Step 4: 250 -> 1, 249 -> 3, k = 97
Step 5: 249 -> 3, 125 -> 1, 124 -> 1, k = 96
Step 6: 125 -> 1, 124 -> 7, k = 93
Step 7: 124 -> 7, 62 -> 2, k = 91
Step 8: 62 -> 9, 61 -> 7, k = 84
Step 9: 61 -> 7, 31 -> 9, 30 -> 9, k = 75
Step 10: 31 -> 9, 30 -> 23, k = 68
Step 11: 30 -> 23, 15 -> 18, k = 59
Step 12: 15 -> 41, 14 -> 23, k = 36

Now things get special, because there are 41 groups of 15 free stalls, but only 36 people left to choose a stall. Therefore, the last person will choose the middle stall of a group of 15 free stalls, and thus Ls = 7 and Rs = 7!