Кто-нибудь может объяснить мне, зачем в задачах делают мультитесты?
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3773 |
| 3 | Radewoosh | 3646 |
| 4 | ecnerwala | 3624 |
| 5 | jqdai0815 | 3620 |
| 5 | Benq | 3620 |
| 7 | orzdevinwang | 3612 |
| 8 | Geothermal | 3569 |
| 8 | cnnfls_csy | 3569 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 163 |
| 2 | cry | 161 |
| 3 | maomao90 | 160 |
| 4 | -is-this-fft- | 159 |
| 5 | awoo | 158 |
| 6 | atcoder_official | 157 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | maroonrk | 152 |
| 10 | Dominater069 | 148 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.09.2024 05:52:56 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
Видимо, чтобы меньше файлов с тестами юзать.
думаете?
это ускоряет процесс тестирования, или просто программа участника тратит меньше времени на чтение (за счет меньшего открытия файлов)?
Ускоряет конечно, но не сильно заметно, я думаю. Мне кажется, это просто более удобно для составителя задачи. Вместо того, чтобы плодить десятки файлов, можно сделать всего несколько. Или просто, формат соревнования таков, чтобы без мультитестов нельзя — типа GCJ.
ну насчет gcj вы правы. но насчет плодить, казалось бы, не на себе же их нести
На соревнованиях, где много участников, мультитест применяется для существенного ускорения тестирования простых задач. Все-таки запустить на 2-5 тестах сильно быстрее, чем на 50. А когда на эту задачу приходит по несколько посылок в секунду — это весьма критично сказывается на появлении очереди тестирования и времени ответа.
Пример такого соревнования — идущий сейчас RCC.
Чтобы никакой другой WA, кроме WA 2, нельзя было получить.
труЪ стори)
Ну вот кстати на нашем контесте в Петрозаводске была задача с мультитестом, и какие же глаза у меня были, когда я в логе тестирования увидел WA 54. При том что тестов было 56.
Хотя, взглянув на тесты, я почти уверен что это было переполнение инта. А все предыдущие тесты были маленькие)
чтобы участники могли схватить бревна на том, что не почистили какие-нибудь структуры О_о
такое тоже было) но все таки, у кого-нибудь есть более объективное объяснение?
Это достаточно объективно, ИМХО. В реальных проектах память обычно надо за собой убирать (если нет Garbage collector).
Есть такое. Допустим, у задачи есть два решения: одно — с предподсчётом за O(n^2) и ответом на тест за O(n), второе — без предподсчёта, просто за O(n*log(n)). Хочется автору, чтоб люди искали неочевидное первое и не писали боянистое второе. Вот и вводится в задачу много тестов, чтоб n*n+T*n (Т — количество тестов) было меньше, чем T*n*log(n). Ибо одним тестом тут, понятно, не обойдёшься.
Иногда это нужно для отсечения правильных решений по асимптотике, чтобы например хуже n^2 ничего не пропихивалось. У меня есть такая задача в идеях, там не очень просто ограничить решения так, чтобы с одной стороны плохие не прошли, и на жаве не надо было выёживаться чтобы протолкнуть.
да я думал об этом, но это можно решить путем увеличения n, чтобы хуже n^2 не проходило
n можно увеличивать в пределах существующих "разумных" ограничений — подразумевается собственно комп на котором тестируется, количество участников, размер инпута. На жаве может стать большей проблемой считать огромный инпут, чем реализовать быстрое решение. В некоторых задачах N надо сделать сильно большим, чтобы N^2 стало хуже N*log(n)^2 т.к. у первого решения маленькая константа, а у второго внушительная. Ну и нельзя же сожрать ГБ оперативы и тестить каждый тест по 20 секунд, это будет слишком расточительно, и создаст громадную очередь тестирования.
Лично я мультитестов по возможности избегаю, но в одной задаче, которую я тестировала, мультитесты добавили для более точной настройки ограничений по времени — если давать тесты по одному, проходило бы больше вариантов сложности алгоритма.
P.S. Изумительная синхронизация ответов :-)
Много какие системы тестирования исторически не позволяли работать с кучей файлов. Плюс на олимпиадах по старым IOI-правилам не было никакого резона давать YES/NO задачу и дарить решениям "поддерживающим базовую грамматику английского языка" (С) в районе половины баллов.
пожалуй наиболее объективное из всего вышенаписанного, но тем не менее есть много задач без "Yes/No"
Например иногда хочется сделать очень много тестов. Например я абсолютно не понимаю, как тестировать С с нашего раунда, кроме как сделать там 600000 тестов, что мы и сделали. Иногда если тестов всего не очень много 10^5-10^6, то иногда их можно дать все.
При плохих решениях вместо привычных WA5 или WA205 получаем WA2 и не понимаем что за бага в программе. Опытные участники, умеющие тестировать, имеют намного меньший штраф, чем остальные.
Если олимпиада IOI-style, то опять же: у правильного решения 100 баллов, а у решения с мелкими багами не 90+ (как без мультитестов), а, например, 50 баллов.
На IOI лечится группировкой, а не мультитетстом. Все современные системы это поддерживают.
Проблема не когда мультитест. А когда мультитест в индийском стиле. Без ограничения на количество тестов или сумму. Вот получил TL2 и гадай что не так.
Самая ненавистная фраза в контестах с закрытым инпутом: "There will be several test cases." И вот иди думай — пройдёт 10^8 или нет.
На самом деле нормальная фраза, ограничивать надо сумму. Потому что обычно даже если указанно, то потом выясняется, что не все максимальные и.т.д.
Исторически на финалах ACM ICPC (а оттуда пошли почти все студенческие соревнования) тестирование было ручное. Запускать решение на нескольких тестах, соответственно, было очень громоздким занятием
Я еще слышал страшные истории про первые IOI. 4 теста, запуск руками в присутствии участника и руководителя. ТЛ по методу когда надоело. Еще слышал про "ну ладно, если вы настаиваете, то пусть работает, до награждения доработает зачтем". Вроде недоработало.
Я всегда думал, что рассказы про ручное тестирование на финале — это шутка:)
В целом, я готов поверить, что в то время когда финал начинал проводиться автоматическое тестирование казалось еще большей шуткой. А вот дожившее до черти когда полуавтоматическое меня действительно удивляет.
Мне Ваш топик сразу напомнил задачу J (Pyramids) с финала 2011 года. Решения некоторых команд использовали там массив размером около 1ГБ и работали за асимптотику O(maxc^(4/3)) на препроцессинг — на мощных компах на финале это работает примерно 8 секунд, зато после такого препроцессинга на один тест можно отвечать за O(c^(1/3)). А теперь представьте себе, что бы было, если бы в задаче не было мультитестов (а тестов-то аж 202 штуки).