Соревнования по планированию самолетов с 2009 финала ACM-ICPC World

Question

Из любопытства я проверял проблему, поставленную на Международном конкурсе программирования ACM 2009 года. Вопросы довольно интересные. Они доступны по адресу http://cm.baylor.edu/resources/pdf/2009Problems.pdf. Я не смог придумать алгоритм, который решил проблему 1, который я воспроизведу здесь. Это вызвало оживленную дискуссию в офисе, и мы думаем, что довольно близки к ответу, но мы были бы очень благодарны, если бы кто-нибудь смог найти / разработать полное решение (код не требуется).

Я воспроизведу здесь проблему для вашего удобства:

Задача 1

Рассмотрим задачу планирования самолетов, которые приземляются в аэропорту. Поступающие самолеты сообщают о своем местоположении, направлениях и скоростях, и затем диспетчер должен разработать график посадки, который доставит все самолеты безопасно на землю. Как правило, чем больше времени между последовательными посадками, тем «безопаснее» график посадки. Это дополнительное время дает пилотам возможность реагировать на изменение погоды и другие неожиданности. К счастью, часть этой задачи планирования может быть автоматизирована - это то, куда вы входите. Вам будут предоставлены сценарии посадки самолетов. У каждого самолета есть временное окно, в течение которого он может безопасно приземлиться. Вы должны рассчитать заказ на посадку всех самолетов, которые соответствуют этим временным окнам. Кроме того, приземления самолета должны быть максимально растянуты, чтобы минимальный промежуток времени между последовательными посадками был как можно большим. Например, если три самолета приземляются в 10:00, 10:05 и 10:15, то наименьший промежуток составляет пять минут, который происходит между первыми двумя самолетами. Не все зазоры должны быть одинаковыми, но наименьший зазор должен быть как можно большим.

Input

Входной файл содержит несколько тестовых случаев, состоящих из описаний сценариев посадки. Каждый тестовый пример начинается со строки, содержащей одно целое число n (2 ≤ n ≤ 8), которое представляет собой количество самолетов в сценарии. Далее следуют n строк, каждая из которых содержит два целых числа a _i , b _i , которые дают начало и конец закрытого интервала [ a _i , b _i ], в течение которого плоскость i может безопасно приземлиться. Числа a _i и b _i указаны в минутах и ​​удовлетворяют 0 ≤ a _i ≤ b _i ≤ 1440. Вход заканчивается строкой, содержащей одно целое число ноль.

выход

Для каждого теста на входе выведите его номер (начиная с 1), за которым следует минимально достижимый промежуток времени между последовательными посадками. Выведите время, разделенное на минуты и секунды, округленное до ближайшей секунды. Следуйте формату образца вывода.

Пример ввода

3
0 10
5 15
10 15
2
0 10
10 20
0

Пример вывода

Case 1: 7:30
Case 2: 20:00

Answer 1

Я дам эскиз алгоритма.

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

Чтобы проверить, можете ли вы достичь T , попробуйте все n! приказы, в которых самолеты могут приземляться (8! достаточно мало, чтобы этот алгоритм работал вовремя). Для каждой перестановки P1 ... Pn вы пытаетесь назначить времена жадным образом :

int land = a[0];
for (int i = 1; i < n; i++) {
    land = max(a[i], land + **T**);
    if (land > b[i]) return "CAN NOT ACHIEVE INTERVAL T";
}
return "CAN ACHIEVE";

Answer 2

Эта задача оптимизации может быть решена с помощью линейного программирования http://en.wikipedia.org/wiki/Linear_programming

Answer 3

Вот некоторый Ruby-код, который грубо форсирует решение. Обратите внимание, что test_case_one на самом деле терпит неудачу , потому что я закомментировал код, который сделает эту работу за секунды (а не за целые минуты).

Стратегия грубой силы заключается в перестановке всех последовательностей, в которых могут приземляться самолеты. Для каждой последовательности посадки создайте произведение всех возможных времен посадки. Это хорошо с целыми минутами, жестокими с секундами.

Но, конечно, преждевременная оптимизация, зло и все такое, так что это первый шаг:

require 'test/unit'

