Suma 2023 din termeni distincți

Metoda de rezolvare

Se folosește un vector caracteristic sp, cu elementele numerotate de la 0 la 2023. Elementul sp[s] are valoarea 1 dacă suma s se poate obține ca sumă de termeni distincți dintre numerele citite până în acel moment și valoarea 0 în caz contrar. Suma 0 se obține fără niciun termen, deci inițial sp[0] = 1, iar celelalte elemente sunt 0.

Numerele se citesc din fișier unul câte unul și nu se memorează. Un număr x mai mare decât 2023 nu poate face parte dintr-o sumă egală cu 2023 și se ignoră.

Pentru un număr x ≤ 2023, fiecare sumă s obținută deja produce o sumă nouă, s + x. Se parcurg sumele s de la 2023 − x până la 0, în ordine descrescătoare, iar pentru fiecare s cu sp[s] = 1 se atribuie sp[s + x] = 1. Sumele mai mari decât 2023 nu interesează, de aceea s nu depășește 2023 − x.

Parcurgerea se face de la dreapta la stânga pentru ca x să intre cel mult o dată în fiecare sumă. Elementul sp[s + x] modificat la un pas are indicele mai mare decât toate sumele încă neparcurse, deci el nu mai este folosit la citirea aceluiași x.

Citirea se oprește la sfârșitul fișierului sau imediat ce sp[2023] devine 1. La sfârșit se afișează DA dacă sp[2023] = 1 și NU în caz contrar.

Justificarea eficienței

Numerele din fișier sunt distincte, deci cel mult 2023 dintre ele au valori din intervalul [1, 2023]. Numai pentru acestea se parcurge vectorul sp, iar o parcurgere are cel mult 2023 de pași. Numărul total de operații pentru actualizarea vectorului este deci cel mult 2023 · 2023, adică aproximativ 4 · 10⁶, oricât de mare ar fi fișierul. Restul numerelor sunt doar citite și comparate cu 2023, câte o operație pentru fiecare.

Timpul de executare este de ordinul O(n + S²), unde n este numărul de valori din fișier, iar S = 2023 este suma cerută. Algoritmul este liniar în raport cu numărul de valori citite.

Memoria folosită se reduce la vectorul sp, cu 2024 de elemente, fiindcă numerele din fișier nu sunt memorate.

O rezolvare care ar genera toate submulțimile șirului ar avea timpul de executare de ordinul 2ⁿ. Pentru n = 10⁶ numărul de submulțimi este imposibil de parcurs în timp util.