👨‍💻
CTFs
HomePlaygroundOSCPBuy Me a Flag 🚩
  • 🚩Zeyu's CTF Writeups
  • Home
  • Playground
  • OSCP
  • My Challenges
    • SEETF 2023
    • The InfoSecurity Challenge 2022
    • SEETF 2022
    • Cyber League Major 1
    • STANDCON CTF 2021
      • Space Station
      • Star Cereal
      • Star Cereal 2
      • Mission Control
      • Rocket Science
      • Space University of Interior Design
      • Rocket Ship Academy
      • Space Noise
  • 2023
    • DEF CON CTF 2023 Qualifiers
    • hxp CTF
      • true_web_assembly
    • HackTM CTF Qualifiers
      • Crocodilu
      • secrets
      • Hades
  • 2022
    • niteCTF 2022
      • Undocumented js-api
      • js-api
    • STACK the Flags 2022
      • Secret of Meow Olympurr
      • The Blacksmith
      • GutHib Actions
      • Electrogrid
      • BeautyCare
    • LakeCTF Qualifiers
      • People
      • Clob-Mate
      • So What? Revenge
    • The InfoSecurity Challenge 2022
      • Level 1 - Slay The Dragon
      • Level 2 - Leaky Matrices
      • Level 3 - PATIENT0
      • Level 4B - CloudyNekos
      • Level 5B - PALINDROME's Secret (Author Writeup)
    • BalsnCTF 2022
      • 2linenodejs
      • Health Check
    • BSidesTLV 2022 CTF
      • Smuggler
      • Wild DevTools
      • Tropical API
    • Grey Cat The Flag 2022
    • DEF CON CTF 2022 Qualifiers
    • Securinets CTF Finals 2022
      • StrUggLe
      • XwaSS ftw?
      • Strong
      • Artist
    • NahamCon CTF 2022
      • Flaskmetal Alchemist
      • Hacker TS
      • Two For One
      • Deafcon
      • OTP Vault
      • Click Me
      • Geezip
      • Ostrich
      • No Space Between Us
    • Securinets CTF Quals 2022
      • Document-Converter
      • PlanetSheet
      • NarutoKeeper
    • CTF.SG CTF
      • Asuna Waffles
      • Senpai
      • We know this all too well
      • Don't Touch My Flag
      • Wildest Dreams Part 2
      • Chopsticks
    • YaCTF 2022
      • Shiba
      • Flag Market
      • Pasteless
      • Secretive
      • MetaPDF
      • Crackme
    • DiceCTF 2022
      • knock-knock
      • blazingfast
    • TetCTF 2022
      • 2X-Service
      • Animals
      • Ezflag Level 1
  • 2021
    • hxp CTF 2021
    • HTX Investigator's Challenge 2021
    • Metasploit Community CTF
    • MetaCTF CyberGames
      • Look, if you had one shot
      • Custom Blog
      • Yummy Vegetables
      • Ransomware Patch
      • I Hate Python
      • Interception
    • CyberSecurityRumble CTF
      • Lukas App
      • Finance Calculat0r 2021
      • Personal Encryptor with Nonbreakable Inforation-theoretic Security
      • Enterprice File Sharing
      • Payback
      • Stonks Street Journal
    • The InfoSecurity Challenge (TISC) 2021
      • Level 4 - The Magician's Den
      • Level 3 - Needle in a Greystack
      • Level 2 - Dee Na Saw as a need
      • Level 1 - Scratching the Surface
    • SPbCTF's Student CTF Quals
      • 31 Line PHP
      • BLT
      • CatStep
    • Asian Cyber Security Challenge (ACSC) 2021
      • Cowsay As A Service
      • Favorite Emojis
      • Baby Developer
      • API
      • RSA Stream
      • Filtered
      • NYONG Coin
    • CSAW CTF Qualification Round 2021
      • Save the Tristate
      • securinotes
      • no pass needed
      • Gatekeeping
      • Ninja
    • YauzaCTF 2021
      • Yauzacraft Pt. 2
      • Yauzabomber
      • RISC 8bit CPU
      • ARC6969 Pt. 1
      • ARC6969 Pt. 2
      • Back in 1986 - User
      • Lorem-Ipsum
    • InCTF 2021
      • Notepad 1 - Snakehole's Secret
      • RaaS
      • MD Notes
      • Shell Boi
      • Listen
      • Ermittlung
      • Alpha Pie
    • UIUCTF 2021
      • pwnies_please
      • yana
      • ponydb
      • SUPER
      • Q-Rious Transmissions
      • capture the :flag:
      • back_to_basics
      • buy_buy_buy
    • Google CTF 2021
      • CPP
      • Filestore
    • TyphoonCon CTF 2021
      • Clubmouse
      • Impasse
    • DSTA BrainHack CDDC21
      • File It Away (Pwn)
      • Linux Rules the World! (Linux)
      • Going Active (Reconnaissance)
      • Behind the Mask (Windows)
      • Web Takedown Episode 2 (Web)
      • Break it Down (Crypto)
    • BCACTF 2.0
      • L10N Poll
      • Challenge Checker
      • Discrete Mathematics
      • Advanced Math Analysis
      • Math Analysis
      • American Literature
      • More Than Meets the Eye
      • 􃗁􌲔􇺟􊸉􁫞􄺷􄧻􃄏􊸉
    • Zh3ro CTF V2
      • Chaos
      • Twist and Shout
      • 1n_jection
      • alice_bob_dave
      • Baby SSRF
      • bxxs
      • Sparta
    • Pwn2Win CTF 2021
      • C'mon See My Vulns
      • Illusion
    • NorzhCTF 2021
      • Leet Computer
      • Secure Auth v0
      • Triskel 3: Dead End
      • Triskel 2: Going In
      • Triskel 1: First Contact
      • Discovery
    • DawgCTF 2021
      • Bofit
      • Jellyspotters
      • No Step On Snek
      • Back to the Lab 2
      • MDL Considered Harmful
      • Really Secure Algorithm
      • The Obligatory RSA Challenge
      • Trash Chain
      • What the Flip?!
      • Back to the Lab 1
      • Back to the Lab 3
      • Dr. Hrabowski's Great Adventure
      • Just a Comment
      • Baby's First Modulation
      • Two Truths and a Fib
    • UMDCTF 2021
      • Advantageous Adventures
      • Roy's Randomness
      • Whose Base Is It Anyway
      • Cards Galore
      • Pretty Dumb File
      • Minetest
      • Donnie Docker
      • Subway
      • Jump Not Easy
      • To Be XOR Not To Be
      • Office Secrets
      • L33t M4th
      • Bomb 2 - Mix Up
      • Jay
    • Midnight Sun CTF 2021
      • Corporate MFA
      • Gurkburk
      • Backups
    • picoCTF 2021
      • It Is My Birthday (100)
      • Super Serial (130)
      • Most Cookies (150)
      • Startup Company (180)
      • X marks the spot (250)
      • Web Gauntlet (170 + 300)
      • Easy Peasy (40)
      • Mini RSA (70)
      • Dachshund Attacks (80)
      • No Padding, No Problem (90)
      • Trivial Flag Transfer Protocol (90)
      • Wireshark twoo twooo two twoo... (100)
      • Disk, Disk, Sleuth! (110 + 130)
      • Stonks (20)
    • DSO-NUS CTF 2021
      • Insecure (100)
      • Easy SQL (200)
