Как узнать тестовые примеры, где код не работает?

Опубликовано: 1 Января, 2022

В соревновательном программировании довольно часто пишут код, который работает с указанными примерами тестовых случаев, но при отправке его конца с вердиктом WA (неправильный ответ). Здесь все становится неприятно, и вы не знаете, в каком тестовом примере решение не удается . В таких ситуациях программист может сделать несколько вещей:

Проверить вручную наличие угловых случаев
Стресс-тестирование

Проверка угловых ящиков :

В некоторых постановках задачи есть угловые тестовые случаи, когда программисту нужно добавить / отредактировать несколько строк кода, чтобы убедиться, что программа работает нормально и для этих случаев. Например, в задаче, где нужно найти минимальное положительное целое число в массиве, и если решение будет примерно таким:

int mn = arr[0]
for i : 1 -> arr_size:
if (arr[i] < mn)
mn = arr[i]
print mn

Пояснение :
Вышеупомянутая логика не дала бы вердикт AC (Принято), и здесь легко выяснить проблему. Один из тестовых случаев, когда этот код не сработает, - это когда массив arr [] = {2, -1, 3, 4, 5} . Вышеупомянутый алгоритм Output равен -1, но правильный Output равен 2 .
Для нахождения минимального положительного целого числа, то нужно отредактировать код , чтобы не должны быть включены уверены отрицательные целые числа.

Стресс-тестирование :

Стресс-тестирование - это метод тестирования кода, который определяет надежность кода путем тестирования за пределами нормальной работы. Предположим, что проблема, которая имеет наивное решение (медленное) и оптимальное решение (быстрое), получает вердикт TLE (Time Limit Exceeded) при отправке решения грубой силы, поэтому придумайте оптимальное решение, но отправив его, мы получаем WA на некоторых или все тестовые случаи.

Теперь первое, что нужно сделать здесь, - это подумать о некоторых тестовых примерах, где решение может не работать, и проверить решение на них. Если вы не можете придумать тестовые примеры, есть еще один способ - стресс-тестирование .

В стресс-тестировании идея состоит в том, чтобы сгенерировать случайные тестовые примеры и проверить результат решения методом грубой силы и оптимального решения. Хотя решение методом грубой силы работает медленно, оно все же верно, в то время как оптимальное решение работает быстрее, но в некоторых тестовых случаях оно неверно. Это позволяет нам проверить, является ли вывод оптимального решения для некоторого тестового примера правильным или нет, не проверяя вручную , он может просто проверить, совпадает ли вывод наивного решения с выводом Оптимального решения. Проверка выполняется автоматически, а также правильность кода для тысяч зависит от сложности наивного решения тестовых случаев в секундах, поэтому вероятность найти тестовый пример, в котором наш код не работает, становится очень высокой .

Итак, выполните следующие шаги, чтобы проверить решение на случайном входе, запустив бесконечный цикл:

Сгенерировать случайный ввод (нажмите здесь, чтобы узнать, как)
Сохранение вывода грубой силы и оптимального решения
Если два выхода (равны), то распечатайте правильно
Иначе распечатайте ввод и разорвите цикл

Если цикл выполняется в течение некоторого времени без сбоев, т. Е. Все выходные данные верны, либо проверьте входные данные большего размера, либо попробуйте отправить свое решение.

Пример:

Постановка задачи : для массива arr [] из N положительных целых чисел задача состоит в том, чтобы найти максимальное попарное произведение элементов в массиве.

Input: arr[] = [2, 3, 4, 9, 4, 7]
Output: 63
Explanation:
The maximum pairwise product of the array is 9 * 7 = 63.
Input: arr[] = [-20, -50, 1, 2]
Output: 1000
Explanation:
The maximum pairwise product of the array is (-20) * (-50) = 1000.

Ниже представлена реализация стресс-тестирования для указанной выше проблемы:

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
" ;
 
        // Else print the WA Test Case
        else {
            cout << "Wrong Answer
" ;
 
            cout << n << endl;
 
            // Print the array a[]
            for ( int i = 0; i < n; i++)
                cout << a[i] << " " ;
 
            cout << "
Correct Output: "
                 << ans_brute << endl;
 
            cout << "Wrong Output: "
                 << ans_optimal << endl;
            break ;
        }
    }
 }
 
// Driver Code
 int main()
 {
    // Function Call for Stress Testing
    test();
    return 0;
 }

Выход:

Неверный ответ
4
-4-3-3 1 
Правильный вывод: 12
Неправильный вывод: -3

Пояснение :
Оптимальное решение отлично работает для положительных целых чисел, но не работает для отрицательных целых чисел, как показано в выходных данных кода. С помощью стресс-теста выяснилась проблема с кодом. Чтобы сгенерировать и протестировать наш код для ввода большего размера, сгенерируйте большие целые числа для n и [I].

Резюме : стресс-тестирование , безусловно, поможет в отладке кода, но сначала следует попытаться подумать о тестовом примере, когда код может не работать, потому что его менее сложно проверить для некоторых простых тестовых случаев, и если это не помогает, перейдите к стресс-тестированию. .

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по доступной для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Олимпиады по программированию Программная инженерия Тестирование программного обеспечения

Как узнать тестовые примеры, где код не работает?

Проверка угловых ящиков :

Стресс-тестирование :

C ++

РЕКОМЕНДУЕМЫЕ СТАТЬИ