Добрий день, шановні читачі. Сьогодні я розповім про те, на який милицю я наступив, розробляючи невелику програмку на C ++.
Після лекції, присвяченій сортування злиттям. мене чекала досить цікава задача. Дозволю процитувати текст завдання, сподіваюся, ніхто не буде проти.
Перший рядок введення містить число n (1 ≤ n ≤ 100000), друга - масив A [1 ... n], який містить натуральні числа, що не перевищують 1000000000. Необхідно порахувати число пар індексів 1 ≤ i A [j].
Грубо кажучи, потрібно знайти кількість інверсій в масиві. Наївна реалізація вкрай проста. Порівнюємо всі пари чисел масиву, вважаємо кількість інверсій. А-ля, так:
Цей код, напевно, гарний. Він зрозумілий кожному. Навіть Джуніору. Але є одна проблема. У такий імплементації алгоритму тимчасова асимптотика O (n * n).
Природно, в курсі, присвяченому алгоритмам і структурам даних такий код не пройшов (провалений тест за часом). Потрібен алгоритм, який працює хоча б за O (n * log (n)).
Так як я тільки що пройшов лекцію по сортуванню за допомогою злиття, то, подумав, що вона тут якось причетна. І правда: існує стандартний алгоритм знаходження числа інверсій в масиві за O (n * log (n)).
Не довго думаючи, я знайшов опис алгоритму і реалізував його на C ++. Закидаю код на сайт для автоматичної перевірки - код падає. Невірне рішення на 6-й набір даних.
У себе я не сумніваюся, а тому відразу подумав, що помилка десь у мене в коді. Однак це зовсім не страшно: адже у мене вже була в кишені наївна реалізація завдання, а значить я зможу досить швидко знайти проблему.
Пишу простенький генератор, який генерує випадкові масиви. Для кожного з них вважаю два рази число інверсій: за допомогою наявного алгоритму і за допомогою алгоритму із застосуванням сортування злиттям.
Запускаю 1000 ітерацій, йду пити чай. Приходжу - бачу, що всі тести успішно пройшли. Ось тут я вже перейнявся: в наївною реалізації помилитися складно, а тут виходить, що я ще зробив помилку і в нормальній реалізації.
Пішов гуглити, шукати вже існуючі реалізації алгоритму. Мабуть, завдання це вкрай поширена на курсах по алгоритмам. Я знайшов, як мінімум, 5 різних імплементацій пошуку числа інверсій в масиві. Примітно, що всі вони падали на 6-му наборі даних.
Я вже подумав, що помилка в тесті. Пишу творцям курсу, дізнаюся, що помилка на моєму боці: вже є люди, які вирішили це завдання.
Ось тут-то я вже і перейнявся, що робити. Наївна реалізація вкрай проста, щоб там припуститися помилки. Вхідних даних тесту у мене немає: теж не зможу, виходить, відстежити помилку.
І тут мене осінило: може в Росії хтось пише щось на цей рахунок (раніше я шукав інформацію тільки в eng). Виявляється, що і в РУ є дещо яка інформація.
Я, не довго думаючи, запускаю цей тест. І, що ж я бачу? Негативна відповідь (це, очевидно, абсурд). І тут я розумію всю свою дурість. Я вважав кількість інверсій і складав результат в int.
Чому це дурість? Максимальне число інверсій досягає при вхідному масиві, відсортованому по спадаючій. Число інверсій в цьому випадку дорівнює 100000 * 99999/2 = 4,999,950,000 - майже 5 мільярдів. А в int у нас влазить 2,147,483,647. Ось така ось Біда.
Моя помилка була в тому, що я відразу не подумав про те, якою може вийде результат. Я навіть не замислювався про те, що тут можливо переповнення. Адже на даних, на яких я тестував, таких проблем не було навіть близько. Як то кажуть, потрібно тестувати програму на всіх можливих вхідних даних.
Інші записи з цієї рубрики: