In the same section, there’s a link to a Capture the Flag. This CTF consists of challenges in 5 different categories and for each challenge there’s a score and the estimated time (in minutes) for solving it. R-Boy is really good in WEB, so he can solve those challenges in half the estimated time, but he needs twice the time to solve BINARY challenges. The CTF lasts only 24 hours. Can you help R-Boy choose which challenges to solve to achieve the best score possible – and win the prize? The IDs of the challenges to choose, sorted by ETA descending, will reveal you the prize
The challenge provide us a .csv file with the list of challenge with the ids, categories, scores and ETAs:
ChallengeID Category Score ETA
N binary 100 35
p binary 200 55
q binary 300 85
I binary 500 140
j binary 1000 125
V coding 100 25
U coding 200 45
i coding 300 95
B coding 500 150
0 coding 1000 180
6 crypto 100 35
R crypto 200 40
F crypto 300 60
e crypto 500 110
f crypto 1000 200
x miscellaneous 100 20
J miscellaneous 200 5
A miscellaneous 300 100
M miscellaneous 500 80
P miscellaneous 1000 160
t web 100 30
Z web 200 70
8 web 300 50
Q web 500 100
D web 1000 90
The problem is a simple 0/1 knapsack problem, where we have a knapsack of capacity 1440 (minutes).
We only have to pay attention as we have to consider only half of the time for the web challenges and double of the time for the binary challenges.
To solve the problem we can simple use an online solver like this
The challenge that provide us the best solution are (already sorted):
ChallengeID Category Score ETA
f crypto 1000 200
0 coding 1000 180
P miscellaneous 1000 160
j binary 1000 125
e crypto 500 110
Q web 500 100
i coding 300 95
D web 1000 90
M miscellaneous 500 80
Z web 200 70
F crypto 300 60
8 web 300 50
U coding 200 45
R crypto 200 40
t web 100 30
V coding 100 25
x miscellaneous 100 20
J miscellaneous 200 5
The list of choosen IDs, sorted by ETA desc, are f0PjeQiDMZF8URtVxJ so the flag is {FLG:f0PjeQiDMZF8URtVxJ}