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

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

Предлагаю здесь обсудить задачи. Как правильно решать I?

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

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

I решается жадно. На каждом шаге пробуем посмотреть очередной фильм. Тогда складываем в вектор все уже посмотренные фильмы, сортируем его по времени и жадно смотрим.

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

    Жадно смотрим — можно подробнее?

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

      для каждого студента поддерживаем время, когда он закончит смотреть какой-то фильм — endi и предыщую красоту фильма ci, для очередного фильма пытаемя из всех свободных студентов выбрать студента с максимальным ci, но меньшим, чем красота текущего фильма.

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

        Я вроде такое и писал, только у меня WA3. Так и не понял в чем подвох.
        upd. кажется понял, неверно выбирал

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

        А почему не студента с максимальным временем окончания фильма? Для вашего алгоритма, как я его понял, есть простой тест:
        4 2
        1 2 3
        3 4 1
        5 6 4
        2 3 4
        Пусть 1й студент посмотрит 1й фильм, а 2й студент 2й фильм. Тогда для 3 фильма мы выберем 1го студента, т.к. красота его фильма больше чем у 2-го, и для 4-го фильма уже не сможем выбрать никого. Или я что-то не так понял?

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

          сортируем его по времени и жадно смотрим.

          ключевое слово — сортируем, так этот алгоритм валится тестом еще проще
          100 200 5
          1 2 4
          300 400 3

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

    А куда именно жадно смотрим? Я ниасилил придумать жадность в этом месте, и решил с помощью наименьшего покрытия графа путями %)

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

      Авторское именно такое — покрытие графа путями. Но на контесте в УрФУ все сдавали жадину.

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

        А как именно? я делал двудольный граф. Ребро из i-ой вершины левой в j-ую правой если можно посмотреть фильм j после i-ого. Находим паросочетание максимальное, строим новый граф неориентированный, в котором есть ребро (i,j) если (i,j) или (j,i) есть в паросочетании. Далее помечаем все компоненты связности в этом графе пока есть студенты.
        Еще пробовал искать по очереди паросочетания минимального веса мощностью 1,2,.. n, и лучшее выбирать.

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

        А можно узнать суть 19 теста?

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

      У меня почему-то такое ВА27 получало упорно.

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

        У меня тоже :( Из-за этого зафейлил контест. Так бы выиграл.

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

    Я решал I другим способом.

    Предположим, что у каждого фильма есть вес и нам надо найти ответ наибольшего веса. Тогда если i-тому фильму присвоить вес 2n - i - 1, то мы сведем исходную задачу к этой.

    Как решать задачу с взвешенными фильмами. Построим взвешенную сеть, где у каждого ребра пропускная способность равна 1. Каждому фильму поставим в соответствие две вершины: входную и выходную. Между входной и выходной вершинами одного фильма проведем ребро веса, равного весу фильма. Между выходной вершиной фильма i проведем ребра веса 0 ко входным вершинам всех фильмов, которые можно посмотреть после просмотра фильма i. Так же из истока добавим ребра веса 0 во все входные вершины, а из всех выходных — в сток.

    Пропустим k единиц потока. Каждая единица потока — это один студент.

    Так как 299 — это много, то пришлось писать на Java с BigInteger. Прошло с первой попытки.

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

Как решать F? OEIS подсказал только 21 число:(

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

    Критерий того, что набор (A1, A2, ..., An) с A1 ≤ A2 ≤ ... An подходит это A1 + ... + Ak ≥ 3k(k - 1) / 2 для 1 ≤ k ≤ n, причем при k = n должно достигатся равенство. Необходимость очевидна, так как любые k команд разыгрывают между собой ровно 3k(k - 1) / 2 голов. В достаточность я поверил, и после того как увидел, что ее уже сдали, без сомнения закодил ДП, которое теперь уже без труда угадывается, но из-за дурацкого ML — 64MB пришлось сдать массив ответов в коде.

    UPD. Исправил  ≤  на  ≥ 

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

      При n = 3 возможен результат (0, 4, 5). Это не вписывается в предложенную схему, так как 0 + 4 > 3. То же самое с (1, 3, 5). Тут 1 > 0. Что я понимаю неверно?

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

        должно быть

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

          Есть идеи, почему этого достаточно?

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

            Если коротко, то можно свести задачу проверки возможности данной таблицы результатов к поиску полного паросочетания в двудольном графе, а потом применить теорему Холла. Унылое доказательство в первой правке :)

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

    Еще OEIS говорит:

    FORMULA Nonnegative integer points (p_1, p_2, ..., p_n) in polytope p_0=p_{n+1}=0, 2p_i -(p_{i+1}+p_{i-1}) <= 3, p_i >= 0, i=1, ..., n.

    по этому условию можно написать динамику

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

Как решать E и H?

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

    Можно получить такое решение H. Если дискриминант меньше нуля, ответ 1. Иначе ответ:
    sqrt(1 + 3 * b^2 / a^2 — 12 * c / a), округленный вверх. Е — самому интересно)

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

      еще можно бинпоиск)

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

        А откуда бинпоиск?

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

          перебираем ответ задачи код

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

            Тоже писал бинпоиском, но во время контеста не сдал изза тупой ошибки с приведением типов: ф-ия проверки дискриминанта:

            static bool d(int A, int B, int C, long n)
                    {
                            BigInteger _b = A * n * (n - 1) + B * (n);
                            BigInteger _a = A * (n);
                            BigInteger _c = A * n * (n - 1) * (2 * n - 1) / 6 + B * n * (n - 1) / 2 + (n) * C;
            
                            BigInteger res = _b * _b - 4 * _a * _c;
            
                            return res < 0;
                    }
            

            А надо было:

            static bool d(BigInteger A, BigInteger B, BigInteger C, long n)
                    {
                        checked
                        {
                            BigInteger _b = A * n * (n - 1) + B * (n);
                            BigInteger _a = A * (n);
                            BigInteger _c = A * n * (n - 1) * (2 * n - 1) / 6 + B * n * (n - 1) / 2 + (n) * C;
            
                            BigInteger res = _b * _b - 4 * _a * _c;
            
                            return res < 0;
                        }
                    }
            
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      А как такая формула получилась?

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

        Составляем уравнение a * x^2 + b * x + c + ... + a * (x + k — 1) ^ 2 + b * (x + k — 1) + c = 0. Если у него нет корней, то дискриминант меньше 0. Из этого составляется квадратное неравенство на k. Получится (k — 1)^2 + 2 * (k — 1) + 12 * c / a — 3 * b^2 / a^2 > 0. Получим два случая — или ответ 1 (подставляя вместо k, получим условие на дискриминант), или ответ — больший корень уравнения, округленный вверх (это сама формула).

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

        Сначала сворачиваем сумму f(x) + f(x + 1) + ... + f(x + k - 1). Получаем

        Это квадратное уравнение на x. Так что считаем дискриминант. Он чудесным образом окаывается очень простым:

        a2 + 3b2 - 12ac - a2k2.

        Откуда уже все и получаем. Не знаю как все делали, но у меня, чтобы не писать длинку, были какие-то извращения со знаковым и беззнаковым 64-битным целым типом.

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

          А можно считать в даблах — для того, чтобы сравнить число с нулем, точности хватает.

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

          А корень тоже как-то в целых числах вычисляли?
          У меня зашло в даблах, но я не понимаю почему, ведь под корнем число порядка 10^18, а в мантиссе дабла всего 15 десятичных знаков (16-й как повезет), и кажется, что при преобразовании unsigned long long в double имеет место большая погрешность.

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

            Я обычно корень вот так вычисляю:

            ll sqrt(ll x) {
                ll s = (ll)sqrt(x + 0.0);
                while (s*s <= x) s++;
                while (s*s > x) s--;
                return s;
            }
            

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

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

    У меня в E решение короче, чем в любой из остальных задач :)
    Там ответ всегда да, причём номер кинозала для уранца с X руками можно найти только по числам n2, n3, n5, где X = 2^n2 * 3^n3 * 5^n5 * Y, (gcd(Y,30)=1).

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

      а можно поподробней?

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

        Не хочется раскрывать всю задачу. То есть код выглядит так:

        for i=1 to n
            read x
            n2 = 0
            for(; x % 2 == 0; x /= 2) n2++;
            // Аналогично n3, n5
            if(g==2) print f2(n2)
            if(g==3) print f3(n2,n3)
            if(g==4) print f4(n2,n3)
            if(g==5) print f5(n2,n3,n5)
        

        Функции f2,f3,f4,f5 занимают не более 10-15 символов каждая. Например, f2(n2) = n2 % 2 + 1. Остальные могу раскрыть, если кому-то сильно надо. Но, мне кажется, интересней самому их найти.

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

Как долго займет процесс добавления задач в основной архив?

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

Ну и ради интереса: как решать C кроме рандом шафла?

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

    Перебор показывает, что для n=5 всегда можно выиграть. Поэтому просто перебираем все перестановки суффикса длины min(n,5), а префикс не трогаем (за первые max(n-5,0) шагов он съестся поэтому мы работаем только с суффиксом)

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

      Зделал так как Вы написали, но ВА12 не знаю в чем может быть проблема.. может ктото может помочь? вот код:

      http://pastebin.com/a0uDPHcj

      UPD: Туплю должго быть: var basic = new[] { arr[arr.Length - 5], arr[arr.Length - 4], arr[arr.Length - 3], arr[arr.Length - 2], arr[arr.Length - 1] }; вместо: var basic = new[] { arr[arr.Length - 1], arr[arr.Length - 2], arr[arr.Length - 3], arr[arr.Length - 4], arr[arr.Length - 5] };

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

    Если у нас есть хотя бы 5 карт, то всегда можем выиграть. Теперь если карт много, то N-5 положим в том же порядке, что у противника, а остальные 5 — переберем все перестановки. Если карт меньше 5 — тоже втупую переберем все перестановки, но в этом случае мы можем и проиграть.

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

Как решать B? Пробовал переводить координаты в I координатную четверть, домножать их на 1000, брать по модулю 1000, потом искать точку, в которую отобразилось наибольшее количество установок, среди всех таких выбирать наиболее близкую к началу координат — WA 32.

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

    Близость до начала координат меряется как . То есть иногда ближе переехать в точку с отрицательной координатой. Возможно в этом ошибка.

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

    Может проблема в точности? (int)(a * 1000) не всегда дает верный ответ.

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

      А как тогда делать?

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

        Перед приведением к инту прибавлять чуть-чуть, если положительно, отнимать чуть-чуть, если отрицательно. Или как-нибудь хитро сразу читать целочисленно.

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

        Добавить EPS в случае когда a ≥ 0 и вычесть его в противном случае

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

        Например, для чисел с тремя знаками после запятой можно (int)(a * 1000 + 0.5), если a неотрицательно, и (int)(a * 1000 — 0.5), если отрицательно.

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

      Да, действительно, проблема была в этом. Спасибо!

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

