Rating:

# Left or right? (19 solves, 217 points)
by y011d4



nc challs.m0lecon.it 5886

Authors: Drago_1729, matpro, mr96



Hello hacker! This challenge will test your programming skills.
I will give you some strings made up only by L and R. You start at a point O, L means moving to the left by 1 unit, R means moving to the right by 1 unit.
Your objective is to concatenate ALL these strings such that the leftmost point that you reach during your path is as near as possible to O.
Let's call this point P. What is the distance between O and P?

The first line of the input contains a number N.
The following N lines contain a string made up only of the characters L and R.
In every testcase 0<N<=150 and the sum of the lengths of the given strings is at most 100000.
You must answer to 200 testcases to get the flag! Time limit is one second for each test.


Examples are:


4
LRLRLLRRRLLRLLRRRRLR
LRLRRLRLLRLLLRR
LRRLRLLLLLLLLLLRLRRLLLLRRLLLRRRL
LLLRLRLLR


First of all, we need to hold not all "LR" but:
- the leftmost place from the current position (call it lr_diff_max)
- the final place from the current position (call it last_pos)

for each string, where the left side is positive.
For example above:


lr_diff_max: 2, 3, 12, 3
last_pos: -2, 1, 10, 1


Note that lr_diff_max >= last_pos.

In the following, we consider the case last_pos <= 0 and the other case separately.

#### last_pos <= 0
In this case, the last position will be on the right or the same. This is higher priority than the other case.

For each choice, we should pick the case of lr_diff_max <= ans (ans means the current answer for each task) because it won't affect the answer. If there are no such cases, choose the smallest lr_diff_max case in order to minimize the ans

#### last_pos > 0
After the all last_pos <= 0 cases are chosen, we go to this case.
Considering the fact that the final position (call it all_last_pos) after all are selected doesn't change, we should pick the case of maximum lr_diff_max - last_pos in each choice, because naively the final ans equals to the final lr_diff_max - last_pos + all_last_pos.

The all script is as follow:

python
import re
from hashlib import sha256
from itertools import product

import numpy as np
from pwn import *

_r = remote("challs.m0lecon.it", 5886)
ret = _r.recvline().strip().decode()
prefix, suffix = re.findall(
r"Give me a string starting with (.+) such that its sha256sum ends in (.+).", ret
)[0]

for i_list in product(list(range(32, 128)), repeat=4):
c_list = list(map(chr, i_list))
tmp = prefix + "".join(c_list)
tmp_hash = sha256(tmp.encode()).hexdigest()
if tmp_hash[-len(suffix):] == suffix:
print("found!")
_r.sendline(tmp)
break

_r.sendlineafter("Time limit is one second for each test.\n", "")

for epoch in range(200):
print(epoch)
N = int(_r.recvline().strip())
steps_list = []
for _ in range(N):
steps_list.append(_r.recvline().strip().decode())
lr_diff_max_list_0 = []
lr_diff_max_list_1 = []
last_pos_list_0 = []
last_pos_list_1 = []
for steps in steps_list:
lr_diff_max = 0
tmp = 0
for step in steps:
if step == "L":
tmp += 1
else:
tmp -= 1
if tmp > lr_diff_max:
lr_diff_max = tmp
if tmp <= 0:
lr_diff_max_list_0.append(lr_diff_max)
last_pos_list_0.append(tmp)
else:
lr_diff_max_list_1.append(lr_diff_max)
last_pos_list_1.append(tmp)

lr_diff_max_list_0 = np.array(lr_diff_max_list_0)
lr_diff_max_list_1 = np.array(lr_diff_max_list_1)
last_pos_list_0 = np.array(last_pos_list_0)
last_pos_list_1 = np.array(last_pos_list_1)

ans = 0
# case0: last_pos <= 0
n_0 = len(lr_diff_max_list_0)
used = [False] * n_0
current_pos = 0

for _ in range(n_0):
found = None
for i in range(n_0):
if not used[i] and lr_diff_max_list_0[i] <= current_pos:
found = i
break
if found is None:
pos_min = 10 ** 10
for i in range(n_0):
if not used[i] and lr_diff_max_list_0[i] <= pos_min:
pos_min = lr_diff_max_list_0[i]
found = i
assert found is not None
used[found] = True
ans = max(ans, current_pos + lr_diff_max_list_0[found])
current_pos += last_pos_list_0[found]

# case1: last_pos > 0
argidx = np.argsort(lr_diff_max_list_1 - last_pos_list_1)[::-1]
for idx in argidx:
ans = max(ans, current_pos + lr_diff_max_list_1[idx])
current_pos += last_pos_list_1[idx]
_r.sendline(str(ans))
if "Yay" not in _r.recvline().strip().decode():
break
print(_r.recvall())


ptm{45_r16h7_45_p0551bl3}

Original writeup (https://wrecktheline.com/writeups/m0lecon-2021/#left_or_right_writeup).