Bună ziua, dragi cititori. Astăzi vă voi spune despre ce cârjă am venit, dezvoltând un mic program în C ++.
După prelegerea privind sortarea fuziunii. Așteptam o sarcină interesantă. Permiteți-mi să citez textul problemei, sper că nimeni nu va obiecta.
Prima linie de intrare cuprinde un număr n (1 ≤ n ≤ 100000), al doilea - matricea A [1 ... n], conținând numărul natural nu depășește 1000000000. necesară pentru a contoriza numărul de perechi de indici 1 ≤ i A [j].
Aproximativ, trebuie să găsim numărul de inversiuni din matrice. Implementarea naivă este foarte simplă. Comparați toate perechile de numere din matrice, numărați numărul de inversiuni. A-la, deci:
Acest cod este probabil bun. Este de înțeles pentru oricine. Chiar și juniorul. Dar există o problemă. Într-o astfel de implementare a algoritmului, asimptotica timpului O (n * n).
Firește, în cursul dedicat algoritmilor și structurilor de date, un astfel de cod nu a trecut (testul a eșuat în timp). Avem nevoie de un algoritm care să funcționeze cel puțin O (n * log (n)).
De când tocmai am trecut o prelegere despre sortare cu ajutorul fuzionării, m-am gândit că ea a fost implicată cumva în asta. Și adevărul este: există un algoritm standard pentru a găsi numărul de inversiuni într-o matrice pentru O (n * log (n)).
Fără ezitare, am găsit o descriere a algoritmului și l-am implementat în C ++. Am aruncat codul pe site pentru verificare automata - codul cade. Soluție nevalidă la cel de-al șaselea set de date.
În sine, nu am nici o îndoială, și, prin urmare, imediat gândit că eroarea undeva în codul meu. Cu toate acestea, acest lucru nu este absolut deloc teribil: la urma urmei, am avut deja o implementare naivă a problemei în buzunar, așa că pot găsi rapid problema.
Scriu un simplu generator care generează matrice aleatoare. Pentru fiecare dintre ele numesc de două ori numărul de inversiuni: folosind un algoritm naiv și folosind un algoritm folosind sortarea fuziunii.
Încep 1000 de iterații, las să beau ceai. Vin - văd că toate testele au trecut cu succes. Aici am fost deja nedumerit: este greu să faci o greșeală într-o implementare naivă, dar se pare că încă am făcut o greșeală în implementarea normală.
M-am dus pe Google, caut implementările existente ale algoritmului. Aparent, această sarcină este foarte frecventă în cursurile de algoritmi. Am găsit cel puțin 5 implementări diferite pentru a găsi numărul de inversiuni din matrice. Este demn de remarcat faptul că toți au căzut pe cel de-al 6-lea set de date.
Am crezut deja că a fost o greșeală în test. Îi scriu creatorilor cursului, aflu că greșeala este de partea mea: există deja oameni care au rezolvat această problemă.
Atunci am fost nedumerit de ce să fac. Implementarea naivă este extrem de simplă, pentru a face o greșeală. Nu am testul de intrare: nu se poate, de asemenea, se dovedește că pentru a detecta eroarea.
Și apoi mi-a dat seama: poate cineva din Rusia scrie ceva despre asta (obișnuiau să caut informații numai în engleză). Se pare că există unele informații în ÎF.
Eu, fără să mă gândesc de două ori, conduceți acest test. Și ce văd? Un răspuns negativ (acest lucru este evident absurd). Și apoi înțeleg toată prostia mea. Am calculat numărul de inversiuni și am adăugat rezultatul la int.
De ce este această prostie? Numărul maxim de inversiuni atinge când matricea de intrări este ordonată în ordine descrescătoare. Numărul de inversiuni în acest caz este de 100.000 * 99999/2 = 4.999.950.000 - aproape 5 miliarde. Și int avem 2,147,483,647. Aici aici este problema.
Misiunea mea a fost că nu m-am gândit imediat la rezultat. Nici măcar nu m-am gândit la posibilitatea de a trece peste. La urma urmei, datele pe care le-am testat, astfel de probleme nu au fost nici măcar apropiate. După cum se spune, trebuie să testați programul pe toate datele de intrare posibile.
Alte intrări din această coloană: