Discussion on Ants Challenge

1 year ago+ 0 comments

Most solutions (and even the editorial) are not fully correct, because they ignore this case:
If there are ants on positions 999 and 0 (distance 1 over ends of intervall) the algorithms may give wrong results, e.g : the algos find one pair (0,1), not two pairs (1,2), (999,0) .
(see also post of ygrinev below).

Clumsy but correct solution:

def solve(V):
    n = len(V)
    # instead of turning, the ants can be seen to pass each other
    # so they simply go around and around. 
    # in each direction go about half of them,
    #   meeting the other half 2 times a round, 2x hello in a meeting
    # 1 round is 10_000 sec, 10**9 sec is 10**5 rounds
    meets = (n//2) * (n-n//2) * 2 * 2 * 10**5
    # now what about the last 6 sec? => must maximize meetings here
    # 6 sec is 0.6 m per ant, that is ants can only meet if adjacent
    V.sort()
    for pos in range(n): 
        if (V[pos]-V[pos-1])%1000 > 1: break
    run = 0
    for i in range(pos, pos+n):
        if (V[i%n]-V[(i-1)%n])%1000 == 1:
            run += 1
        else:
            meets += (run+1)//2 * 2
            run = 0
    else:
        if run: meets += (run+1)//2 * 2
    return meets

Cookie support is required to access HackerRank