As the problem states in order not to be noticed by the guard we should not execeed h. We can simply track the width(a variable w) of the road by tracking the number of people that exceeds the h and that don't and incrementing 2 and 1 to w(width of a road) respectively.

• Time complexity: $$$O(n)$$$
• Space complexity: $$$O(1)$$$

n, h = map(int, input().split())
heights = list(map(int, input().split()))
total = n

for height in heights:
    total += height > h    
 
print(total)

Let's iterate through the given array from the left to the right and store in the variable cur the length of the current increasing subarray. If the current element is more than the previous we need to increase cur on one. In the other case we need to update the answer with the value of cur and put in cur 0, because new increasing subarray began.

• Time complexity: $$$O(n)$$$
• Space complexity: $$$O(1)$$$

n = int(input())
a = list(map(int, input().split()))
 
ans = 1
cur = 1
 
for i in range(1, n):
    if a[i] <= a[i-1]:
        ans = max(ans, cur)
        cur = 0
    cur += 1
 
print(max(cur, ans))

The statement we should focus on is the one that says and I quote, "the box covers stairs with numbers 1, 2, ..., wi." on line 4 of the question. Let us take some examples and explain it a bit more. If there was a box with width 4, then this would cover the first 4 stairs. And box with width 6 would cover the first 6 stairs. What the aforementioned question statement implies is that if another box with width 2 — meaning it will cover the first 2 staircases — was thrown, the only option it has is to sit on top of the 6 width box that was thrown before it. Because the first 4 width box covered the first 4 stairs and then the 6 width box covered the first 6 stairs. And since we are told that the staircases are increasing, it means the more stairs covered means the more higher the box will be at. So, we could just keep track of the maximum height we reached so far, compare that with the height we got for the current box (which we can find by accessing the element on the list of stair height on the index width of the box minus one), we take the higher one and update the maximum height.

• Time complexity: $$$O(n)$$$
• Space complexity: $$$O(1)$$$

n = int(input())
 
hieght_of_strairs = list(map(int, input().split(" ")))
 
m = int(input())
best_attainable_height = -1
 
for i in range(m):
    bw, bh = list(map(int, input().split(" ")))
    curr_h = hieght_of_strairs[bw-1]
    best_attainable_height = max(best_attainable_height, curr_h)
    print(best_attainable_height)
    best_attainable_height += bh

What the question basically asks us is to find the lexicographically smallest permutation of [2...n] that is possible to get by moving only from some already visited city to another unvisited city and we are initially located at city 1.

Key Observations: -> We don't care about the length of the path we take, we only care about its lexicographical order. i.e We can go back and forth without being affected. -> We always choose the smallest reachable city, greedily, as our next destination. -> The number of possible candidates for next move is dynamic as our list can grow and shrink when we visit an new city. -> Heap is ideal for dynamic sized sorted arrays.

First, we build the graph so that we can access neighbors of a city efficiently later. Next, We create a heap(min-heap for our purpose) with 1 inside it. Note that at any point in time all the elements in the heap are possible candidates for our immediate next move. So we pop the smallest city from the heap, add it to the end of our path, mark it as visited and insert all the neighbors of this city to our heap (if a neighbor is already visited we ignore it to avoid cycle). Keep doing this until the heap becomes empty.

Q: What if the currently added neighbors are larger than a city we have left unvisited since we had a better choice back then? A: As I mentioned above, we will go back and visit that city before visiting the new cities. The questions doesn't explicity limit the the number of steps we can take to visit all the cities.

• Time: $$$O(m * log(n))$$$
• Space: $$$O(m)$$$

NB: $$$m >= n$$$ (since the graph is connected), so $$$(m + n <= 2m)$$$

from collections import defaultdict
from heapq import *

n, m = map(int, input().split())
graph = defaultdict(list)

for _ in range(m):
    u, v = map(int, input().split())
    graph[u].append(v)
    graph[v].append(u)

heap, path, visited = [1], [], {1}

while heap:
    current = heappop(heap)
    path.append(current)

    for neighbor in graph[current]:
        if neighbor not in visited:
            heappush(heap, neighbor)
            visited.add(neighbor)

print(*path)