Форум DL

Мой профиль

Как избегать ошибок (а особенно глупых) при решении задач.
Часто бывает так, что вы придумываете задачу, пишете решение, которое вроде бы работает, но в итоге получаете не все баллы.
Есть разные способы борьбы с этим. Вот, пожалуй, самый эффективный метод поиска и устранения ошибок.
Итак, у вас есть вроде бы решение на 100. Как сделать, чтобы оно действительно было решением на 100?
Во-первых, перечитайте свой код.
Да, это помогает. И это особенно здорово работает, если задача несложная.
Во-вторых, придумайте несколько тестов, не обязательно сложных. Так можно найти маленький тест, на котором решение неверно работает, и далее действовать по стандартной схеме (кому как нравится - отладка/отладочный вывод).
Если и так вы не нашли ошибку, можно попробовать стресс-тесты.
Как это делать.
Предположим, в задаче N<=10^5, вы придумали и написали решение O(NlogN) и тестируете его, а вот O(N^2) пишется совсем просто.
Тогда можно поступить так:
Напишите решение за O(N^2)
Напишите генератор рандомных тестов c небольшим N, запускайте его
Запустите свою программу O(NlogN) на сгенерированном тесте, запустите свою программу O(N^2)
Сверьте ответы
Для надежности, конечно, нужно это делать много раз.
Как делать это много раз, не прикладывая усилий? .bat файлы. Об этом уже можно почитать в интернете, есть много гораздо более крутых объяснений, чем мои

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

А вообще, самый лучший метод - быть внимательным. Но он самый сложный

Мой профиль

Владислав Мосько:

.bat файлы. Об этом уже можно почитать в интернете, есть много гораздо более крутых объяснений, чем мои

Было бы здорово, если бы ты просто привёл прямые ссылки на все известные тебе такие объяснения.

И ещё всё-таки хотелось бы конкретики.

Вот в ближайшее воскресенье - ты напишешь все решения (6 штук, на сборах - в день по 4 штуки).
Например через 2.5 часа.

Что конкретно ты будешь делать потом?

1. Перечитаешь исходники
(Всех задач? Не всех задач? Какие будешь перечитывать, а какие нет?)

2. Тестирование на ручных тестах
(Все задачи? Не все задачи? Для каких задач будешь делать, для каких - нет? и почему?)

3. Автоматическое тестирование (альтернативное решение+генерация тестов+автосравнение результатов)
(Все задачи? Не все задачи? Для каких задач будешь делать, для каких - нет? и почему?)

Мой профиль

Насчет .bat файлов. Если вдруг кому-нибудь очень интересно и он хочет подробно почитать про это - вот самая первая ссылка по запросу "bat файлы" - http://www.philosoft.ru/batniki.zhtml
Бегло просмотрел, вроде там все очень так доступно объясняется. Если лень это все читать и разбираться, то вот:

:loop
    generate.exe
    slow_solution.exe
    my_solution.exe
    check.exe
Goto :loop

(Goto здесь создает бесконечный цикл)
Пишем такое в блокноте, сохраняем с расширением bat, запускаем.
Вроде здесь из названий все понятно.
generate.exe - создает input.
slow_solution.exe - ваше медленное, но точно верное решение.
my_solution.exe - решение, которое вы тестируете.
check.exe - сравнивает output1 и output2. Если они совпадают, можно, например, вывести зеленую надпись OK. Если нет - красную WA. Но это не обязательно. Можно просто check.exe заставить сохранить где-нибудь input, на котором ваше решение упало, чтобы потом можно было изучить этот тест.
////
По поводу того, что я буду/не буду делать в воскресение и далее...
Пункты 1 и 2 обязательны для всех задач.
А вот уже пункт 3 - довольно скользкое место. Можно потерять, скажем, час суммарно, на написание всего этого добра (generate, slow_solution, check) по всем задачам, а потом этого часа где-нибудь в конце на отладку. (А еще иногда так бывает, что даже не хватает времени написать. Здесь уже нужно расставлять приоритеты и решать, стоит ли рискнуть). Так что с этим нужно быть аккуратным и использовать только когда не до конца уверен в своем решении.

Мой профиль

Ещё раз

Написал все решения за 2.5 часа.
Ещё пол-часа - перечитывал все решения.
Ещё пол-часа - тестил вручную все решения

Возможно, что-то нашёл и исправил.

Прошло 3.5 часа, осталось 1.5
Будешь продолжать перечитывать/тестить вручную/писать автоматизацию?
На основании чего будешь принимать решение?

