En la programación competitiva , es muy frecuente escribir código que funcione en los casos de prueba de muestra dados, pero al enviarlos termina con un veredicto WA (respuesta incorrecta) . Aquí es donde las cosas se vuelven frustrantes y no se sabe en qué caso de prueba falla la solución . En tales situaciones, hay algunas cosas que un programador puede hacer:
- Comprobar manualmente si hay casos de esquina
- Pruebas de estrés
Comprobación de casos de esquina :
En algunas declaraciones de problemas, tiene casos de prueba de esquina donde el programador necesita agregar/editar algunas líneas de código para asegurarse de que el programa también funcione bien en esos casos. Por ejemplo, en un problema en el que necesita encontrar el entero positivo mínimo en una array y si una solución es algo como esto:
int mn = arr[0]
for i : 1 -> arr_size:
if (arr[i] < mn)
mn = arr[i]
print mn
Explicación :
la lógica anterior no daría un veredicto AC (aceptado) y es fácil resolver el problema aquí. Uno de los casos de prueba en los que este código fallará es cuando la array es arr[] = {2, -1, 3, 4, 5} . La Salida del algoritmo anterior es -1 Pero la Salida correcta es 2 . Para encontrar el número entero positivo
mínimo, debe editar el código para asegurarse de que no se incluyan números enteros negativos.
Pruebas de estrés :
Prueba de estrés Supongamos que un problema que tiene una solución ingenua (lenta) y una solución óptima (rápida) obtiene un veredicto TLE (límite de tiempo excedido) al enviar la solución de fuerza bruta, así que encuentre la solución óptima pero al enviarla obtenemos WA en algunos o todos los casos de prueba.
Ahora, lo primero que debe hacer aquí sería pensar en algunos casos de prueba en los que la solución puede no funcionar y verificar la solución en ellos. Si no puede pensar en los casos de prueba, entonces hay una forma más y es la prueba de estrés .
En las pruebas de estrés , la idea es generar casos de prueba aleatorios y verificar el resultado de la solución de fuerza bruta y la solución óptima. Aunque la solución de fuerza bruta es lenta , sigue siendo correcta , mientras que la solución óptima es más rápida , pero es incorrecta en algunos casos de prueba. Esto nos permite verificar si la salida de la solución óptima de algún caso de prueba es correcta o no sin verificar manualmente , simplemente puede verificar si la salida de Naive Solution concuerda con la salida de Optimal Solution . La verificación se realiza automáticamente y también la corrección del código en miles depende de la complejidad de la solución Naivede casos de prueba en segundos, por lo que la probabilidad de encontrar el caso de prueba donde falla nuestro código se vuelve muy alta .
Entonces, realice los pasos a continuación para verificar la solución en la entrada aleatoria ejecutando un ciclo infinito:
- Generar entrada aleatoria ( haga clic aquí para saber cómo )
- Salida de la tienda de fuerza bruta y solución óptima
- Si las dos salidas son (iguales) entonces imprima correctamente
- De lo contrario, imprima la entrada y rompa el bucle.
Si el ciclo se ejecuta durante algún tiempo sin interrumpirse, es decir, todas las salidas son correctas, entonces verifique si hay una entrada más grande o intente enviar su solución.
Ejemplo:
Declaración del problema : Dada una array arr[] de N enteros positivos, la tarea es encontrar el máximo producto por pares de elementos en una array .
Entrada: arr[] = [2, 3, 4, 9, 4, 7]
Salida: 63
Explicación:
El producto máximo por pares de la array es 9 * 7 = 63.Entrada: arr[] = [-20, -50, 1, 2]
Salida: 1000
Explicación:
El producto máximo por pares de la array es (-20) * (-50) = 1000.
A continuación se muestra la implementación de las pruebas de estrés para el problema anterior:
C++
// C++ program to illustrate the stress
// testing for the above problem
#include <bits/stdc++.h>
using namespace std;
// Function that implements the Naive
// Solution for the given problem
int maxProductNaive(int a[], int n)
{
int ans;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (i == 0 && j == 1)
ans = a[i] * a[j];
else if (a[i] * a[j] > ans)
ans = a[i] * a[j];
}
}
return ans;
}
// Function that implements the Optimal
// Solution for the given problem
int maxProductOptimal(int a[], int n)
{
// Sort the given array
sort(a, a + n);
// Find the maximum product
int ans = a[n - 1] * a[n - 2];
// Return the product
return ans;
}
// Function that performs the
// Stress Testing
void test()
{
// Seeding random number generator
// to get uniques values
srand(time(0));
while (1) {
// Generate values for n
// from 2 to 10
int n = rand() % 10 + 2;
int a[n];
// Iterate over array a[]
for (int i = 0; i < n; i++) {
// Subtracting -5 will
// generate -ve integers
a[i] = rand() % 10 - 5;
}
// Solution using Naive Approach
int ans_brute
= maxProductNaive(a, n);
// Solution using Optimal Approach
int ans_optimal
= maxProductOptimal(a, n);
// If ans is correct
if (ans_brute == ans_optimal)
cout << "Correct\n";
// Else print the WA Test Case
else {
cout << "Wrong Answer\n";
cout << n << endl;
// Print the array a[]
for (int i = 0; i < n; i++)
cout << a[i] << " ";
cout << "\nCorrect Output: "
<< ans_brute << endl;
cout << "Wrong Output: "
<< ans_optimal << endl;
break;
}
}
}
// Driver Code
int main()
{
// Function Call for Stress Testing
test();
return 0;
}
Wrong Answer 4 -4 -3 -3 1 Correct Output: 12 Wrong Output: -3
Explicación :
la solución óptima funciona bien para números enteros positivos, pero falla en números enteros negativos , como se muestra en la salida del código. A través de la prueba de estrés se descubrió el problema con el código. Para generar y probar nuestro código para entradas más grandes, genere números enteros más grandes para n y a[I].
Resumen : las pruebas de estrés seguramente ayudarán a depurar el código, pero primero debe intentar pensar en un caso de prueba en el que el código puede no funcionar porque es menos complejo verificar algunos casos de prueba simples y, si eso no ayuda, continúe con la prueba de estrés. .