Автор, розробник, автор розбору: Тимур Деґтярь
Для тестів, що задовольняють n, m \le 50, можна використати повний перебір: ми перебираємо всі можливі значення (це 1, 2, \dots, m-1, зауважимо, що при d \ge m Містер IP ніколи не видалить жоден тест), і для кожної пари перебираємо всі 1 \le k \le m та явно рахуємо, скільки з них задовольняють a_{i,k} > a_{i,j}, і відмічаємо, чи є тест "недійсним" для рішення при даному значенні .
Після цього залишається лише підрахувати, скільки тестів буде видалено, щоб перевірити, чи підходить це значення . Обравши максимальне , яке видаляє достатньо тестів, ми знаходимо відповідь. Якщо жодне значення не підходить, виводимо . Часова складність такого рішення — O(n m^3).
Для тестів, що задовольняють n, m \le 400, можна покращити описане вище рішення. Якщо для кожної пари попередньо порахувати, скільки існує таких , що a_{i,k} > a_{i,j}, то для фіксованих та пари можна визначити за , чи є тест "недійсним" для рішення . Попереднє обчислення можна виконати наївно — для кожної пари перебираємо всі 1 \le k \le m. Це робиться за O(n m^2). Перевірка кожного значення займає часу, і оскільки існує m-1 значень , які потрібно перевірити, загальна складність становить O(n m^2), а отже, рішення у цілому працює за O(n m^2).
Для повного розв'язку потрібно оптимізувати дві речі — обчислення для кожної пари кількості таких , що a_{i,k} > a_{i,j}, та пошук відповідного значення . Для першої частини можна для кожного відсортувати масив пар {a[i][j], j}, після чого кількість таких буде рівною (позиція у відсортованому масиві). Для другої частини можна зробити таке спостереження: якщо для деякого значення та рішення тест є "недійсним", то він буде "недійсним" і для d-1. Звідси випливає: якщо для деякого тест був видалений, то для d-1 його також буде видалено. Це дозволяє виконати бінарний пошук за значенням : встановлюємо межі пошуку [0,, m-1], і якщо результат — , то відповідь , інакше ми знайдемо її бінарним пошуком.