Buggy python submission (verdict: Runtime Error):
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed([int((3 ** i - 1) / 2) for i in range(1, len(array)) if (3 ** i - 1) / 2 < len(array)]))
    if not G:
        G = [1]
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    n = int(input())
    A = [int(input()) for _ in range(n)]
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    print('\n'.join(map(str, A)))

Fixed submission:
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Buggy python submission (verdict: Runtime Error):
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    n = int(input())
    A = [int(input()) for _ in range(n)]
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    print('\n'.join(map(str, A)))

Fixed submission:
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Buggy python submission (verdict: Runtime Error):
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    i = 2
    while 1:
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()
        i += 1


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    n = int(input())
    A = [int(input()) for _ in range(n)]
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    print('\n'.join(map(str, A)))

Fixed submission:
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Buggy python submission (verdict: Runtime Error):
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    n = int(input())
    A = [int(input()) for _ in range(n)]
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Fixed submission:
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Buggy python submission (verdict: Runtime Error):
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    n = int(input())
    A = []
    for _ in range(n):
        A.append(int(input()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Fixed submission:
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Buggy python submission (verdict: Runtime Error):
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Fixed submission:
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Buggy python submission (verdict: Runtime Error):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import sys
  
def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
  
# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))
  
# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]
  
# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))
  
# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])
  
# 3 output cnt
print(cnt)
# 4 output sorted a
print('\n'.join(map(str, a)))

Fixed submission:
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Buggy python submission (verdict: Runtime Error):
import sys
   
def isort(a, n, g):
    global cnt
    for i in range(g, n):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j + g] = a[j]
            j -= g
            cnt += 1
        a[j + g] = v
   
# input data
n = int(sys.stdin.readline())
a = []
for i in range(n):
    a.append(int(sys.stdin.readline()))
   
# determine m, g
g = [1]
m = 1
while True:
    x = 3 * g[m - 1] + 1
    if x >= n: break
    g.append(x)
    m += 1
g = g[::-1]
   
# 1 output m
print(m)
# 2 output g
print(' '.join(map(str, g)))
   
# sort it
cnt = 0
for i in range(m):
    isort(a, n, g[i])
   
# 3 output cnt
print(cnt)
# 4 output sorted a
print('\n'.join(map(str, a)))

Fixed submission:
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/python
import sys
if sys.version_info[0]>=3: raw_input=input
 
def insertionSort(a,g):
    global cnt
    for i in range(g,len(a)):
        v = a[i]
        j = i - g
        while j >= 0 and a[j] > v:
            a[j+g] = a[j]
            j = j - g
            cnt+=1
            a[j+g] = v
 
def shellSort(a):
    global cnt
    cnt = 0
    g = []
    h = 1
    while h <= len(a):
        g.append(h)
        h = 3*h+1
    g.reverse()
    m = len(g)
    print(m)
    print(' '.join(map(str,g)))
    for i in range(m):
        insertionSort(a,g[i])
 
a=[int(raw_input()) for i in range(int(raw_input()))]
shellSort(a)
print(cnt)
for e in a: print(e)

Fixed submission:
def insertion_sort(array, g, result):
    for i in range(g, len(array)):
        v = array[i]
        j = i - g
        while j >= 0 and array[j] > v:
            array[j + g] = array[j]
            j -= g
            result['count'] += 1
        A[j + g] = v


def g_gene(n):
    yield 1
    for i in range(2, n):
        x = int((3 ** i - 1) / 2)
        if x < n:
            yield x
        else:
            raise StopIteration()


def shell_sort(array, result):
    result['count'] = 0
    G = list(reversed(list(g_gene(len(array)))))
    m = len(G)
    result['G'] = G
    result['m'] = m
    for i in range(m):
        insertion_sort(array, G[i], result)


if __name__ == '__main__':
    import sys
    n = int(sys.stdin.readline())
    A = []
    for _ in range(n):
        A.append(int(sys.stdin.readline()))
    result = {}
    shell_sort(A, result)
    print(result['m'])
    print(' '.join(map(str, result['G'])))
    print(result['count'])
    for a in A:
        print(a)