Quand on lit le code pour la première fois on voit qu’on va devoir résoudre pour des tableaux de tailles variables, la somme maximale d’une sous-liste connexe. La première idée naturelle, si on ne regarde pas bien les nombres, c’est d’envisager toutes les sous-listes possibles, de calculer leur somme et de garder la meilleure.
On envisage donc assez un vite un code de ce genre :
def solve(A: list[int]) -> tuple[int, int, int]:
m = A[0]
x = 0
y = 1
for i in range(len(A)):
for j in range(i + 1, len(A) + 1):
if sum(A[i:j]) > m:
m = sum(A[i:j])
x = i
y = j
return m, x, y
Mais très vite la complexité explose et on ne peut pas faire ça pour les grands tableaux. En effet, il y a $O(len(A)^2)$ sous-listes possibles et chacune d’elle peut faire l’objet d’une somme en $O(len(A))$ dans le pire des cas, ce qui nous donne une complexité totale en $O(len(A)^3)$. Et ici $len(A)$ peut être de l’ordre de $10^6$, ce qui est complètement inenvisageable.
On voit que la solution doit être plus intelligente, les sommes se répètent etc… on cherche donc à revenir à une liste plus petite. 2 choix se présentent à nous, soit enlever un nombre fixe d’éléments soit une partie variable. On ne trouve pas de raison de se ramener à $len(A) - k$ pour un $k$ fixe, pas plus que pour un autre $k$. C’est ça qui fait envisager la récursivité : on peut se ramener à 2 sous-listes quelconques. On va choisir de se ramener à 2 sous-listes de même taille, c’est le plus simple à implémenter et cela ne change rien à la complexité algorithmique.
Maintenant il faut expliciter le lien entre la solution à une taille 2K et à une taille K.
Une solution est donc une sous-liste où tous les éléments se suivent.
Le mieux pour raisonner dans de tels cas est de faire un dessin.
Une solution d’un tableau de taille 2K est soit entièrement dans la partie gauche, soit entièrement dans la partie droite, soit elle passe par le centre.
La partie gauche et la partie droite -> ce sera un appel à notre fonction récursive.
Réfléchissons à la partie qui passe par le centre : elle doit être constituée d’une partie de la gauche et d’une partie de la droite. On cherche à maximiser la somme de cette partie, on doit donc maximiser la partie de gauche et la partie de droite. Cela se fait en $O(K)$ : on part du centre et on ajoute les éléments un par un à gauche, on garde la meilleure somme obtenue, on fait pareil à droite et cela nous donne la meilleure somme pour la partie qui passe par le centre.
Notre condition d’arrêt est assez simple : quand on a une liste de 2 éléments, on peut calculer la somme maximale en $O(1)$ et c’est notre cas de base. En réalité on peut le faire pour une liste de 1 élément aussi, mais cela me semblait moins logique donc je ne l’ai pas choisi - ce qui restreint ma solution à des tableaux de taille 2^n - ce qui fonctionne pour le chall.
Il reste à comparer les 3 solutions : la partie gauche, la partie droite et la partie qui passe par le centre pour avoir le résultat final !
Le plus simple pour comprendre reste un bout de code, attention à ne pas se perdre dans les indices…
def solve(A: list[int]) -> tuple[int, int, int]:
"""
Fonction récursive pour trouver la somme maximale d'une sous-liste connexe dans une liste d'entiers.
"""
# Cas de base : 2 éléments
if len(A) == 2:
m_base = max(A[0], A[1], A[0] + A[1])
if m_base == A[0]+A[1]:
return m_base, 0, 2
elif m_base == A[0]:
return m_base, 0, 1
else:
return m_base, 1, 2
index_of_mid = len(A) // 2
# Première partie : résoudre la partie gauche et la partie droite
m1, x1, y1 = solve(A[0:index_of_mid])
m2, x2, y2 = solve(A[index_of_mid:len(A)])
x2 += index_of_mid
y2 += index_of_mid
# Si la solution n'est pas dans la partie gauche ou la partie droite, elle contient un bout des 2 donc le centre
# On peut faire une expansion à partir du centre vers la gauche et vers la droite pour trouver la solution maximale qui contient le centre
# Commençons à gauche par le suffixe maximal qui se termine à index_of_mid -1 (dernier élément de la partie gauche)
s_expansion_of_suffix = A[index_of_mid - 1] # Pris car il nous faut au minimum un élément de gauche
current_sum = A[index_of_mid - 1]
x1_expansion_of_suffix = index_of_mid - 1
for i in range(index_of_mid - 2, -1, -1): # On a déjà pris index_of_mid - 1
current_sum += A[i]
if current_sum > s_expansion_of_suffix:
s_expansion_of_suffix = current_sum
x1_expansion_of_suffix = i
# On fait la droite maintenant, tout idem mais miroir
s_expansion_of_prefix = A[index_of_mid]
current_sum = A[index_of_mid]
y2_expansion_of_prefix = index_of_mid + 1
for i in range(index_of_mid + 1, len(A)):
current_sum += A[i]
if current_sum > s_expansion_of_prefix:
s_expansion_of_prefix = current_sum
y2_expansion_of_prefix = i + 1
m_expansion_crossing = s_expansion_of_suffix + s_expansion_of_prefix # Le maximum de notre partie qui passe par le centre
x1_expansion_crossing = x1_expansion_of_suffix
y2_expansion_crossing = y2_expansion_of_prefix
if m1 >= m2 and m1 >= m_expansion_crossing: # Si la solution est dans la partie gauche
return m1, x1, y1
elif m2 >= m1 and m2 >= m_expansion_crossing: # Si la solution est dans la partie droite
return m2, x2, y2
else:
return m_expansion_crossing, x1_expansion_crossing, y2_expansion_crossing # Sinon la solution est la partie construite qui passe par le centre
Finalement on écrit le code pour s’interfacer avec le conteneur, ce qui permet d’utiliser la librairie pwn que je recommande vivement.
import random
import re
from pwn import remote
from solution import solve
if __name__ == "__main__":
HOST = "localhost"
PORT = 4000
io = remote(HOST, PORT)
while True:
line = io.recvline().decode()
if "seed" not in line:
print(line.strip())
continue
m = re.search(r'seed, n, N\) = \((\d+), (\d+), (\d+)\)', line)
seed, n, N = map(int, m.groups())
print(f"{(seed, n, N) = }")
random.seed(seed)
A = [random.randrange(-n, n) for _ in range(2**N)]
# print(A)
m, i, j = solve(A)
print(f"La somme maximale est {m} for A[{i}:{j}]")
io.recvuntil(b">>> i =")
io.sendline(str(i).encode())
io.recvuntil(b">>> j =")
io.sendline(str(j).encode())
Le script crash à l’étape du flag et on l’a :
(seed, n, N) = (???, 100000, 22)
La somme maximale est ??? for A[???:???]
FCSC{b3a6e5e45a7efcbefe1757d689ad20c1b1ff886eced11b87b74bb25175efad05}
Pour des solutions plus optimisées encore, il existe un algorithme en $O(n)$ pour ce problème, il est pas plus compliqué que celui-ci à comprendre et plus simple à implémenter, un peu plus dur à imaginer seul par contre. Il s’agot de l’algorithme de Kadane
Enjoy !