Блог пользователя Edvard

Автор Edvard, 12 лет назад, По-русски

Всем привет! В последнее время интерактивные задачи стали очень модными (сегодня даже все задачи оказались такими), поэтому хотелось бы узнать мнение сообщества по поводу хитрого вопроса. Сегодня на контесте были такие задачи, что интерактор просто читал тест из инпута и честно отвечал нам на наши запросы. Но бывают и другие интеракторы у которых ровно один тест, они ничего не читают из инпута и играют против нас оптимально (т.е. если мы хоть раз ошибемся то интерактор точно выиграет). Задача последнего типа например была на позапрошлом полуфинале NEERC. Эти два типа сильно отличаются поскольку в первом типе можно запихать всякую рандомизированную фигню, в то время как во втором типе нельзя. С другой стороны в сегодняшней задаче А (мне так кажется) и не только можно было написать интерактор который играет против нас оптимально, а если я правильно понял там были тупо тесты. Поэтому хотелось бы знать не правильнее было бы участникам давать информацию по поводу того какого типа интерактор в задаче, поскольку в противном случае команда сразу пихающая хрень получает преимущество (хотя это не логично).

  • Проголосовать: нравится
  • +44
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Наверное, ты путаешь А и D.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да нет вроде в А где строчки были. Хотя в D про игру тоже можно

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      В А нет игры. Там интерактор просто на запросы отвечает.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +26 Проголосовать: не нравится

        Видимо, имеется в виду, что можно не загадывать строку заранее, а отвечать на запросы так, чтобы игроку приходилось задавать как можно больше запросов.

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Вань ну ты же знаешь я все называю "играми" и "чуваками". Я имею в виду, что например в задаче А интерактор на первые 16 запросов типа * c * мог бы всегда (вообще всегда отвечать No)

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Если говорить о рандоме, то он еще и в I, и в J проходил. Там, правда, вряд ли существует тест или стратегия против него.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А что плохого в рандомных решениях, если они проходят ~150+ тестов?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я не против рандома. Просто думаю надо предупреждать о том что рандом проходит. К примеру как ты помнишь в Сазанке была задача (про точки) которая просто для точек не решалась, но для точек нагенеренных случайно существовало отличное решение и в условии было сказано что точки рандомные. P.S.: проходит ~150+ тестов не значит, что решение правильное. а на олимпиадах вроде нужно решать правильно

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    На всех тестах не протестируешь, но есть такие рандомные решения которые можно завалить...

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    То, что в идеале проходить должны доказуемо правильные решения. Или, более чёткий принцип: "Если решение можно за разумное время убить, жюри должно его убить".

»
12 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

... is fixed but not revealed to you.

Не хочу судить о, том, насколько это хорошо, но отсюда вроде достаточно хорошо понятно, что строчка должна быть фиксирована.

В русских условиях не так хорошо понятно, но я понимаю "загадано" тоже так.

Ну и вообще в задачах, похожих на эту(не могу сформулировать, что это значит), я думаю стоит писать более менее ЯВНО в условие, если интерактор оптимальный.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Я как раз об этом и говорю

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Эм, вроде бы не совсем об этом.

      Я имел ввиду, что вот именно в этой задаче, было написано, что стрчока загадана и этого вполне достаточно, а вот если интерактор был умный, тогда да, стоило бы это добавить.

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Фразу "строка загадана" я понял как часть легенды. Особенно учитывая какие бывают баги в условии (например сегодня в F вроде серьезная недописка была) эту фразу можно было понять и так и этак. А я как раз писал о том, что стоить написать большими буквами, а не в последнем предложении последнего комментария к последнему примеру шрифтом 8px типа: "строка становится известной и не меняется в течении работы вашей программы".

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Да, эта фраза как раз для того, чтобы различить эти два понимания условия.

    Согласен, что какая из двух задач имеется в виду — следует указывать как можно более явно. Жюри Открытого Кубка работало над тем, чтобы это было понятно и в этих условиях.

    Какая задача лучше — в которой 150 тестов или в которой один, а интерактор играет оптимально? Мне кажется, обе задачи хорошие.

»
6 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

О каком контесте речь?