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

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

257A - Sockets

Очевидно, что выгоднее использовать сетевые фильтры с наибольшим количеством розеток на них. Поэтому сначала отсортируем их по убыванию этой величины. Теперь переберем ответ, то есть, сколько фильтров мы будем использовать, пусть это значение равно p, а фильтры имеют a1, a2, ..., ap розеток. Очевидно, что если соединить эти фильтры, то итого будет доступно k - p + a1 + a2 + ... + ap розеток. Это значение надо сравнить с m и выбрать минимальное подходящее p. Если ни одно значение p не подходит, то следует вывести  - 1.

257B - Playing Cubes

Для начала переберем цвет первого кубика, который поставит Петя. Вася следующим ходом захочет поставить кубик противоположного цвета, затем Петя захочет поставить кубик такого же цвета, как и поставленный Васей и т.д. Так мы можем проэмулировать всю последовательность ходов обоих мальчиков и найти их счет.

Единственное, что может изменить Петя в игре – это цвет первого кубика, и он его поставит так, чтобы его счет был как можно больше.

257C - View Angle

Сначала давайте избавимся от координат точек, а именно, заменим все точки лучами от (0, 0) до каждой из точек.

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

Отдельный случай — когда все точки лежат на одном луче, в этом случае ответ равен 0.

257D - Sum

У нас есть последовательность переменных a1, a2, …, an. Возьмем две переменные с максимальными значениеми (допустим, i и i + 1), удалим их и вставим в последовательность новую переменную x = ai + 1 - ai так, чтобы сохранилось свойство неубывания последовательности. Так будем делать до тех пор, пока не останется единственное число s, которое и будет искомой суммой. Очевидно, что если мы будем разворачивать последовательность замен с учетом знаков, то в итоге узнаем, какой знак стоит у каждой из начальных переменных так, чтобы их сумма была равна s.

Теперь осталось понять, почему число s подходит под ограничения 0 ≤ s ≤ a1. Очевидно, что оно не может быть отрицательным, так как при всех заменах мы из большего числа вычитаем меньшее. Также несложно понять, что при всех заменах минимальное число в последовательности не может увеличиваться, значит, оно до последней замены будет максимум a1. Аналогично, второе число в последовательности также не может перед последним шагом быть больше a2 и так далее. Несложно понять, что при последней замене мы получим s ≤ a2 - a1 ≤ a1.

257E - Greedy Elevator

Эта задача решается классическим методом – событиями во времени. Событиями являются: «человек встал в очередь к лифту», «человек вошел в лифт», «человек вышел из лифта».

Будем поддерживать множество будущих событий, текущее время T и текущее положение лифта x.

В каждый момент времени будем выполнять следующие действия:

  1. если есть люди, которые в текущее время T пришли к лифту, то поставим их в очередь на их стартовом этаже;
  2. если на текущем этаже есть люди, то посадим их в лифт, таким образом очередь на этом этаже опустеет;
  3. если в лифте есть люди, которые должны выйти на текущем этаже, то высадим их и запомним для них ответ – текущее время T;
  4. найдем количество людей, которые ждут выше этажа x или которые едут выше, а также найдем количество людей, которые ждут ниже этажа x или едут ниже, и согласно условию выберем направление движения.

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

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

Это можно сделать с помощью структуры «множество» с операциями «найти следующее число в множестве после данного» и «найти предыдущее число в множестве перед данным». Это умеет стандартные структуры set в С++ или TreeSet в Java.

Также для действия номер 4 нам понадобятся две структуры данных, которые умеют находить сумму чисел на определенном отрезке в массиве, для этого можно использовать, например, деревья отрезков или деревья Фенвика. Одна из структур хранит, сколько людей ждут лифта на каждом из этажей, а вторая – сколько людей в лифте хочет выйти на каждом из этажей. В принципе, эти две структуры можно объединить в одну.

Таким образом, для каждого из людей мы будем обрабатывать ровно по три события, и итоговое время решения будет равно O(n·log(n)).

