ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1196. Экзамен по истории

Probably 10th test has a bug!
Послано [SPbSU ITMO] Yuri Bedny 26 фев 2007 06:25
I used the following O(m) algorithm, where 'a' - teacher's list, 'b' - student's list.
I got WA on test 10. After sorting _teacher's_(!) list as well, program was accepted. Therefore, it seems that 10th test has a bug. Am I right, or maybe missed smth?
It seems this bug wasn't mentioned before, 'cause general approach is not O(m), but O(m*ln(n)) solution, which uses O(n) memory. And that approach may work somehow..

Arrays.sort(b);
int c = 0;
int j = 0;
for (int i = 0; i < a.length; i++) {
    if (i > 0 && a[i] == a[i - 1]) continue;
    while (j < b.length && b[j] < a[i]) {
        j++;
    }
    while (j < b.length && b[j] == a[i]) {
        c++;
        j++;
    }
}
cout.println(c);
Re: Probably 10th test has a bug!
Послано [SPbSU ITMO] Yuri Bedny 26 фев 2007 06:29
Argument follows.. This program craches on test 10.

            cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            PrintWriter cout = new PrintWriter(System.out);
            int a [] = new int[readInt()];
            for (int i = 0; i < a.length; i++) {
                a[i] = readInt();
            }
            for (int i = 1; i < a.length; i++) {
                if (a[i] < a[i - 1]) throw new RuntimeException("10th test is wrong.");
            }
Re: Probably 10th test has a bug!
Послано Sandro (USU) 26 фев 2007 21:14
You are right! Test is fixed now. 9 authors got AC. Thank you for help.