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

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

Сегодня прошел первый тур вышеописанной олимпиады. Предлогаю обсудить здесь задачи.

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

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

А-шку бинпоиском по ответу решал

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

    А как вы осуществляете проверку на то, что k! % n = 0

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

      Лично я разбил n на простые множители, а затем для каждого простого множителя находил k! и из них брал максимальный(если было несколько одинаковых простых множителей, то считал что то навроде ans=max(ans,минимальный к, чтобы k!/x+k!/x*x+k!/x*x*x была >= количеству одинаковых простых множителей)).

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

        И сколько в итоге получили баллов?

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

          Незнаю скоро выйдут резы(поидее я как то убито объяснил свое решение)
          По А 100

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

      Для каждого простого делителя N сравниваем степень этого простого в N со степенью этого простого в K!.

      А степень простого в K! находится так:

      int calc(int K, int P) {
        int res = 0;
        while (K >= P) K /= P, res += K;
        return res;
      }
      
»
10 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

B примерно за O(8*N) (тама 8 различных случаев и каждый перебираем за n).
C — находил для каждой X-axis точки максимальный рост(который равняеться h+0.5 или же если пересекаются то h+0.75) и суммировал их.Где то за O(N*H+X).

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

    C. Тоже самое. Решение работает в худшем случаи за 2 * 10^8 при TL 2 секунды :(.

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

      я добавил break; когда он хоть раз пересекаеться(надеюсь затащит:D)

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

        У меня макстест работал у себя за 1.7. Но прошло не на full (86), пока не знаю почему.

        UPD. WA оказывается. Тупая ошибка. Проверял до 10^6 надо до 10^6+10^4. :(

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

          в С можно по точкам ходить, отсортировав(для треугольника p[i], l[i], r[i]).

          Надо не забыть только убрать все внутренние треугольники за N^2(я забыл)

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

          Надо еще с -10^4

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

            Это я не забыл, потому что в сэмпле есть :)

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

    А можно сканлайном вот так:

    Добавим в вектор для каждой верхней вершины треугольника (x, y) данный (x — 1, 1) и (x + 1, 1). Проходим по всем высотам i сверху вниз, и по вектору слева направо, поддерживая сканлайн и несколько случаев, когда мы добавляем sqrt(2), 3sqrt(2) / 2 или 2. Сложность O(2NH), и че-то все задачи решаются за 10^8, может это нормально для ваших серверов?

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

      У нас в каждом регионе по-другому и еще нету feedback-а.

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

У вас в области тоже катают? Не знаю как других, но меня раздражает как другие пытаются скатать (непонятно откуда) и хотят порвать тех кто чалил с 7 класса олимпиаду.

UPD: Они катают отсюда походу

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

Вы Б — шку как написали(не квадрат)

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

    У нас есть 8 случаев
    насчет х(x1>=x2 или же x1<x2), y(y1>=y2 и y1<y2), z(аналогично).
    2 случая * 2 * 2 = 8 случаев.
    Каждый случай за O(N) находим максимум и минимум и его разницу берем. И из всех разниц берем максимальный.
    Итоговая асимптотика O(8*n).

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

      блин) я так подумал но не смог доказать) завтра сюда резы скинте

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

Скорее всего завтра будет игра, граф и строки. Всем удачи!

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

    игра и граф не будут отвечаю) геометрия,динамика и строки будут отвечаю) ну все равно удачи всем)

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

      Как на счет прошлой области???

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

      Ахах, ни игры, ни строк, ни динамики и ни графов не было

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

        зато геометрия была и F — ку можно двухмерной динамикой решить:D

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

Не знаю как вы, а я прочитав условия, увидел первые 2 задачи как: напишите бинпоиск по ответу.

А геома халява по идее

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

    Увидел в B: решите это уравнение и там всё будет :)

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

Задачи второго тура как решать?

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

    F можно за N, я написал за NlogN что то вроде этого:

    solve(l, r) {
      int pos = rmq(l, r); // min element
      ans = max(ans, (r - l + 1) * a[pos]);
      solve(l, pos - 1);
      solve(pos + 1, r);
    }
    

    Вроде должно проходить.

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

    В D я написал жадное решение, сортируя девушек по росту, ищу для них минимальную пару.

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

      Можно диницу было пустить за N*sqrt(N) :)

      Сколько баллов по второму кстати?

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

        Еще не проверили. Но не фулл. Я перебирал (p-a) тоже.)

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

Прошел 2-тур, может кто-то сделать разбор задач?

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

    D) Отсортим оба массива по невозрастанию, пустим два указателя, рассмотрим случаи, когда они родственники. То есть, если они не родственники, просто присваиваем i-тому мальчику j-тую девочку. В другом случае, пытаемся i + 1 -ому мальчику присвоить j-тую девочку, а для i — того двигаем второй указатель.

    Е) Предпосчитаем все делители S до его корня четвертой и корня третьей степени(2 массива). Пройдемся по ним двумя циклами. Первым итератором будет p — c, вторым p — b. p — c + p — b = 2a -> найдем а. Нужно не забыть проверить чтобы все делилось на 2.

    Решаем квадратное уравнение p^2 — ap — S/(p — b)/(p — c) = 0.

    F) Для каждого i посчитаем ближайший справа и слева элементы, меньшие его. Ответом будет максимум среди всех (r[i] — l[i] — 1) * a[i](не забудьте отнять k — 1)

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

      Капец я Е не смог до норм решения додуматься

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

        Я вообще на контесте думал, что ответы в Е только 0 и 1. :)

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

Может кто-нибудь скинуть условия 2-ого тура

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

У нас кто-то взял задачи до контеста (вчера) можете сказать откуда?

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

Задачу F можно решить используя этот алгоритм. Проходит на 100% !!!

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

А можно где-нибудь посмотреть результаты?