Jay

Jay 1

1
I've been stuck in this room for some time now. They locked me in here and told
2
me the only way I can leave is if I solve their problem within five seconds.
3
I've tried so much, but my algorithm keeps going over the time. Can you help me?
4
​
5
What I have to do is find the maximum contiguous sub-array within this array of
6
numbers. They keep telling me my algorithm isn't efficient enough! If you can
7
send me the indices of this array, I might live to see another day.
8
​
9
Format: "sum, i, j" Example: 103, 345, 455
10
​
11
sum = the maximum contiguous sum
12
i = start index of sub-array
13
j = end index of sub-array
14
​
15
Press Enter to get the arr
Copied!
This is the maximum contiguous subarray algorithm. Luckily, I had experience with this algorithm (yay competitive programming!). The only twist is we had to output the start and end indices.
1
from pwn import *
2
​
3
conn = remote('chals3.umdctf.io', 6001)
4
​
5
conn.send('\n')
6
conn.recvuntil('[')
7
data = '[' + conn.recvuntil(']').decode()
8
print(data)
9
​
10
arr = eval(data)
11
​
12
max_so_far = 0
13
max_end_here = 0
14
curr_index = 0
15
curr_i = 0
16
i = 0
17
j = 0
18
​
19
while curr_index < len(arr):
20
max_end_here += arr[curr_index]
21
if max_end_here > max_so_far:
22
max_so_far = max_end_here
23
i = curr_i
24
j = curr_index
25
​
26
if max_end_here < 0:
27
max_end_here = 0
28
curr_i = curr_index + 1
29
​
30
curr_index += 1
31
​
32
print(f"{max_so_far}, {i}, {j}")
33
​
34
conn.send(f"{max_so_far}, {i}, {j}")
35
conn.recvline()
36
conn.recvline()
37
print(conn.recvline())
38
print(conn.recv())
39
​
40
conn.close()
Copied!

Jay 2

1
Welp that didn't work. As soon as they took me out of this place, they dragged me
2
to another room and told me to solve another stupid puzzle. You think you could help
3
me with this one as well? This was all they gave me:
4
​
5
"You are given a 2-dimensional array of values for an image. Find the
6
brightest subregion of the image (the bigger the number, the brighter). A subregion (rectangular) can range from one pixel to the whole
7
image. You can assume the image has the same width and height."
8
​
9
They also gave me an example for clarification:
10
|-----|-----|-----|-----|-----|
11
| | | | | |
12
| 6 | -5 | -7 | 4 | -4 |
13
| | | | | |
14
|-----|-----|-----|-----|-----|
15
| | | | | |
16
| -9 | 3 | -6 | 5 | 2 |
17
| | | | | |
18
|-----|-----|-----|-----|-----|
19
| | | | | |
20
| -10 | 4 | 7 | -6 | 3 |
21
| | | | | |
22
|-----|-----|-----|-----|-----|
23
| | | | | |
24
| -8 | 9 | -3 | 3 | -7 |
25
| | | | | |
26
|-----|-----|-----|-----|-----|
27
​
28
Format: "sum, row_start, row_end, col_start, col_end" Example: 17, 2, 3, 1, 2
29
​
30
sum = the maximum subregion sum
31
row_start = row index of top left
32
row_end = row index of bottom right
33
col_start = col index of top left
34
col_end = col index of bottom right
35
​
36
Press Enter to get the 2D array
Copied!
The idea here is to apply the above algorithm for 1D arrays onto the 2D array, by treating the sum of each row of the subarea as an element in the 1D array. So, when finding the maximum contiguous sum of the "1D array", we are finding the optimal row_start and row_end for any combination of col_start and col_end,
1
from pwn import *
2
​
3
def longest_contiguous_subarray(arr):
4
​
5
max_so_far = 0
6
max_end_here = 0
7
curr_index = 0
8
curr_i = 0
9
i = 0
10
j = 0
11
​
12
while curr_index < len(arr):
13
max_end_here += arr[curr_index]
14
if max_end_here > max_so_far:
15
max_so_far = max_end_here
16
i = curr_i
17
j = curr_index
18
​
19
if max_end_here < 0:
20
max_end_here = 0
21
curr_i = curr_index + 1
22
​
23
curr_index += 1
24
​
25
return max_so_far, i, j
26
​
27
conn = remote('chals3.umdctf.io', 6002)
28
​
29
conn.send('\n')
30
conn.recvuntil('[')
31
data = '[' + conn.recvuntil(']]').decode()
32
#print(data)
33
​
34
arr = eval(data)
35
​
36
"""
37
arr = [
38
[6, -5, -7, 4, -4],
39
[-9, 3, -6, 5, 2],
40
[-10, 4, 7, -6, 3],
41
[-8, 9, -3, 3, -7],
42
]
43
"""
44
​
45
max_sum = 0
46
max_row_start = 0
47
max_row_end = 0
48
max_col_start = 0
49
max_col_end = 0
50
​
51
​
52
col_start = 0
53
while col_start < len(arr[0]):
54
​
55
new_arr = [0 for i in range(len(arr))]
56
​
57
col_end = col_start
58
while col_end < len(arr[0]):
59
​
60
for i in range(len(arr)):
61
# Note that we can only add the entire subrow, since the subregion must be rectangular
62
# Each element in the new array represents the sum of a subrow
63
new_arr[i] += arr[i][col_end]
64
# print(new_arr)
65
​
66
subarray_sum, row_start, row_end = longest_contiguous_subarray(new_arr)
67
if subarray_sum > max_sum:
68
max_sum = subarray_sum
69
max_row_start = row_start
70
max_row_end = row_end
71
max_col_start = col_start
72
max_col_end = col_end
73
​
74
col_end += 1
75
​
76
col_start += 1
77
​
78
​
79
conn.recvline()
80
conn.recvline()
81
print(f"{max_sum}, {max_row_start}, {max_row_end}, {max_col_start}, {max_col_end}")
82
conn.send(f"{max_sum}, {max_row_start}, {max_row_end}, {max_col_start}, {max_col_end}")
83
print(conn.recv())
84
​
85
conn.close()
Copied!
Last modified 7mo ago
Copy link
Contents
Jay 1
Jay 2