Dragons Flight | Coding

🐉 Dragons Flight — Write-Up | Cyber Apocalypse 2025

Details
URL	[Hack The Box :: Dragons Flight
Difficulty	Easy
Team Rank	541 / 8129
CTF Date	26 Mar, 13:00

📖 Challenge Summary

In the mystical realm of the Floating Isles, dragons navigate the skies between sacred sanctuaries. But turbulent wind currents across segmented paths can make or break their flight. You, the Dragon Flight Master, must simulate their journey by adapting to wind shifts and answering critical pathfinding queries in real-time.

🧠 Problem Rules

You are given:

• A list of N wind segments, each representing a stretch of the sky.
  • Positive values = tailwinds (boost)
  • Negative values = headwinds (resistance)
• A sequence of Q operations:
  • U i x: Update the wind effect at segment i to value x
  • Q l r: Query the maximum contiguous subarray sum (most favourable continuous stretch) from index l to r (inclusive, 1-based)

💻 Python Solution

We use Kadane’s Algorithm to compute the maximum subarray sum for each query and perform updates directly on the array.

def max_subarray_sum(arr):
    max_sum = float('-inf')
    current = 0
    for val in arr:
        current = max(val, current + val)
        max_sum = max(max_sum, current)
    return max_sum

# Read input
N, Q = map(int, input().split())
arr = list(map(int, input().split()))

for _ in range(Q):
    parts = input().split()
    if parts[0] == 'U':
        i = int(parts[1]) - 1
        x = int(parts[2])
        arr[i] = x
    elif parts[0] == 'Q':
        l = int(parts[1]) - 1
        r = int(parts[2])
        print(max_subarray_sum(arr[l:r]))

🧪 Example Flight Simulation

Input

6 6
-10 -7 -1 -4 0 -5
Q 3 3
U 2 9
Q 6 6
U 1 -1
Q 6 6
U 5 -9

Output

-1
-5
-5

Step-by-Step Breakdown:

1. Initial Array:
   [-10, -7, -1, -4, 0, -5]

2. Q 3 3
   → Segment 3 = -1
   → ➤ Output: -1

3. U 2 9
   → Update segment 2 to 9
   → New array: [-10, 9, -1, -4, 0, -5]

4. Q 6 6
   → Segment 6 = -5
   → ➤ Output: -5

5. U 1 -1
   → Update segment 1 to -1
   → New array: [-1, 9, -1, -4, 0, -5]

6. Q 6 6
   → Segment 6 = -5
   → ➤ Output: -5

7. U 5 -9
   → Update segment 5 to -9
   → Final array: [-1, 9, -1, -4, -9, -5]

🔮 Final Challenge Input

Input

7 5
7 4 0 -4 -6 3 2
U 7 4
Q 4 7
U 1 3
U 3 4
U 1 6

Operation Breakdown

1. Initial Array: [7, 4, 0, -4, -6, 3, 2]
2. U 7 4 → Array becomes: [7, 4, 0, -4, -6, 3, 4]
3. Q 4 7 → Query [ -4, -6, 3, 4 ] → max contiguous sum = 7
4. U 1 3 → Update index 1 to 3
5. U 3 4 → Update index 3 to 4
6. U 1 6 → Update index 1 to 6

Output

7

🏁 Flag

HTB{DR4G0N_FL1GHT_5TR33_5907f8463bb8ab2291f1cc49c699d816}