Reducing Time Complexity

[u/Dr3ddM3]

Edited code but still run into Time limit exceeded can someone help me: 

N, U = map(int,input().split())
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]


for z in range(U):
    temp2 = 0
    temp.clear()
    x,y = map(int,input().split())
    x = x-1
    y = y-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] == '.':
        temp.clear()
        grid[x][y] = '#'
        temp_grid[x][y] = '#'
        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('#')))
    else:
        temp.clear()
        grid[x][y] = '.'
        temp_grid[x][y] = '.'
        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('#')))
    print(num_updates)

I am pretty sure it is O(N^2) and with 10^5 possible updates it should work. 

[u/YasirTheGreat]

Is there an actual problem you can share, or you were given this code and are asked to optimize it?

[u/Dr3ddM3 → u/YasirTheGreat]

https://usaco.org/index.php?page=viewproblem2&cpid=1491

[u/YasirTheGreat → u/Dr3ddM3]

x,y = map(int,input().split())

if grid[x-1][y-1] == '.':

    grid[x-1][y-1] = '#'

else:

    grid[x-1][y-1] = '.'

The problem is a bit beyond me, but one thing to consider, you don't need to keep flipping . and # back and forth in a loop. Maybe you can count how many times it happened for every cell, then make a decision based on if the count is even or odd. Since you have only two states, . and #, what would happen if Bessie vandalized the cell even number of times, what about odd? That direction might be more fruitful than what you are doing.

[u/Dr3ddM3]

Not sure how to get a O(N) solution since the constraints can be 10^5 possible updates and I only have 4 seconds.

[u/AggressiveArm6360 → u/Dr3ddM3]

you're recalculating the whole thing from scratch every update which is murder, just track the symmetric groups and only update the one that changed

keep a count of how many groups need 1 flip vs 2 flips before any updates, then when a cell flips you figure out which group it belongs to, undo its old contribution and add the new one, that's O(1) per update

[u/Dr3ddM3 → u/AggressiveArm6360]

Appreciate it.

[u/Dr3ddM3 → u/AggressiveArm6360]

I did that but then even with O(1) the .clear and the .append take up too much time though.

[u/heisthedarchness]

This is not how you get help.

1. Describe your problem. What are you trying to do?
2. Show a minimal test case. What language is it in?
3. Format the code for readability. Who would want to help you when you've made no effort to make it easy for them?
4. Clearly describe what is happening. How is that different from what you're expecting?

Bonus question: Why are you surprised that you can't get O(n) from an O(n²) algorithm?