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.
CodePudding user response：
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.
CodePudding user response：
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 1010 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))):
ops = next(stdin).strip()
forward = True
trim_from_front = 0
trim_from_rear = 0
for op in ops:
if op == "R":
forward = not forward
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 = [int(x) for x in next(stdin)[1:-2].split(",")]
if trim_from_rear > 0:
x = x[trim_from_front:-trim_from_rear]
elif trim_from_front > 0:
x = x[trim_from_front:]
print("[", end="")
if not forward:
x = reversed(x)
print(",".join([str(y) for y in x]), end="")
print("]")
if __name__ == "__main__":
main()
See also: