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

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

Сегодня в Новосибирске начинается Всесибирская олимпиада по программированию.


Завтра состоится соревнование первой номинации (Game Challenge) была марафонская задача : http://olimpic.nsu.ru/wso/archive (надеюсь, что не сделаю много плохого, если выложу пароль: Tentura), в воскресенье - ACM тур.

Предлагаю здесь обсуждать впечатления и задачи.
  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

13 лет назад, # |
Rev. 2   Проголосовать: нравится +31 Проголосовать: не нравится

То ни солнца закат - то
грусть одолела.
На всесибе я не был.

13 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Оставлю небольшой обзор с личными примечаниями.

Well... Всесиб для нашей команды начался с небольшой экскурсии по городу. Мы пропустили в нужный момент банкомат одного известного банка. Нам выделили волонтершу, которая сопроводила нас до ближайшего. Что в целом было приятно :)

Жеребьевка. Это конечно мой личный взгляд, но процесс мне показался лишним. Я верю, что организаторы могли написать программу, которая рассадила бы всех участников. И кроме того, я верю в честность организаторов. Они же хотят поддерживать престиж своего турнира. Могли сэкономить минут 40 от всего процесса.

Пробный тур. Пробный тур прошел вполне спокойно. Eclipse, Far, Visual Studio, gcc запускались без каких-либо проблем.  Большой монитор, стабильные и адекватные вердикты. Печать мы не пробовали, но у ИТМО 1 она не заработала. Думаю отключили на пробный тур, на основном не использовали. Вызвала некоторую оторопь клавиатура: очень уж тяжко было перестроиться, т.к. блок Insert/Home/PgUp был повернут на 90 градусов. Длился по факту пробный тур около полутора часов; проверить можно было почти все.

Ненавязчиво волонтеры выгнали нас на открытие, а сами стали чистить компы. Как я понял, делали они это вручную. Что мне кажется не очень верным.

Открытие. Особо информативным открытие не было. Рассказали о перспективах, пожелали удачи, в конце были освещены какие-то организационные моменты.

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

Столовая порадовала своей эффективностью: особых заторов я не заметил. Либо мне повезло, либо местный персонал работает довольно резво.

Основной тур. Читатель наверное уже знаком с условиями. Я думаю о звездах еще могут сказать другие романтики :) В целом я бы оценил создание хорошего решения по ней месяца в три работы бодрой исследовательской группы. Скоро узнаем, насколько превосходят мои ожидания лидеры.

Да, немного смущающим для нас были вердикты во время основного тура. Между временем работы и баллами была у нас строчка вида AAAM. И к великому нашему сожалению узнали мы, что означала она "Accepted, Accepted, Accepted, Memory Limit" только после контеста. Этот момент мы упустили. Жаль, но и не очень очевидно было. Как оказалось, мы были не одиноки.

В итоге вместо наших потуг с разумным решением в отослали заглушку.

Ужин.

P.S. Спасибо организаторам за сок и шоколадку во время тура! Это было кстати :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Кстати, насчет жеребьевки - можно сделать так.
    Пишем программу
    int main()
    {
       ifstream cin("teams.txt");
       vector<string> v;
       while(getline(cin,s))
          if (s != "")
             v.push_back(s);
       int currentTime = time(0);
       cout<<"Current time = " << currentTime << endl;
       srand(currentTime);
       random_shuffle(v.begin(),v.end());
       for (int i=0;i<(int)v.size();i++)
          cout<<i+1<<' '<<v[i]<<endl;
       return 0;
    }

    Которая торжественно запускается на большом экране во время жеребьевки. В случае паранойи показанный рандсид полностью гарантирует честность жеребьевки (всегда можно перепроверить), а правильность времени с точностью до пары секунд проконтролировать по часам. Подтасовка вида "подогнали" выглядит нереальной.
13 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

