🔒 Wall Clock limit/time limit exceeded

[warped herald]

import sys
from sys import stdin, stdout

N = int(sys.stdin.readline())
lst =  [int(x) for x in sys.stdin.readline().split()]
lst.sort()
smallest = [0] * len(lst)
for i in range(len(lst)):
    smallest[len(lst)-i-1] = lst[i]
Q = int(sys.stdin.readline())

for i in range(Q):
    length = len(smallest)
    a, b = map(int, sys.stdin.readline().split())
    if a == 1:
        for j in range(length):
            
            if smallest[j] < b:
                smallest.insert(j, b)
                break
            elif j == length-1:
                smallest.append(b)
        
            
    
        
    else:
        if bool(smallest):
            sys.stdout.write(str(smallest[-1])+"\n")
            smallest.pop()

        
    

[leaden mortar]

@warped herald

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[warped herald]

it is also uncertain if my code works fine for all cases, but it has passed all public test cases that it doesn't time out at for now

[warped herald]

i reversed the order so that i could pop instead of having to sort + remove first index everytime which are both O(N) functions

[valid minnow]

so if it works for the given samples whats causing it to fail?

are there hidden test cases?

[warped herald]

wall clock limit/time limit exceeded

[valid minnow]

yeah but for what input is the time limit exceeded? since youre saying it works for some cases

[warped herald]

nobody knows

why would you need to know the input, it's just finding a way to make it faster

theres this one annoying test case for subtask 1 that exceeds the time limit so that means my code is slow af T-T

[valid minnow]

i just wanted to know if its your loops getting stuck or something like that but i see what you mean now

you could try using a heap instead of a list, its O(logn) instead so that could be it

[warped herald]

i have no idea what a heap is and i probably can't learn it in time

[valid minnow]

hm yeah probably not what they want you to do then

[warped herald]

no it's just my lack ok knowledge and practice XD

anything is allowed

[valid minnow]

but yeah clearly inserting or appending for every element would be bad performance if you had a really big list

[warped herald]

wait a min

nvm

there's no function that reverses a list in O(1)

cuz like i reverse sort them so i can pop, but that means I can't use bisect.bisect

unless there's a way that idk about

[valid minnow]

idk theres something obvious im missing ive been awake too long, sorry

[warped herald]

D:

ok erm im gonna try appending, then sorting, then reversing the order, then popping

[cedar tinsel]

sounds like a lot of expensive operations

[valid minnow]

reversing the list like that isnt helping either

[warped herald]

wait that doesn't do anyting lmao

[static turtle]

I don't understand why you do this and then use the insert

smallest = [0] * len(lst)

[warped herald]

i used insert so that it remains sorted so that i can pop at the end

[valid minnow]

ok for one instead of sorting the list and then getting the last item as the smallest, you should just go through the list and compare the current number to the smallest one youve seen so far

[warped herald]

wouldn't that be slower

[valid minnow]

no because you are only running through the list once

[warped herald]

no but to remove is O(N)

[cedar tinsel]

sorting at each insert is probably more expensive than to just change the list when you need to get the smallest value out unless there is a lot of inserts and very few removals

[warped herald]

lemme try this rq

wait i tried it alr with the min()

which is the same thing right

[cedar tinsel]

min() will only give you the value but not the element index of that value in the list

[warped herald]

list.remove(value) removes the earliest occurring value

wwhich can be paired with min()

[cedar tinsel]

true, but then it needs to iterate through the lists two times

first through the whole list to find the smallest value, then from the beginning until it finds the first occurrence of that value

[static turtle]

A solution that avoids iterating through the list is to insert the smallest value at the beginning of the list if it's smaller than the current first element; otherwise, just append it to the end.

if my_list and number < my_list[0]:
    my_list.insert(0, number)
else:
    my_list.append(number)

[cedar tinsel]

then it needs to alter the list by deleting that element

[static turtle]

print(my_list[0])
my_list.pop(0)

[warped herald]

?

but you still have to uh

idk it's still O(N) solution to remove it

[static turtle]

O(1)

[warped herald]

to remove the smallest integer is still O(N)

right?

[static turtle]

no

[warped herald]

[3, 4, 5, 6, 7, 8,..., 100000, 2, 2, 2, 2, 2]

[cedar tinsel]

if i remember right, inserting at the front is "expensive" for pythons implementation of lists

[warped herald]

yes because you have to move every index back

[static turtle]

with the logic I sent, the smallest number will always be index 0

[warped herald]

removing the first index also means you have to move every index forward by one

furthermore, you can't guarantee that the smallest index won't be at the back

which i just proved using the list example(?)

[1, 2, 3, 4, 5, 6, 7, 8,..., 100000] so you have this list, then it asks you to insert a 2 but 2 is bigger than 1 so it gets appended [1, 2, 3, 4, 5, 6, 7, 8,..., 100000, 2], then you remove the 1, then you remove the 2 [3, 4, 5, 6, 7, 8,..., 100000, 2] now how do you know the smallest element is at the front

[static turtle]

you can use deque

[warped herald]

heh?

(my knowledge of data structures is limited T-T)

[cedar tinsel]

are you restricted to a normal list?

deque is a double ended list

[static turtle]

it is an implementation of a doubly linked list, it does not have the problem of moving the remaining indexes

[cedar tinsel]

cheap to insert and remove from either end

[warped herald]

no

[cedar tinsel]

then deque is a good option for you

[warped herald]

^

i think i'll just find another question to solve..

i dont have to solve all the questions

they are probably easier

one is findin the smallest span of a subarray that contains all the numbers

[trim mica]

isn't this just use a heap?

[warped herald]

yeah bbut idk how to use a heap

[trim mica]

pretty easily actually, cause there's the heapq stdlib

[warped herald]

im havin dinner now so ill see wheen i come finish

[leaden mortar]

Python help channel closed for inactivity

This help channel has been closed. Feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.