https://www.acmicpc.net/problem/13335
initial
I solved this in programmers and knew the general approach but still couldnt implement this. This is an implementation like how a human would solve it. We first fill a bridge deque of 0s and simulate train on this bridge coming it from the right and exiting to the left. While there are still trains waiting OR if current weight of bridge is greater than 0 ( which means there is still a train on the bridge), we pop the left of the bridge and subtract current weight of bridge with that left value. Obviously at time=0, it is minusing 0 but as while loop goes on, the current weight of bridge will subtract the train’s weight as the right side of bridge will be padded with 0s.
If the first train in the deque of waiting trains + current weight of bridge is less or equal to the max weight that the bridge can withstand, we pop this first train and append to the right of the bridge. very impt there is another if condition missing. If there is no waiting trains left cuz we have all popped them off and appended to the bridge, we shouldnt traverse this cuz trying to pop from an empty deque will cause index out of range error.
Else we add 0 to the bridge. All the while we increment time.
solution
from collections import deque
n, w, max_weight = map(int, input().split())
lst = list(map(int, input().split()))
train_queue = deque(lst)
bridge_queue = deque([0 for _ in range(w)])
cur_weight = 0
time = 0
while train_queue or cur_weight > 0:
cur_node = bridge_queue.popleft()
cur_weight -= cur_node
if train_queue and cur_weight + train_queue[0] <= max_weight:
tmp = train_queue.popleft()
bridge_queue.append(tmp)
cur_weight += tmp
else:
bridge_queue.append(0)
time += 1
print(time)complexity
Time Complexity:
The time complexity of this code is primarily determined by the while loop, which iterates until both train_queue is empty and cur_weight is zero. The worst-case scenario is that each element in the lst is processed once, resulting in a time complexity of O(n).
Space Complexity:
The space complexity is determined by the size of the train_queue and bridge_queue. The train_queue stores the input list, and the bridge_queue has a maximum size of n. Therefore, the space complexity is O(n) for both data structures.
In summary:
Time Complexity: O(n)
Space Complexity: O(n)
