Pentru $100p$ problema se rezolva liniar. Se inserează melodiile lui Vasile într-un hash. Apoi se generează cele M melodii alei lui DJ Random, având grija ca înmulţirea trebuie făcută pe long long, iar operaţia modulo trebuie aplicata o singura data, pentru ca este foarte costisitoare din punct de vedere al timpului, iar pentru $10.000.000$ de operaţii, o constanta de 3 creste timpul. Apoi, pentru o melodie de-a lui DJ Random, se cauta în hash, iar dacă aceasta exista, se incrementează soluţia, iar acea melodie se scoate din hash, pentru a nu fi adunata de mai multe ori la soluţie.

Problema se poate rezolva şi folosind o căutare binara, sau folosind set-uri. Aceste implementări ajungeau pana la $70p$.
 
h2. 'Meneaito':problema/meneaito
 
Se observa ca pentru ca un timp sa reprezinte o solutie, atunci pentru fiecare coloana i, 1 < i < N, dansatorul de pe coloana i trebuie sa nu fie pe pozitia i. Astfel, putem marca timpii in care pe o anumita coloana i, pozitia i este ocupata. Mentionam ca nu ne intereseaza cazul in care i < A[i] sau i > B[i]. Pentru celelalte cazuri(unde A[i] <= i <= B[i]), consideram 2 posibilitati:
1) Dansatorul se afla pe pozitia i si se indreapta in jos
2) Dansatorul se afla pe pozitia i si se indreapta in sus
Observam ca pentru fiecare dintre aceste cazuri avem un timp(notat X1 pentru primul caz si X2 pentru al doilea caz) cand evenimentul se produce prima data. Deasemenea observam ca evenimentul(aparitia unui timp care nu poate fi solutie) se produce la un interval dat de timp, notat in continuare Y.
Se vede usor faptul ca:
X1 = i - A[i]
X2 = 2 * (B[i] - i) - (A[i] - i)
Y = 2 * (B[i] - A[i])
Vor aparea astfel ecuatii de forma: T = X1 + K * Y si T = X2 + K * Y, unde T reprezinta un timp ce nu poate constitui o solutie, iar K este un numar natural.
Vom marca aceste ecuatii cu ajutorul unui map care ne va ajuta sa nu avem ecuatii redundante. Astfel pentru fiecare Y, vom tine maxim Y ecuatii.
La fiecare pas la care descoperim o ecuatie noua, eliminam timpii care nu pot constitui o solutie utilizand un algoritm asemanator ciurului lui Eratostene. Pentru a gasi solutia parcurgem toti timpii de la 0 la 200000 si il gasim pe cel mai mic care a ramas nemarcat in urma ciurului

Problema se poate rezolva şi folosind o căutare binara, sau folosind set-uri. Aceste implementări ajungeau pana la $70p$.