Подскажите, пожалуйста, как решать задачу 7 (Ролевая игра 2). Там пересечение полуплоскостей или можно как-то проще?

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

    Пересечь полуплоскости - получим выпуклый многоугольник (нужно отсортить плоскости по углу нормали, а дальше за линейное амортизированное время все пересекается). Ну и потом надо за logn определять принадлежность точек этому многоульнику (делается бинпоиском).

    • 13 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Да, я это и придумал. Но думал, вдруг что попроще можно.
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Помнится, offline задачу о принадлежности N точек выпуклому проще решать сканирующей прямой по вертикали.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        так выпуклый многоугольник ещё получить надо)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Зачем так сложно, тут же очень частный случай. Можно перейти к дополнению пересеченному с первой четвертью и найти его объединение. Проверяется точка на принадлежность бинпоиском по х-координате. Понятно, что это тоже самое, но пишется по моему сильно проще.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
как решать задачу 1 и 6?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    6 - Дейкстра на графе, где цена ребра  —  длина отрезка - длина объединения отрезков, покрывающихся какой-нибудь из окружностей. Длина объединения  —  стандартная задача на эвенты.

  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Если расписать семпл, то можно увидеть общую формулу:

    Ans = sum (i = n - 1 .. 0) (C(n - 1, i) * (-1) ^ (n - 1 - i) * a[i])

    Биномиальные коэффициенты за O(n ^ 2) считать нельзя, поэтому будем вычислять их через определение как отношение факториалов.

    Для этого будем хранить два массива f[] и pow[], где pow[i] - максимальная степень p, являющаяся делителем i!, f[i] = i! / p ^ pow[i];

    Теперь для подсчета ответа достаточно проверить: если степень факториала в числителе больше суммы степеней факториалов в знаменателе, то это слагаемое даст в ответе 0 по модулю p.

    Иначе умножим факториал числителя на числа, обратные по модулю p к факториалам знаменателя. (обратные можно считать, например, Евклидом).

    Вот код: http://pastebin.com/LGKwz4KW
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
В задаче 1 формулу на бумажке можно вывести, получается сумма цешек:
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Да, но что во втором тесте? WA 2 весь контест и всё.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      N > P может быть, выносить надо степени P отдельно)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Не совсем понял, а что ломается в этом случае?
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          деление в цешке
          • 13 лет назад, # ^ |
              Проголосовать: нравится +5 Проголосовать: не нравится
            можете по-конкретней объяснить?
            • 13 лет назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится
              Могу. Мы не можем каждый раз считать Cn - 1i, потому что долго. Для этого надо переходить от i-ой к (i+1)-ой, для этого надо поделить на (i + 1) по модулю p и умножить на (n - i - 1) предыдущую цешку. Проблема в том, что делить по модулю можно если делимое и модуль взаимно просты, но такого может и не быть. Поэтому надо вынести степени p из (i + 1) и (n - i - 1), посокрощать там... как-то так
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      правда, у нас было ВА 3 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А нормально было, если число просчитанное без модулей оказалось отрицательным, выводить по модулю как положительное? Или знак в выводе был важен?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У нас зашел вывод положительного числа.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А мы весь контест парились, как же определить финальный знак :) Думали, ошибка в этом. Как оказалось не заметили про степени простых в факториалах.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать 2?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    На разборе рассказывали какую-то страшную математику.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А какие нить ссылки называли или как вообще все это дело называется (гуглить 2-dimensional random walk особо не помогло)?
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Хотя бы основные моменты решения не помните?
      Например, верно ли, что для леса без медведя существует точное решение, а лес на 20 шагов вокруг медведя нужно просто численно обсчитать?
    • 13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Оригинальный разбор задачи "Пьяный матрос" от автора (Димы Бутюгина). Там только небольшая ботва с собственными векторами в примечании...

      Над преобразованием Фурье Дима тоже думал, но не придумал, как его там использовать.

      • 13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        То, что там написано почти совпадает с моим решением и по существу и есть преобразование Фурье.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У Petr Team Андрей Халявин придумал что-то вроде бы не очень сложное с ключевыми словами "двумерное преоразование Фурье" :) Подробнее не знаю.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      "Petr team: Mitrichev, Kulikov, Mavrin", нет?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Нет, сегодня они писали составом "Петя, Егор, Ха".
    • 13 лет назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Только мне куски "двумерное преобразование Фурье" и "что-то вроде не очень сложное" разрывает шаблон на две неравные части?:)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится
    Да не сложная там математика. Пусть матожидание - это функция f. Тогда для всех деревьев внутри прямоугольника за исключением медведя выполнено f(x,y)=1+0.25*(f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1)). Продолжим f кососимметрично с помощью отражений на прямоугольник 2N*2M. Получим, что на границе выполнено f(x,y)=0.25*(f(x-1,y)+f(x+1,y)+f(x,y-1)+f(x,y+1)). Получаем, что если L - это соотвествующий линейный оператор, то Lf = 1 внутри прямоугольника N*M, 0 на границе и нечто на медведе (за пределами все симметрично, поэтому можно их не рассматривать). Осталось применить синус-преобразование Фурье. Т.е. разложим функцию f на g_kl(x,y)=sin(pi*k*x/N)*sin(pi*l*y/M). Оператор L умножает функцию g_kl на 4-2*cos(pi*k/N)-2*cos(pi*l/M). 

    Таким образом, нужно взять преобразование Фурье функции равной 1 внутри прямоугольника, 0 - снаружи. Затем поделить коэффициенты на  4-2*cos(pi*k/N)-2*cos(pi*l/M), а потом посчитать значения в двух точках - охотника и медведя. Тоже самое делаем для дельта-функции, которая равна 1 на медведе, 0 - в остальных точках. Остается для второй функции подобрать константу так, чтобы на медведе в сумме получилось мат ожидание 0. Тогда на охотнике получим нужное мат ожидание. 

    В обоих случаях подсчет коэффициентов Фурье выполняется аналитически и на каждый коэффициент нужно O(1). С медведем все совсем просто - они равны sin(pi*k*xb/N)*sin(pi*l*yb/M), c 1 внутри прямоугольника - нужно использовать формулу суммы синусов, у которых аргументы образуют арифметическую прогрессию. Подсчет значения функции в точке при известных коэффициентах Фурье - O(NM). Итого получается O(NM) действий.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Андрей, а зачем вообще f продолжать? Мы же просто решаем краевую задачу для оператора Лапласа с нулевыми граничными условиями. А потом так же без продолжения ищем функцию Грина.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Иначе не понятно, почему при применении L получается ноль на границе. 
        В частности, если бы на границе были бы заданные числа вместо нуля, то задача бы так просто не решалась.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Но значения L на границе не несут никакого смысла... Вот если сама f не ноль на границе, тогда нужно еще с соответствующей гармонической функцией для прямоугольника складывать. Разве не так?
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Кажется я понял идею. Действительно можно не обращать внимания на значения Lf на границе, поскольку значения всех синусов там равны 0 и поэтому они на преобразование Фурье не влияют.
13 лет назад, # |
Rev. 3   Проголосовать: нравится -9 Проголосовать: не нравится

Petr-a и tourist-a, наверное, интересует вопрос - как на опенкаповском туре команда Вятки сдала задачу 14 на битмаски за две минуты? ;)

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

    Я не из Вятки, но отвечу:
    Анонимус никогда, после сдачи одной задачи, не исправлял в другой, написанной задаче тупую опечатку, найденную сокомандником?
    Такая супер-тактика позволила нам на четвертьфинале сдать задачу H за рекордное время 1 минута 2 секунды...

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Анонимус внимательно проанализировал время сдачи и считает, что команда в составе двух человек должна быть эпично крута, чтобы вбить эту динамику за 10 минут, потом запустить сампл, узнать, что он не работает (это все делает один человек!), отдать сразу комп второму, тот вписывает другую задачу, сдает ее а за это время первый находит опечатку в своем исходнике по распечатке, которая оказывается в одной букве, исправляет и засылает.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Да ладно, со сдачи 13-й прошло 40 минут. По пути сдалась 3-я, но её кодить 2 минуты. Да и команда опытная.

        Кстати, передавать комп совсем не обязятельно. Когда сидишь и кодишь что-то объемное, отвлечься на пару минут на задач на формулу вполне реально.

        Мне вот интересней, как сдать F с ГП Екатерингбурга за всего 10 минут...

13 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Может ли кто нибудь рассказать как решать 9ю, буду очень благодарен)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Я конечно очень вовремя, но все-таки отвечу. 

    Решение, которое получило ОК, хотя я его строго доказывать не умею.
    Пусть p и q  взаимно просты.
    Рассмотрим разложение в цепную дробь числа . Известно, что четные подходящие дроби дадут выпуклую оболочку всех точек с одной стороны, а нечетные с другой. Сдвинем все точки лежащие ниже прямой на вектор (-1,1), а с другой стороны на (1,-1) при этом они окажутся с другой стороны от прямой. Для каждой точки (x,y) среди полученных добавим точку (p-x,q-y). Кроме того добавим очевидные точки (0,0) и (p,q). Чтобы не мучатся понимать что из этого лишнее, что  нет и в каком это все порядке, построим выпуклую оболочку. Я умею доказывать что все эти точки лежат на выпуклой оболочке и примерно понимаю как доказать, что других нет. 

    Если p и q не взаимно просты, то решим задачу для , отразим полученные точки  центрально симметрично (опять (p-x,q-y)), и опять построим выпуклую оболочку. Итого получили решение за log(n)log(log(n)). При желании доводится до log(n), за счет того, что у нас есть O(1) выпуклых кусков, для которых надо строить оболочку. Но у нас желания не было.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо огромное Паш, достаточно вовремя, я как раз дорешиваю =).
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Расскажите пожалуйста, как решать 8 и 10.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    8 - минимальное контролирующее множество в двудольном графе
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У кого нибудь проблемы с 13 тестом в 8 задаче были?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Да, к наше решение например не работало на таком тесте:

        11011011
        10000001
        11011011

        К нему правильный ответ вроде 3, а у нас больше выдавало.

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Проходит этот тест, написал минимальное контролирующее множество в двудольном графе.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            А потом уже, после того как нашли паросочетание, перенаправить ребра как того требует нахождение контролирующего множества.

            • 13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Не могли бы вы скинуть код, я ищу методом Куна, а после перенаправляю метки с левой доли в правую, путем запуска обхода в глубину из свободных вершин левой доли все по алгоритму.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, жадник на 13-м валился.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        У нас были проблемы. Но мы писали тупой DFS.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А у кого-нибудь Кун зашел? Мы его пихали очень долго, но решение валилось на 10м тесте по RE или по ML.
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        я пишу Куна, проблем с 10 тестом нету, 13 WA.

        Прошла.

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Покажите код, пожалуйста.
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Кун заходит, если провести начальный матчинг жадно.
          • 13 лет назад, # ^ |
              Проголосовать: нравится +1 Проголосовать: не нравится
            Я код выше кинул. Прошла с первого раза на Джаве.

            Там довольно банальный трюк используется, чтобы 150^2 раз 150^2 массив used не обнулять:
            Просто храним таймер и время обновления ячейчки. Если used[x][y] == timer тут уже были.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    10 - жадность. Сначала пропорционально все увеличиваем, так, чтобы сумма не превысила Т. Далее остается распихать уже не 10**6, а не более чем 10**5 единиц, которые распихиваюся жадно - каждый раз туда, где после добавления еще одной единицы среднее квадратичное возрастёт как можно меньше.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    оно же минимальное вершинное покрытие
  • 13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    10 - одна из самых простых по объему кода, странно, что сдавали хуже тех же 1-3-5.

    Найдем сначала raw_ans[i] = floor(c[i]*T/oldT) (oldT = sum (c[i]))
    Потом найдем disturbance[i] = c[i]*T/oldT - raw_ans[i] - это сколько не хватает везде до идеального результата.
    Ну и тогда понятно, что нужно добавить единички к элементам с наибольшими disturbance[i] (а когда disturbance[] одинаков - сравниваем номера)
    • 13 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Да, действительно... Думать лень было, поэтому вместо жадности с единичками написал динамику, которая еще и по точности падала %)
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
А как решается задача #4? Верно ли, что там нужно рассмотреть несколько случаев: вообще жадное решение (вариант когда отрезок с последнего ряда с подиумом кладется на следующий и не кладется), потом когда отрезки от укладки возле подиума перекладывать на ряды без подиума, и когда отрезки на рядках без подиума перекладывать на ряды с подиумом?
Кто вообще и зачем придумал такой мегапротивный изврат?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Нам надо с помощью кусков длины l покрыть c1 отрезков длины l1 и c2 отрезков длины l2  с кучей неприятных ограничений. Рассмотрим состояние (сколько осталось отрезков первого типа, сколько второго, какой "обрезок" отрезка длины l у нас есть). Состояний не так много, посчитаем для них ответы динамикой. Только надо всё делать аккуратно и не забыть про все случаи с обрезками длины 1.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я первую немного извращенно в дорешке придумал/написал.

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

Бином. коэффициент = некий суффикс факториала (например: 5*6*7), поделённый на префикс (например: 1*2*3), причём длина префикса = длине суффикса.

Окей, расфакторизуем все числа до N на простые делители. Будем идти двумя указателями: a = n - 1 к началу и b = 1 к концу.

В дереве отрезков хранить текущую C-шку по простым делителям. Тогда, чтобы получить следующую нужно добавить в дерево все простые делители a и убрать все простые делители b. Ура, победа. 

Ничего сложного, просто длинная арифметика в факторизованном виде + пересчёт.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А зачем все простые если достаточно просто хранить степень простого по которому у нас модуль, а остальные можно делить и умножать в модульной арифметке. И поддерживать 2 числа - степень нашего простого и всё остальное.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Подскажите, как решать задачу 14 (игра в карты).
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    Динамика по подмножествам. Параметры: карты первого игрока, карты второго игрока, кто ходит. Первый стремится максимизировать ответ, второй - минимизировать.

    Пересчет делается так: перебираем по карте у 1 и 2 игрока. Если такой ход возможный - пытаемся обновить ответ. Если первым ходит первый игрок, он выбирает максимальное значение из всех минимальных значений, которые ему может предложить второй игрок. Аналогично, если ходит второй - он выбирает минимальное значение из всех максимальных, которые ему может предложить первый.

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

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

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я сдал жадностью.
    Сначала тупо считаем первые 8 чисел в массив.
    Дальше при считывании очередного числа пытаемся спасти всех пациентов с помощью их "родной" группы крови, а уже потом с помощью остальных групп, подходящих для данной группы пациентов.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    можно было написать макспоток, чтобы не "мучаться" с математическим решением.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      ну просто я подумал, что это ебанутость и извращение странно: писать на такую задачу макспоток... в итоге, мы все таки решили это сделать

