Всем привет! В последнее время интерактивные задачи стали очень модными (сегодня даже все задачи оказались такими), поэтому хотелось бы узнать мнение сообщества по поводу хитрого вопроса. Сегодня на контесте были такие задачи, что интерактор просто читал тест из инпута и честно отвечал нам на наши запросы. Но бывают и другие интеракторы у которых ровно один тест, они ничего не читают из инпута и играют против нас оптимально (т.е. если мы хоть раз ошибемся то интерактор точно выиграет). Задача последнего типа например была на позапрошлом полуфинале NEERC. Эти два типа сильно отличаются поскольку в первом типе можно запихать всякую рандомизированную фигню, в то время как во втором типе нельзя. С другой стороны в сегодняшней задаче А (мне так кажется) и не только можно было написать интерактор который играет против нас оптимально, а если я правильно понял там были тупо тесты. Поэтому хотелось бы знать не правильнее было бы участникам давать информацию по поводу того какого типа интерактор в задаче, поскольку в противном случае команда сразу пихающая хрень получает преимущество (хотя это не логично).
Наверное, ты путаешь А и D.
Да нет вроде в А где строчки были. Хотя в D про игру тоже можно
В А нет игры. Там интерактор просто на запросы отвечает.
Видимо, имеется в виду, что можно не загадывать строку заранее, а отвечать на запросы так, чтобы игроку приходилось задавать как можно больше запросов.
Да я именно это и имел в виду
Теперь понятно.
Вань ну ты же знаешь я все называю "играми" и "чуваками". Я имею в виду, что например в задаче А интерактор на первые 16 запросов типа * c * мог бы всегда (вообще всегда отвечать No)
Если говорить о рандоме, то он еще и в I, и в J проходил. Там, правда, вряд ли существует тест или стратегия против него.
А что плохого в рандомных решениях, если они проходят ~150+ тестов?
Я не против рандома. Просто думаю надо предупреждать о том что рандом проходит. К примеру как ты помнишь в Сазанке была задача (про точки) которая просто для точек не решалась, но для точек нагенеренных случайно существовало отличное решение и в условии было сказано что точки рандомные. P.S.: проходит ~150+ тестов не значит, что решение правильное. а на олимпиадах вроде нужно решать правильно
На всех тестах не протестируешь, но есть такие рандомные решения которые можно завалить...
То, что в идеале проходить должны доказуемо правильные решения. Или, более чёткий принцип: "Если решение можно за разумное время убить, жюри должно его убить".
Отличный принцип.
Не хочу судить о, том, насколько это хорошо, но отсюда вроде достаточно хорошо понятно, что строчка должна быть фиксирована.
В русских условиях не так хорошо понятно, но я понимаю "загадано" тоже так.
Ну и вообще в задачах, похожих на эту(не могу сформулировать, что это значит), я думаю стоит писать более менее ЯВНО в условие, если интерактор оптимальный.
Я как раз об этом и говорю
Эм, вроде бы не совсем об этом.
Я имел ввиду, что вот именно в этой задаче, было написано, что стрчока загадана и этого вполне достаточно, а вот если интерактор был умный, тогда да, стоило бы это добавить.
Фразу "строка загадана" я понял как часть легенды. Особенно учитывая какие бывают баги в условии (например сегодня в F вроде серьезная недописка была) эту фразу можно было понять и так и этак. А я как раз писал о том, что стоить написать большими буквами, а не в последнем предложении последнего комментария к последнему примеру шрифтом 8px типа: "строка становится известной и не меняется в течении работы вашей программы".
Да, эта фраза как раз для того, чтобы различить эти два понимания условия.
Согласен, что какая из двух задач имеется в виду — следует указывать как можно более явно. Жюри Открытого Кубка работало над тем, чтобы это было понятно и в этих условиях.
Какая задача лучше — в которой 150 тестов или в которой один, а интерактор играет оптимально? Мне кажется, обе задачи хорошие.
О каком контесте речь?