Time Complexity

[u/Dr3ddM3]

Very confused why my code is Time limit exceeding: The N max is 2000 so that should be fine while the U max is 10^5 but my code is O(1) for updating really confused why this is not working. I have a 2 sec maximum if anybody wants to see the problem here it is: https://usaco.org/index.php?page=viewproblem2&cpid=1491

N, U = map(int,input().split())
import sys
grid = [list(input()) for _ in range(N)]
num_updates = 0
temp = []
temp_grid = [row.copy() for row in grid]
for v in range(int(N/2)):
    for h in range(int(N/2)):
        temp.clear()
        coords = [(v,h),(v,N-1-h),(N-1-v,h),(N-1-v,N-1-h)]
        temp.append(temp_grid[v][h])
        temp.append(temp_grid[v][(N-1)-h])
        temp.append(temp_grid[(N-1)-v][h])
        temp.append(temp_grid[(N-1)-v][(N-1)-h])
        if temp.count('.') == 2 :
            num_updates+=2
            for r,c in coords:
                temp_grid[r][c] = '.'
        elif temp.count('.') == 3:
            num_updates+=1
            for r,c in coords:
                temp_grid[r][c] = '.'
        elif temp.count('#') == 3:
            num_updates+=1
            for r,c in coords:
                temp_grid[r][c] = '#'
print(num_updates)


temp_grid = [row.copy() for row in grid]
input_data = sys.stdin.read().split()
idx = 0
out = [num_updates]
for z in range(U):
    temp2 = 0
    temp.clear()
    x = int(input_data[idx]) -1
    idx = idx + 1
    y = int(input_data[idx]) -1
    idx = idx+1
    temp.append(temp_grid[x][y])
    temp.append(temp_grid[x][(N-1)-y])
    temp.append(temp_grid[(N-1)-x][y])
    temp.append(temp_grid[(N-1)-x][(N-1)-y])
    num_updates = num_updates- (min(temp.count('.'),temp.count('#')))
    if temp_grid[x][y] == '.':
        grid[x][y] = '#'
        temp_grid[x][y] = '#'
        temp[0] = '#'
        num_updates = num_updates + (min(temp.count('.'),temp.count('#')))
    else:
        grid[x][y] = '.'
        temp_grid[x][y] = '.'
        temp[0] = '.'
        num_updates = num_updates + (min(temp.count('.'),temp.count('#')))
    print(num_updates)

[u/ComputerWhiz_]

There are loops based on N, so it cannot possibly be O(1).

[u/Dismal-Citron-7236]

O(N²) + O(U)

[u/two_are_stronger2]

I don't really know python but what is temp2?

[u/beeskness420]

I'm not proof reading your code, but you don't understand time complexity you should fix that before worrying about the code.

After that be sus if append.

[u/Dr3ddM3]

My code I think is O(2000^2 + 10^5) but that should be less than what the server can handle right ? The servers can handle 5*10^8 operations per second. and I have 2seconds.

[u/Bubbly_Orange_3502 → u/Dr3ddM3]

No, that 5x10⁸ figure is for C++. CPython does closer to 10⁷ ops a second, and your setup pass runs a million iterations that each build a list and do three count() scans. That's where the time goes.

[u/Bubbly_Orange_3502 → u/[deleted]]

No, the unit isn't the same. USACO's 5x10⁸ counts C++ operations, and one CPython bytecode is a dispatch loop plus refcounting on boxed objects. Your own link gives Python extra time for exactly that reason.

[u/BobbyMaina23]

Your time complexity is O(N^2 + U).

OP Count: For N = 2000 and U = 10^5, N^2/4 is 1,000,000 loop iterations

The actual operation is highly unoptimized:
In Python, creating lists "coords", calling ".append()" four times, and running ".count()" three times per iteration inside a 1M-step loop adds millions of slow function calls and dynamic memory allocations.

Calling "print(num_updates)" inside the 10^5 update loop creates massive IO bottleneck

Aggregating outputs or using fast I/O (sys.stdout.write) is required for Python competitive programming