13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Были ли у кого-нибудь еще проблемы с check failed в 6-й задаче (opencup)?
То, что происходило, меня просто убило.
В середине контеста читаем задачу, думаем халява. Сажусь пишу, получаю WA2, отдаю код однокомандникам, пишу другую задачу. В 3:53 исправляю найденное, посылаю, получаю Check failed N/A. Сразу же пишу клару, бегло читаю код-вроде правильно переключаюсь на другую задачу.
Через полчаса не вижу никакой реакции, в 4:26 отправляю еще одну клару. В 4:40 приходит ответ, что check failed - это WA. Без номера теста или каких либо еще пояснений. На вопрос о номере теста до сих пор нет ответа и check failed так и висит в summary.

Я считаю, что подобная реакция жюри недопустима (особенно в конце контеста). И, что обидно, не на что апелляцию подавать - после контеста в том коде нашли пару опечаток (но код на дорешивании всё равно получает check failed :( )
  • 13 лет назад, # ^ |
      Проголосовать: нравится -17 Проголосовать: не нравится
    это всего лишь тренировка...
    • 13 лет назад, # ^ |
        Проголосовать: нравится +17 Проголосовать: не нравится
      Мне всегда казалось, что у открытого кубка совсем другой статус)
      Если так смотреть, то можно и acm icpc world finals списать в тренировки.
      Даже, если считать opencup тренировкой, а Снарка тренером, то почти час в конце не реагировать на check failed - это train failed.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        А на opencup постоянно такая бодяга, нет? Кажется, года полтора назад играл opencup-тур, так там просто проверялка 30 минут не работала. Вообще.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну постоянно и раз в полтора года --- это разные вещи. Да и степень жесткости не такая, как, скажем, то, что творилось на всесибе'07.

          Я негодую не столько по поводу, что с чекером что-то не так, а скорее по поводу того, что жюри не реагирует ни на вердикт, ни на клары в разумное время из-за чего совсем непонятно, что происходит с задачей.

          Что меня больше всего удивляет, что никто не пишет, что столкнулся с похожей проблей в задаче 6.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Года два назад, когда Fly гонял нас на opencup'ы, это было для не очень приятным развлечением типа "а давайте посчитаем, сколько фейлов случится за этот контест". Сейчас, кажется, стабильности стало на порядок больше. Проблемы, кажется, являются исключением.
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Влад не смог смириться с поражением по задаче первого дня "Планетарий".

