Bathroom stalls in Python 3 (Google Code Jam 2017)

Question

This problem is tested against 3 sets of input data to see if the submitted solution gives an incorrect answer, if the solution exceeds the time limit, or if the solution exceeds the memory limit:

Test set 1 (Visible):

1 ≤ N ≤ 1000.

Test set 2 (Visible)

1 ≤ N ≤ 10^6.

Test set 3 (Hidden)

1 ≤ N ≤ 10^18.

My solution (below) passes test sets 1 & 2 but fails test set 3 due to an incorrect answer... This puzzles me. To see if there's a corner/edge case I'm missing here that's only present in the 3rd test set I have it running against a brute force (quadratic) algorithm, testing every allowed N & K combination but so far no differences.

Any help in identifying where I've gone wrong would be greatly appreciated! I'd love to find an example (N,K) input pair where the solution fails so I can debug.

Also, any tips on readability, code quality, best practices I should be following, pythonicness, etc would be helpful. If I should be adding comments to help any potential reviewers please let me know and I'll gladly oblige.

Many thanks!

https://codingcompetitions.withgoogle.com/codejam/round/0000000000000130/0000000000000652

Problem

A certain bathroom has N + 2 stalls in a single row; the stalls on the left and right ends are permanently occupied by the bathroom guards. The other N stalls are for users.

Whenever someone enters the bathroom, they try to choose a stall that is as far from other people as possible. To avoid confusion, they follow deterministic rules: For each empty stall S, they compute two values LS and RS, each of which is the number of empty stalls between S and the closest occupied stall to the left or right, respectively. Then they consider the set of stalls with the farthest closest neighbor, that is, those S for which min(LS, RS) is maximal. If there is only one such stall, they choose it; otherwise, they choose the one among those where max(LS, RS) is maximal. If there are still multiple tied stalls, they choose the leftmost stall among those.

K people are about to enter the bathroom; each one will choose their stall before the next arrives. Nobody will ever leave.

When the last person chooses their stall S, what will the values of max(LS, RS) and min(LS, RS) be?

Input

The first line of the input gives the number of test cases, T. T lines follow. Each line describes a test case with two integers N and K, as described above.

Output

For each test case, output one line containing Case #x: y z, where x is the test case number (starting from 1), y is max(LS, RS), and z is min(LS, RS) as calculated by the last person to enter the bathroom for their chosen stall S.

Limits

1 ≤ T ≤ 100. 1 ≤ K ≤ N. 1 ≤ N ≤ 10^18.

Input               Output 
5
4 2                 Case #1: 1 0
5 2                 Case #2: 1 0
6 2                 Case #3: 1 1
1000 1000           Case #4: 0 0
1000 1              Case #5: 500 499

Solution (in need of review)

from collections import deque

def increment(counts, space, count, q, left=False):
    try:
        counts[space] += count
    except:
        counts[space] = count
        if left:
            q.appendleft(space)
        else:
            q.append(space)

def minmax(stalls, ppl):
    if stalls == ppl:
        return [0,0]

    counts = {stalls: 1}
    q_next = deque([stalls])
    person = 0
    while True:
        q = q_next
        q_next = deque()
        while q:
            space = q.popleft()
            count = counts[space]
            if space % 2:
                if person + count >= ppl:
                    return [int((space - 1)/2), int((space - 1)/2)]
                increment(counts, int((space - 1)/2), 2*count, q_next)
            else:
                if person + count >= ppl:
                    return [int(space/2), int(space/2 - 1)]
                increment(counts, int(space/2), count, q_next, left=True)
                increment(counts, int(space/2 - 1), count, q_next)
            person += count

cases = int(input())

for case in range(cases):
    stalls, ppl = map(int, input().split())
    result = " ".join(map(str, minmax(stalls, ppl)))
    print("Case #%d: %s" % (case + 1, result))

Answer 1

Missing-value logic

This:

try:
    counts[space] += count
except:
    counts[space] = count

has a few problems:

• A bare except is ill-advised; you probably want to be catching KeyError
• Avoid logic-by-exception; for instance:

if space in counts:
    counts[space] += count
else:
    counts[space] = count

Do one better by calling setdefault:

counts.setdefault(space, 0)
counts[space] += count

Do even better by using a defaultdict:

counts = defaultdict(int)
# ... then unconditionally:
counts[space] += count

The last two options you might not be able to meaningfully use if you really need the if left stuff to execute only on the addition of a new key. So this might work:

if not counts.setdefault(space, 0):
    if left:
        q.appendleft(space)
    else:
        q.append(space)
counts[space] += count

Returning a list

This:

return [int((space - 1)/2), int((space - 1)/2)]

should probably drop the brackets, so that you return an implicit 2-tuple:

return int((space - 1)/2), int((space - 1)/2)

Input

Probably better off to have the user input two numbers on separate lines than one line with space separation; and avoid map in this case because it's a little clunky:

stalls, ppl = (int(input()) for _ in range(2))

Formatting

print("Case #%d: %s" % (case + 1, result))

can become

print(f'Case #{case + 1}: {result}')