А как предполагалось решать J? Я сдал все полностью в целых числах, используя некоторые дикие хаки с НОДом, чтоб избежать переполнения long long. В принципе, если б не ошибка в ДНК :), мог бы даже с плюса сдать.

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

    Аккуратное моделирование в даблах заходит

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

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

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

Интересно, как работал чекер задачи С? Если простой эмуляцией игры, то возникает вопрос — могло ли быть так, что игра зацикливается или длится очень долго? Ну и вообще интересная задача — насколько долго игра может затянуться в принципе...

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

Я конечно тупой, но как решать А?

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

    Например хешами.

    А по-другому можно?

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

      можно поддерживать баланс каждой буквы в дереве отрезков, и каждый раз смотреть если минимум и максимум балансов равен = 0, то ans++

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

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

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

          а как это быстро находить?

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

            Для первого отрезка посчитаем втупую, потом пересчитываем за O(1).

            void inc(int ch, int d) // d = 1 для входящих в окно, -1 для выходящих
            {
            	if(cnt[ch] == needCnt[ch])
            		sameCnt--;
            	cnt[ch] += d;
            	if(cnt[ch] == needCnt[ch])
            		sameCnt++;
            }
            
          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            храним длину найболшей подходящей подстроки, на каждом шагу меняем баланс(можно map в с++ или dictionary в с#):

            check[book[i - worst.Length]]--;
            check[book[i]]++;
            

            если подходящих плохих символов после отбрасивания book[i - worst.Length] в даной подстроке стает меньше чем нужно уменьшаем длину, если добавляя book[i], он плохой, и таких меньше или ровно сколько нам нужно — увеличиваем длину. Если длина нашей подстроки равна длине плохого слова — count++.

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

    O (n * m) проходит за 0, 159 с :D