Он переписал решение с использованием информации об алгоритме генератора. Сегодняшнее "решение жюри" набирает очень много баллов=) Вроде бы 155K из возможных 159K (как-то даже не верится=) ). Желающие могут почитать код тут: http://pastebin.com/EFQpiuYM

  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Вы бы лучше таблицу итоговую выложили :)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    На мой вкус это не особо удивительно для такой задачи.

    Просто это задача далеко не на 5 часов, а как минимум часов на 12. С пятью часами времени контест превратился в "кто сможет написать и отдебажить чего-нибудь умнее рандома".

    Почти час надо было потратить на понимание условия и генерации хотя бы какой-нибудь идеи. Дальше шёл процесс реализации в целом тривиальной стереометрии попеременно с попытками понять, что делает "вот та строчка в генераторе".

    Несмотря на то, что в целом генератор был написан неплохо, его основная существенная часть состояла из огроменной функции "generate_map", причём понимание работы этой функции действительно давало почти единственную загвоздку для решения, а в условии задачи алгоритм её работы явно указан не был.

    Также вся интрига была в максимальном значении параметра "от скольких ярчайших звёзд пытаемся плясать". Кажется, это стоило упомянуть в условии, т.к. это существенно влияет на задачу. По дефолту оно равнялось 60. В решении жюри явно фигурирует число "100".

    P. S. Кажется, сейчас решение жюри можно ещё улучшить. Например, можно заметить, что в похожих созвездиях отношения расстояний от звёзд до центра - примерно одинаковые. Тогда можно сразу отсечь кучу непохожих созвездий и сравнивать их более тщательно, учитывая, что самая далёкая от центра звезда не обязательно осталась самой далёкой.
    • 13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

      • 13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        Что-то с астрономией у всех не ладно... То звезды диаметром в парсек, то кубические галактики...
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Для нас было куда внезапнее, что (не спорю, криво написанное, и наверное с багами) осмысленное решение набирает примерно столько же сколько средний рандом. По всем моим представлениям оно должно набирать или больше или сильно меньше.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну, например, наше осмысленное решение, когда расписывалось в несостоятельности заполнить все три слота нормальными кандидатами, в недостающие дописывало по рандому. Соответственно, если бы оно вообще ничего не находило, оно бы и работало просто как рандом. Вы случайно не этим же путём пошли?
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Да черт его знает. Иногда есть ощущение, что оно наоборот рандом гадило.