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

Автор map, 13 лет назад, По-русски
В 3 раунде объясните пожалуйста решение задачи В. Вроде просто считать динамику d[k][i][j] - ответ, если нажали К клавиш, и наши пальцы на i, j.

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

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Да, правильно. А в чем проблема?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    WA 7.
    Я не понимаю, в чем может быть проблема.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А покажи код, пожалуйста.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Может, ошибка возникает, если инпут из одного символа? Потому что негде там набажить, неправильно посчитанные расстояния между кнопками проверяются претестами
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Я, чтобы не рисковать, написал d[k][j] - ответ, если нажали К клавиш, один наш палец на клавише с К-той цифрой, а второй на клавише j. Но должно было пройти и по 3 параметрам, вроде бы, ни с МЛом, ни с ТЛом проблем нету.
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну да, я так написал тоже.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится
      У тебя как-то странно считается расстояние. По моему например для (3,4) будет не правильно. Получится
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Спасибо.
        Извините за беспокойство.
»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать D третьего раунда?
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В задаче D проходит жадность:  сначала мы на каждый корабль должны посадить одного хорошего человека, потом нужно попытаться распределить всех плохих людей так, чтобы ни на один корабль никого досаживать не пришлось. Потом, если есть такая позиция, куда можно посадить плохого, что придется посадить только еще одного хорошего, то тогда помещаем его туда. А после этого постоянно будем сажать плохих на крайний левый корабль. Как-то так :-)
    Ну и естественно нужно учесть случай, когда есть только один корабль
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну или можно забить константы с помощью какой-то многомерной динамики - к примеру F(номер корабля, количество уже посаженых хороших, количество хороших в последнем корабле, количество плохих в предпоследнем корабле, количество плохих в последнем корабле) -> максимальное общее число плохих. Есть и более оптимальные ДП, которые не требуют много памяти и забивать константы не надо, но эта проста как пень.
    • »
      »
      »
      13 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Что значит "забить константы"?

      upd: А, прекальк чтоль.

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

      Можно было простой рекурсивный перебор написать.

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

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

      Он вроде даже по времени проходил.


    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Эх, и без забивания констант эта динамика прошла.
»
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Как решалась Е третьего раунда?


  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    Лично я был очень сильно расстроен, что по задаче E проходит n*m... я даже не пытался такого писать :(
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Time Limit 7 sec
      n * m = 500 000 000

      за 1 секунду бывает пара сотен миллионов срабатывает. А тут их аж 7. Попробовать нужно было, вдруг повезет? :)

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну может быть и надо было. Просто я обычно не люблю писать что-то совсем уж близкое к миллиарду :) и я всё оставшееся время контеста пытался придумать что-то, что работает быстрее :)
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну никто не любит. Наверно из-за того что в большинстве случаев TL  не больше 2 сек. И все забывают на него посмотреть...
          Или ты знал, что ТЛ 7 секунд и все равно думал что в лоб не пройдет?
          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            В этих раундах я почему-то вообще не смотрел на шапки проблем) как я писал раньше, я узнал, о том, что есть файлы только когда мне об этом сказали :-)
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится
        А как решать за n *m ? я в дорешке сдал m * log(n)^2
        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

          Для каждого запроса ищем максимум за O(n) (перебираем все окна, проверяем координаты и смотрим время его отрисовки поверх остальных).

          А как решать за O(m * log2 n)?

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

            в моей терминологии n - число запросов и m - число окон.

            Разобъём по координате X все поле на 2^14 полосок, построим по этому делу дерево отрезков. Каждому интервалу соответствует другое дерево отрезков (теперь по Y), включающее все точки-запросы лежащие на полосках соотвутствующих этому интервалу (максимум n штук <= 10^4). каждая точка-запрос попадёт максимум в 14 деревьев, поэтому памяти у нас n * log(n). ах да, в вершине второго дерева отрезков лежат пары (time, window_id). Чтобы узнать  цвет ячейки мы вибираем максимум из всех интервалов, которые её содержат O(TreeSize), таким образом чтобы покрасить какую-либо ячеку в нужный цвет нам достаточно присвоить этот цвет любому интервалу содержащему её.

            UPD: последнее утверждение верно для деревьев по Y, и для дерева по X, ну и понятно почему оценка O(Log(n)^2) - сначала для дерева по X получаем Log(n) интервалов, и там на каждом дереве запрос будет стоить Log(n) 

            UPD2: код

»
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А как решается F с третьего раунда? Вроде что-то простое должно быть, но никак придумать не могу
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    Там запас топлива не нужен больше 200. Итого 1000 * 200 состояний, 1000 * 1000 * 200 ребер - зашло Дейкстра.
    Альтернативно можно сделать 100 * 100 * 200 вершин (для каждой вообще клетки) и только же * 4 ребер - просто ход в сторону или +1 топлива, и тоже пустить Дейкстру.
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Спасибо... и правда просто. Меня почему сбило с толку, что топлива до 1000 и я подумал, что будет многовато состояний :)
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится
        Даже до 100000. Меня тоже сбило, на контесте я не сдал:)
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Странно что Дейкстра зашла. Вроде бы и ребер 2 * 10 ^ 8, и вершин 2 * 10 ^ 5. Если писать сетом, то  получаем O(m * log(n)), если как обычно то O(n ^ 2). Видимо, стоило писать сетом, ведь константа невелика(обновляем значения не так часто). Или ты использовал еще какие-то соображения?
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Вершин там 200*100*100 = 2*106, из каждой вершины 5 ребер, итого 107 ребер, я использовал priority_queue, прошло с запасом.
      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится -8 Проголосовать: не нравится
        Нет. Я сам удивлен, что зашло, но, судя по всему, там оптимальные пути очень быстро находяться и выходит что-то ближе к  E+VlogV.