Мой профиль

Если остается целых полтора часа, то это очень хорошо

В таком случае можно написать автоматизированное тестирование на все задачи, на которые оно еще не было написано

(Потому что делается это достаточно быстро).
И пока выполняются N процессов тестирования, можно составлять тесты руками / придумывать крайние случаи.

Мой профиль

USACO 2015 February
Bronze:
1: +
2: +
3: +
Silver:
1: +1
(Если сверять только по одному хешу, получаются неточные результаты. Использовать двойной хеш)
2: +
3: +
Gold:
1: +5
(Ошибки в коде, плохо подобранная константа).
2: -9
(Попытки запихнуть асимптотически неоптимальное решение).
3: -12
(Попытки запихнуть эвристику).

Д/З: G2, G3

Мой профиль

Usaco 2012 April
Bronze:
1: +1 - опечатка
2: +2 - неверные идеи
3: +2 - кривые руки
4: +7 - неправильно понял условие, кривые руки
Silver:
1: -2 - неправильно понял условие
2: +
3: не трогал
Gold:
1: не трогал
2: не трогал
3: невпихиваемая в TL идея

Д/З: S3,G2,G3
G1(?комплексные числа)

Мой профиль

http://dl.gsu.by/task.jsp?nid=1266187&cid=15

Моя вечная ошибка --> границы типов данных.
Вот без этого жить просто не могу. Вместо внимательного прочтения условия и сразу установки типа данных переменных на long long, написал int и тест с числом 10е10 сразу же вылетал + я использовал более глупый метод подсчета, т.е. сначала считал сумму минимальных чисел одного массива и сумму максимальных чисел другого массива, а уже в ответ выводил их разность, тем самым во время суммирования в один момент я выходил за границу типа данных int. Надеюсь у меня такого более не повторится

P.S. Спасибо Михаилу Семеновичу за решение по которому я смог определить свою багу.

Мой профиль

USACO 2011 November
B1 - +2. Не прочёл внимательно условие.
B2 - +.
B3 - +.
B4 - +1. Не проверил семпл.
S1 - +2. Посылал идейно неправильное решение.
S2 - +2. Для компилятора GNU С++ 4.8.1 давала CE(у меня всё компилилось). Зашло с MVS C++. В GNU С++ 4.8.1 нельзя использовать переменную next.
S3 - +.
G1 - +1. Не поставил long long.
G2 - +2. Ошибся в константе.
G3 - +3. Не рассмотрел случай.

______________________
Work hard and win a prize

Мой профиль

USACO 2011 November

Bronze
1. +
2. +1 (Случайно открыл файлы)
3. +
4. +

Silver
1. -22 (Неверные идеи, потом очень неоптимально написанное решение. В дорешивании получил WA на последнем тесте)
2. +
3. +

Gold
1. +
2. +1 (Небольшая ошибка)
3. +1 (Неправильно добавил ребра в граф - невнимательность)

Мой профиль

USACO April 2011
Bronze
1: +3 плохо прочитал условие, поспешил писать
2: +
3: +9 сначала stack overflow, потом непонятные ошибки с памятью
4: +1 писал код, потом понял, что нужно немного переделать, переделал, а вот строка из старого варианта осталась
Silver
1: +2 долго пытался понять, что все-таки делать с порталами (в условии мало подробностей о том, как они работают)
2: +2 забыл одну мелочь
3: +
4: нет чекера
Gold
1: +1
2: нет чекера
3: не придумал

Мой профиль

Usaco 2011 February
Bronze:
1: +1 неправильно понял условие
2: +5 не учел мелочи
3: +2 запутался в собственной индексации
Silver:
1: 0 почему-то не заработало, где-то что-то не отнял, надо разобраться
2: +1 не открыл файл
3: -11 не знаю, надо разбираться
Gold:
1: +
2: 0 не читал
3: +10 были проблемы на стороне dl, вообще, скорее всего, где-то +2

Мой профиль

USACO\2011\February\
1 - +.
2 - +.
3 - +.
4 - +.
5 - +1. 1 упало из-за размера стека.
6 - +10. Пихал всякую ерунду.
7 - +.
8 - -20. Не упихал.
9 - +.
______________________
Work hard and win a prize

Мой профиль

USACO\2010\December.
G_1 на самом деле +2. Не обнулил переменную.
G_2 должно было быть +.
______________________
Work hard and win a prize

Мой профиль

15_NizhNovg
Задача 2. Стояло 1e-18, а надо -1e18.
______________________
Work hard and win a prize