Разбор задач Codeforces Round 159 (Div. 2)
  • Проголосовать: нравится
  • +22
  • Проголосовать: не нравится

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

Какое-то у меня совсем другое решение Б:


x:=min(n,m); write(n+m-x-1,' ',x);
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Всё правильно). Собственно говоря, если следовать инструкциям из разбора, это и получится.

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

      Ответ будет конечно такой же, но в разборе предлагают проэмулировать игру дважды. Итого O(2*N) вместо O(1)

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

        Просто написать эмуляцию за пару минут обычно проще, чем придумывать формулы.

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

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

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

    n+m-x-1=max(n,m)-1;

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

Sorry

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

Can you check my solution for problem C? http://codeforces.me/contest/257/submission/2892972 I have wa6, but don't understand whats wrong. Thanks a lot.

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

Вопрос по задаче D: Тест из условия: 3 3 3 5. Мы выберем i = 1. Тогда после первой итерации у нас получится 0 5. Из пары чисел "0" и "5" число <= 3 получить не выйдет. Что с этим делать?

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

    Да, вы правы, неувязочка получается.

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

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

      А я делал жадно. Завел две переменных. Далее проходил с конца циклом и брал a[i] и прибавлял к меньшей переменной. А дальше все что прибавилось к однму числу — с одной сторны разности, что к второму со второй. Если слогаемое в разности меньше второго и сумма отрицательна, то менял местами. Не очень уверен в минимальной разности данного разбиения и вообще, что оно решает задачу. То есть еще над чем подумать.

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

      У меня так на работе распределяется нагрузка на сервера. Там есть m бирж и в каждой i-ой по a[i] символов(котировок). Далее нужно на заданое число серверов разбить эти биржи, что бы примерно уравнять нагрузку.

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

    Простите, что-то я загнался. Конечно, надо брать два максимальных числа

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Доказательство корректности решения задачи D очень похоже на доказательство теоремы Римана о перестановке условно (но не абсолютно) сходящегося ряда. Естественно, проходить надо с конца. А вообще, задачи B и D идейно весьма похожи. И там и там начинаем либо с плюса, либо с минуса, а дальше действуем жадно.
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The problem B, the answer is max(red, blue)-1 and min(red,blue). How to prove it? thx !

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

Hi, the answer of problem B is max(red,blue)-1 and min(red,blue), how to prove it ? thx !

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

    petya first turn is only wasted, in all the later turns both will keep on taking points but when any one of the color dice is over , vasya cannot win points anymore. Indeed later every turn will give points to petya, since there is only single color dice. NOTE: only first dice is wasted

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

    I think this is wrong as it fails on the test 2 3
    The final sequence looks like this: RBBRB so answer should be 1 3 whereas by your algo answer would be 2 2

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

English , please...

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

    In fact, you can translate the whole page into English by using http://translate.google.com

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

      google translate: "We have a series of variables a1, a2, ..., an. Take two variables with the highest znacheniemi (say, i and i + 1)..."

      znacheniemi?

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

        It means "values" but the original word is written incorrectly in Russian.

        P.S. The first time I see when illiteracy can really make harm.

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

Зацените извращение, которое я написал по разбору 2900370. Комментарии для вас. Пожалуй, самая сложная моя реализационная задача. Критика приветствуется!

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

257C - View Angle Can somebody tell me, how will I know, is this ray neighbor with something else?

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

    sort by angle

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

      I understood how decide this problem, but how will I know, is this ray neighbor with something else? Maybe between first and second rays will be others rays? So, this picture. 'alpha'- is the biggest angle, but it's wrong answer.

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

        You should check all pairs of neigbors and choosethe best one.

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

          I understood, that you said, but how i must check it, that be sure, that between this two rays i haven't others, as at the picture the rays between l1 and l2?

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

            If ray A between B and C, then B and C aren't neighbors?

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

              Yeah, if we have the other rays, that is neighbors with C and B. Maybe i just must to search the least angle for all rays, then pick the biggest from these. Is it correct?