Keep getting wrong answer for Integer List challenge on Kattis even though it works just fine for the test case

Question

I am trying to solve the Integer Lists challenge on Kattis.

for _ in range(int(input())):
    operation, elements = input(), int(input())
    error = False
    if elements <= 0:
        input()
        print('error')
    else:
        inp_lst = list(map(int, input().strip('[]').split(',')))
        for op in operation:
            try:
                if op == 'R':
                    inp_lst.reverse()
                elif op == 'D':
                    inp_lst.pop(0)
            except IndexError:
                print('error')
                error = True
                break
        if not error:
            print(inp_lst)

Sample input:

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

Expected Output:

[2,1]
error
[1,2,3,5,8]
error

My code does get the right output, but it is still getting marked wrong. I am not sure what's wrong with my solution. Any help would be appreciated.

Answer 1

Your solution is too straightforward. Reversing a list and removing the first element is an O(n) operation, which you potentially repeat O(len(p)) times. Obviously, a O(n * len(p)) solution will time out, and it will be marked as wrong.

To improve the solution, you need to realise that reversing the list isn't actually required. You can manipulate that by keeping a track of the end which "acts" like the list head.

Answer 2

This is one of those unnecessarily cruel coding challenges that seems pretty straightforward, but requires a good deal of micro optimization to pass.

As mentioned in this answer, for starters, you shouldn't take the "drop" and "reverse" operations literally. Reversing a list is O(n), so in a worst-case scenario where you have a 100k element list and the operations are 100k of R, you're doing 10¹⁰ steps that achieve nothing.

A better approach is to use a deque and a boolean. The deque has O(1) removal at either end, and the boolean flips back and forth between the front and back to determine which side to drop elements from. If we end with the list in a "reversed" state, print it reversed. Now we're down to linear time, but for Python, simple linear time isn't necessarily good enough, so we have to attack the constant factor.

My next attempt was to avoid the deque and instead focus on counting the number of elements I needed to remove on either end, then removing them all in one fell swoop with a slice. Separating the execution and analysis of the operations led to more optimizations. The order of the input for each test case is a good hint: we collect the operations, then the list size n, then the list contents. Whenever there are more drops than items in the list, we can avoid parsing the list and print error. If there are an equal number of drops as items in the list, we can print [] and again avoid parsing the list.

Tossing in these micro optimizations eventually allowed me to pass. Here's my solution:

from sys import stdin

def main():
    for _ in range(int(next(stdin))):
        forward = True
        trim_from_front = 0
        trim_from_rear = 0

        for op in next(stdin):
            if op == "R":
                forward = not forward
            elif op == "\n":
                break
            elif forward:
                trim_from_front += 1
            else:
                trim_from_rear += 1

        n = int(next(stdin))

        if trim_from_front + trim_from_rear > n:
            print("error")
            next(stdin)
            continue
        elif trim_from_front + trim_from_rear == n:
            print("[]")
            next(stdin)
            continue

        x = next(stdin)[1:-2].split(",", n - trim_from_rear)

        if trim_from_rear > 0:
            x.pop()

        if trim_from_front > 0:
            x = x[trim_from_front:]

        if not forward:
            x = reversed(x)

        print("[", ",".join(x), "]", sep="")


if __name__ == "__main__":
    main()

See also:

• Fast Python I/O
• Why does Python code run faster in a function?

Answer 3

So there are a few different things wrong with your program. First, as others have mentioned, your solution is widely inefficient. While it would work in theory, you have the entirely wrong approach to the problem. You haven't gotten the 'right idea' yet. The reason you are failing is because the output format is wrong.

This line

print(inp_lst)

prints the list as comma separated with spaces, when you shouldn't have spaces. kattis compares the output byte by byte, so even a unexpected '\n' will cause you to fail.

Other things to consider:
Do you print "[]" when the list has all elements removed?

While this is the reason you are failing, you are not going to pass with your current solution, as you'll time out fairly fast. While others have posted the correct idea's and code, I suggest you refrain from looking at them to improve your problem solving skills