Wrong Answer în C++: cum găsești un contraexemplu

Wrong Answer înseamnă că rezultatul produs nu corespunde cerinței pentru cel puțin un test evaluat. Faptul că exemplul din enunț trece este util, dar nu demonstrează corectitudinea algoritmului. Următorul pas este găsirea celui mai mic caz pe care îl poți explica și pe care soluția greșește.

Verifică întâi contractul

Recitește formatul intrării și ieșirii. Se cer valori sau poziții? Pozițiile încep de la zero sau de la unu? Sunt permise duplicate? La egalitate se cere prima soluție, ultima sau oricare? Un algoritm bun pentru o cerință apropiată poate primi pe bună dreptate un verdict greșit.

Verifică și textele afișate. Mesaje precum „Introduceți n” sunt potrivite într-un program interactiv personal, dar pot încălca formatul unui evaluator care așteaptă doar rezultatul. Urmează exact convenția problemei și nu presupune că orice diferență de formatare este ignorată.

Pentru un maxim inițializat greșit cu zero, intrarea negativă minimală -1 arată eroarea: așteptat -1, obținut 0.Mărește schema ↗

Construiește un test pentru fiecare ramură

Pentru maxim, folosește toate valorile negative. Pentru al doilea maxim distinct, repetă maximul. Pentru cifre, include zero. Pentru secvențe, pune cea mai bună secvență chiar la sfârșit. Pentru matrici, folosește și dimensiuni diferite, dacă sunt permise.

Un test trebuie să aibă un răspuns pe care îl poți calcula independent. Dacă nu știi răspunsul așteptat, o ieșire diferită de intuiție nu este încă dovada unui bug. Scrie calculul manual lângă intrare.

Micșorează cazul care eșuează

Dacă greșeala apare pe 100 de valori, elimină porțiuni păstrând diferența dintre program și răspunsul corect. Continuă până când rămân câteva valori. De exemplu, un bug la ștergerea elementelor pare se poate reduce la 2 4 5: două elemente de eliminat sunt vecine și al doilea este sărit.

Păstrează limitele și precondițiile problemei în timpul reducerii. Dacă metoda cere un vector sortat, un contraexemplu nesortat nu demonstrează că implementarea încalcă acel contract.

Compară stări, nu doar ieșiri

Adaugă temporar informații de diagnostic despre indice, suma curentă sau începutul secvenței. Folosește ieșirea de diagnostic locală și elimină mesajele din rezultatul final cerut. Caută primul pas la care starea diferă de calculul manual; eroarea de la final poate fi doar consecința lui.

Verifică inițializarea, tipurile numerice și accesul la vecini. O valoare neinițializată sau un acces în afara tabloului poate produce simptome schimbătoare. Rularea locală cu instrumente de detectare a erorilor de memorie ajută, dar nu înlocuiește demonstrația algoritmului.

Păstrează regresia

După corectare, rulează din nou testul mic care eșua și exemplele anterioare. Salvează acel test. Dacă modifici mai târziu soluția, el îți arată dacă ai readus aceeași greșeală. O colecție mică de teste cu motive clare este mai valoroasă decât multe intrări asemănătoare.

Consultă ghidul verdictelor Algo25, limitele indicilor și tipurile de date pentru verificările de bază.

Întrebări frecvente

Ce înseamnă verdictul Wrong Answer?

Rezultatul programului nu corespunde cerinței pentru cel puțin un test evaluat. Compilarea și trecerea exemplului nu demonstrează corectitudinea pe întregul domeniu permis.

Care este primul pas când primesc Wrong Answer?

Recitește exact rezultatul cerut, indexarea și departajarea, apoi caută un test mic pe care îl poți calcula manual. Urmărește prima stare greșită a programului, nu doar ieșirea finală.

Cum verific o soluție optimizată care dă rezultate greșite?

Compar-o pe intrări mici cu o soluție simplă, verificată independent. Salvează fiecare caz diferit și micșorează-l până când cauza poate fi explicată. Păstrează acel test după repararea erorii.