Powered by GitBook
On this page
  • Jay 1
  • Jay 2

Was this helpful?

  1. 2021
  2. UMDCTF 2021

Jay

Jay 1

I've been stuck in this room for some time now. They locked me in here and told
me the only way I can leave is if I solve their problem within five seconds.
I've tried so much, but my algorithm keeps going over the time. Can you help me?

What I have to do is find the maximum contiguous sub-array within this array of
numbers. They keep telling me my algorithm isn't efficient enough! If you can
send me the indices of this array, I might live to see another day.

Format: "sum, i, j" Example: 103, 345, 455

sum = the maximum contiguous sum
i = start index of sub-array
j = end index of sub-array

Press Enter to get the arr

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.

from pwn import *

conn = remote('chals3.umdctf.io', 6001)

conn.send('\n')
conn.recvuntil('[')
data = '[' + conn.recvuntil(']').decode()
print(data)

arr = eval(data)

max_so_far = 0
max_end_here = 0
curr_index = 0
curr_i = 0
i = 0
j = 0

while curr_index < len(arr):
    max_end_here += arr[curr_index]
    if max_end_here > max_so_far:
        max_so_far = max_end_here
        i = curr_i
        j = curr_index

    if max_end_here < 0:
        max_end_here = 0
        curr_i = curr_index + 1

    curr_index += 1

print(f"{max_so_far}, {i}, {j}")

conn.send(f"{max_so_far}, {i}, {j}")
conn.recvline()
conn.recvline()
print(conn.recvline())
print(conn.recv())

conn.close()

Jay 2

Welp that didn't work. As soon as they took me out of this place, they dragged me
to another room and told me to solve another stupid puzzle. You think you could help
me with this one as well? This was all they gave me:

"You are given a 2-dimensional array of values for an image. Find the
brightest subregion of the image (the bigger the number, the brighter). A subregion (rectangular) can range from one pixel to the whole
image. You can assume the image has the same width and height."

They also gave me an example for clarification:
|-----|-----|-----|-----|-----|
|     |     |     |     |     |
|  6  | -5  | -7  |  4  | -4  |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
|     |     |     |     |     |
| -9  |  3  | -6  |  5  |  2  |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
|     |     |     |     |     |
| -10 |  4  |  7  | -6  |  3  |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|
|     |     |     |     |     |
| -8  |  9  | -3  |  3  | -7  |
|     |     |     |     |     |
|-----|-----|-----|-----|-----|

Format: "sum, row_start, row_end, col_start, col_end" Example: 17, 2, 3, 1, 2

sum = the maximum subregion sum
row_start = row index of top left
row_end = row index of bottom right
col_start = col index of top left
col_end = col index of bottom right

Press Enter to get the 2D array

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,

from pwn import *

def longest_contiguous_subarray(arr):

    max_so_far = 0
    max_end_here = 0
    curr_index = 0
    curr_i = 0
    i = 0
    j = 0

    while curr_index < len(arr):
        max_end_here += arr[curr_index]
        if max_end_here > max_so_far:
            max_so_far = max_end_here
            i = curr_i
            j = curr_index

        if max_end_here < 0:
            max_end_here = 0
            curr_i = curr_index + 1

        curr_index += 1

    return max_so_far, i, j

conn = remote('chals3.umdctf.io', 6002)

conn.send('\n')
conn.recvuntil('[')
data = '[' + conn.recvuntil(']]').decode()
#print(data)

arr = eval(data)

"""
arr = [
    [6, -5, -7, 4, -4],
    [-9, 3, -6, 5, 2],
    [-10, 4, 7, -6, 3],
    [-8, 9, -3, 3, -7],
]
"""

max_sum = 0
max_row_start = 0
max_row_end = 0
max_col_start = 0
max_col_end = 0


col_start = 0
while col_start < len(arr[0]):

    new_arr = [0 for i in range(len(arr))]

    col_end = col_start
    while col_end < len(arr[0]):

        for i in range(len(arr)):
            # Note that we can only add the entire subrow, since the subregion must be rectangular
            # Each element in the new array represents the sum of a subrow
            new_arr[i] += arr[i][col_end]
        # print(new_arr)

        subarray_sum, row_start, row_end = longest_contiguous_subarray(new_arr)
        if subarray_sum > max_sum:
            max_sum = subarray_sum
            max_row_start = row_start
            max_row_end = row_end
            max_col_start = col_start
            max_col_end = col_end

        col_end += 1

    col_start += 1


conn.recvline()
conn.recvline()
print(f"{max_sum}, {max_row_start}, {max_row_end}, {max_col_start}, {max_col_end}")
conn.send(f"{max_sum}, {max_row_start}, {max_row_end}, {max_col_start}, {max_col_end}")
print(conn.recv())

conn.close()
PreviousBomb 2 - Mix UpNextMidnight Sun CTF 2021

Last updated 3 years ago

Was this helpful?