我不知道我的算法在谷歌代码Jam 2018 1B-B的代码中出了什么问题

Question

现在比赛结束了，所以我想问我的算法在我的代码上失败了。

这就是问题所在。如果有人感兴趣，你可以在这里看到它

def solve():
    S = int(input())
    D, A, B, M, N = [], [], [], [], []
    for i in range(S):
        d, a, b = [int(c) for c in input().split(" ")]
        D.append(d); A.append(a); B.append(b)
        M.append(d+a); N.append(d-b)
    straightMstart, straightNstart = [0]*(S), [0]*(S)
    crossedMstart, crossedNstart = [0]*(S), [0]*(S) # cross over
    for i in range(1, S):
        if M[i] == M[i-1]:
            straightMstart[i] = straightMstart[i-1]
            crossedNstart[i] = crossedNstart[i-1]
        else:
            straightMstart[i] = i
        if N[i] == N[i-1]:
            straightNstart[i] = straightNstart[i-1]
            crossedMstart[i] = crossedMstart[i-1]
        else:
            straightNstart[i] = i
        if M[i] != M[i-1]:
            crossedNstart[i] = straightNstart[i-1]
        if N[i] != N[i-1]:
            crossedMstart[i] = straightMstart[i-1]
    maxlen = 1
    maxlensubsets = 1
    for i in range(1, S):
        thislen = i - min(crossedMstart[i], crossedNstart[i]) + 1
        if maxlen < thislen:
            maxlen = thislen
            maxlensubsets = 1
        elif maxlen == thislen:
            maxlensubsets += 1
    # print(crossedNstart)
    # print(crossedMstart)
    return "%d %d" % (maxlen, maxlensubsets)
testcase = int(input())
for tc in range(1, testcase+1):
    print("Case %d: %s" % (tc, solve()))

我使用交叉的最大长度来找到集合的最大大小。(对于 M 和 Ns(

我将给你举个例子，以便更容易理解我的逻辑：

# Let's suppose that the M and N is:
M (=D[i]+A[i]) = [  9,  9, 18, 22, 22]
N (=D[i]-B[i]) = [-10, -5,  7, -1, -1]
# Straight Start means starting index for same value.
# M=9 starts from index 0, M=18 starts from index 2, M=22 starts from index 3
straightMstart = [0, 0, 2, 3, 3]
# Same logic applied to straightNstart
straightNstart = [0, 1, 2, 3, 3]
# Crossed Start means cross-starting index of opponent array.    
# For crossedMstart, you start from N[i] and climb N then cross to climb M
# The reason why I swapped order of cNs and cMs is that both arrays are based on opponent arrays
crossedNstart = [0, 0, 1, 2, 2]
crossedMstart = [0, 0, 0, 2, 2]

我真的很困惑，我真的不明白我的错是什么。请帮助我纠正我的逻辑。

Answer 1

您的算法有多种失败方式。其中最简单的方法是在任何输入中输入string。然后我确实看到了straightNstart[i]的问题，如果N[i]或M[i]匹配N[i-1]或M[i-1]，则当前迭代始终为零。这会将crossedMstart[i]和crossedNstart[i]值设置为 0 。另一个问题是当S <= 1忽略两个循环时。

第一个问题很容易解决，它可能涵盖了d，a，b，testcase的问题，其中d，a，b，testcase应该只引发TypeError：

S = input("[description]")
if S.isdigit():
    S = int(S)
    if S <= 1:
        raise ValueError("Value must be greater then 1")
else:
    raise TypeError("Value must be numeric")

对于另一个问题，可以迭代两次，以便straightNstart[i]、straightMstart[i]赋值对结果有任何影响(至少当M[i]或N[i]不等于M[i-1]或N[i-1]时

(。

Answer 2

我发现我的算法无法处理多个交叉。