class SampleTests < Test::Unit::TestCase
  def test_case_one
    problem = Problem.new
    problem.add_plane(Plane.new(0, 10))
    problem.add_plane(Plane.new(5, 15))
    problem.add_plane(Plane.new(10, 15))
    problem.solve()
    minimum_gap = problem.minimum_gap()
    assert_equal(7.5, minimum_gap)
  end

  def test_case_two
    problem = Problem.new
    problem.add_plane(Plane.new(0,10))
    problem.add_plane(Plane.new(10, 20))
    problem.solve()
    minimum_gap = problem.minimum_gap()
    assert_equal(20, minimum_gap)
  end

  def test_case_three
    problem = Problem.new
    problem.add_plane(Plane.new(0, 2))
    problem.add_plane(Plane.new(7, 10))
    problem.add_plane(Plane.new(4, 6))
    minimum_gap = problem.minimum_gap()
    assert_equal(5, minimum_gap)
  end

  def test_case_four
    problem = Problem.new
    problem.add_plane(Plane.new(1439, 1440))
    problem.add_plane(Plane.new(1439, 1440))
    problem.add_plane(Plane.new(1439, 1440))
    assert_equal(0, problem.minimum_gap())
  end

  def test_case_five
    problem = Problem.new
    problem.add_plane(Plane.new(0, 10))
    problem.add_plane(Plane.new(1, 2))
    assert_equal(9, problem.minimum_gap())
  end

  def test_case_six
    problem = Problem.new
    problem.add_plane(Plane.new(8, 9))
    problem.add_plane(Plane.new(0, 10))
    assert_equal(9, problem.minimum_gap())
  end
end

class Plane
  def initialize(min, max)
    @ts = Array.new
    #This is a cheat to prevent combinatorial explosion. Just ignore 60 seconds in a minute!
    #min = min * 60
    #max = max * 60
    min.upto(max) { | t | @ts << t}
  end

  #Array of times at which the plane might land. 
  def times
    return @ts
  end
end

#from 'permutation' gem
class Array
  def permute(prefixed=[])
      if (length < 2)
          # there are no elements left to permute
          yield(prefixed + self)
      else
          # recursively permute the remaining elements
          each_with_index do |e, i|
              (self[0,i]+self[(i+1)..-1]).permute(prefixed+[e]) { |a| yield a }
          end
      end
  end
end


class Problem
  def initialize
    @solved = false
    @maximum_gap = 0
    @planes = Array.new
  end

  def add_plane(plane)
    @planes << plane
  end

  #given a particular landing schedule, what's the minimum gap?
  #A: Sort schedule and spin through it, looking for the min diff

  #Note that this will return 0 for invalid schedules (planes landing simultaneously)
  def gap_for(schedule)
    schedule.sort!
    min_gap = 1440
    0.upto(schedule.length - 2) { | i |
      gap = schedule[i + 1] - schedule[i]
      if gap < min_gap
        min_gap = gap
      end 
    }
    return min_gap
  end

  #Brute-force strategy
  #Get every possible plane sequence (permute)
  #Get every possible schedule for that sequence (brute_force_schedule)
  #Check that schedule
  def solve
    @planes.permute { | sequence |
        schedules = brute_force_schedule(sequence)
        schedules.each { | schedule | 
          schedule.flatten!
          gap = gap_for(schedule)
          if gap > @maximum_gap
              #puts "Found a new one: #{schedule.inspect}"
              @maximum_gap = gap
          end
        }
    }
  end

  #The list of all possible schedules associated with an array of planes
  def brute_force_schedule(planes)
    head = planes[0]
    tail = planes[1..-1]
    if tail.empty?
      #Last element, return the times
      return head.times.to_a
    else
      #Recurse and combine (product) 
      return head.times.to_a.product(brute_force_schedule(tail))
    end
  end


  def minimum_gap
    unless @solved
      solve
    end
    return @maximum_gap
  end
end

Answer 4

Я бы сделал что-то вроде этого:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef uint MASK;
#define INPUT_SCALE 60
#define MAX_TIME (1440 * 60)


void readPlaneData(int& endTime, MASK landingMask[MAX_TIME], int index)
{
    char buf[128];
    gets(buf);
    int start, end;
    sscanf(buf, "%d %d", &start, &end);

    for(int i=start * INPUT_SCALE; i<=end * INPUT_SCALE; i++)
        landingMask[i] |= 1 << index;

    if(end * INPUT_SCALE > endTime)
        endTime = end * INPUT_SCALE;
}


int findNextLandingForPlane(MASK landingMask[MAX_TIME], int start, int index)
{
    while(start < MAX_TIME)
    {
        if(landingMask[start] & (1 << index))
            return start;
        start++;
    }

    return -1;
}


bool canLandPlanes(int minTime, MASK landingMask[MAX_TIME], int planeCount)
{
    int next = 0;
    for(int i=0; i<planeCount; i++)
    {
        int nextForPlane = findNextLandingForPlane(landingMask, next, i);
        if(nextForPlane == -1)
            return false;

        next = nextForPlane + minTime;
    }

    return true;
}


int main(int argc, char* argv[])
{
    while(true)
    {
        char buf[128];
        gets(buf);
        int count = atoi(buf);
        if(count == 0)
            break;

        MASK landingMask[MAX_TIME];
        memset(landingMask, 0, sizeof(landingMask));

        int endTime = 0;
        for(int i=0; i<count; i++)
            readPlaneData(endTime, landingMask, i);

        while((endTime > 0) && !canLandPlanes(endTime, landingMask, count))
            endTime--;

        printf("%d:%02d\n", endTime / 60, endTime % 60);
    }
}