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

Разбор задач Codeforces Beta Round #4
Автор Jokser, 15 лет назад, По-русски

Задача A

Здесь все просто. Если число нечетное или равно 2, то ответ "NO", иначе ответ "YES".

Задача B

В этой задаче есть более простые пути решения, но я решил написать ДП. Обозначим массивом bool dp[d][sumTime] возможность того, что в день d можно набрать ровно sumTime времени. Если true - то можно, если false - то нельзя. Изначально dp[0][0]=true, остальные - false.

Получаем следующее реккурентное соотношение dp[i][j]=dp[i-1][j-k], где i - текущий день, j - текущее суммарное время и k - время, которое Петя хочет потратить в i день.

Попутно запоминаем расписание формулой from[i][j]=k. Далее, восстановить расписание не составляет труда.

Задача C

Здесь можно использовать map<string,int> в С++. Считываем имя, смотрим какое число соответствует данному имени. Если 0 - выводим OK, и прибавляем единичку в map. Иначе выводим имя+текущее число в mapе и снова прибавляем единичку в map.

Задача D

Сначала отсортируем все конверты, включая открытку по возрастанию по ширине. Далее применяем алгоритм, как если бы мы искали самую длинную возрастающуюю подпоследовательность. Обозначаем dp[i] - длину наибольшой цепочки конвертов, оканчивающейся на конверт с номером i. Тогда получаем следующее реккурентное соотношение.

dp[i]=max(dp[i],d[j]+1), где j=0..i-1 и a[i].длина>a[j].длина и a[i].ширина>a[j].ширина.

Начальное условие dp[номер открытки]=0. Все остальным можно сделать -1.

Запоминаем максимальное число открыток, а также порядок их следования.

Далее отсортируем все конверты, включая открытку по возрастанию, но теперь уже по длине! И проделываем все те же действия, что написаны выше. Cравниваем результаты и выводим наибольший.

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

15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
ДП на вторую задачу О_о, классно!
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    я тоже дп писал, хотя жадина тоже была очевидна.

    просто я посчитал что в ДП меньше шансов набажить.

    → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А что с жадным алгоритмом?
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Находишь сумму минимумов sumMin и сумму максимумов sumMax. Проверяешь случаи NO: если sumMin больше sumTime или sumMax меньше sumTime.
    2. находишь diff = sumTime - sumMin.
    3. Для каждого i-го, если diff > 0, пока можно увеличивать min[i] и можно уменьшать diff, увеличиваем min[i] и уменьшаем diff.
    4. для каждого i-го результатом будет min[i]
    → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ок, спасибо! Я правда не понял, думал, про жадный по 4 задаче речь идет ))) А со второй понятно )
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Вот ещё графовая интерпретация задачи D. Построим DAG, считая что между вершинами u и v  есть дуга тогда, когда конверт u можно положить в v. При этом считаем открытку конвертом, т.е. некоторой вершиной s. Т.к. это DAG (нет циклов и петель) применяем алгоритм Дейкстры из s, назначив каждой дуге вес -1. Восстанавливаем путь.
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    не дейкстры, нам нужно максимальный путь.

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

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

      Нет. Всё верно. Мы назначаем всем дугам отрицательный вес (-1). И ищем минимальный путь дейкстрой, потом инвертируем ответ. В общем случае такой приём не работает, но в случае ДАГа можем так поступить. 

      Сам я сдал задачу квадратной от числа конвертов динамикой по графу. Сейчас попробовал написать дейкстрой - ТЛ на 25ом - видимо 25 миллионов на логарифм это уже перебор)) Хотя и нравятся мне унифицированные решения, но это не лучшее)

      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        По универсальным решениям )) я сдал так (на дорешке, на контесте не успел). 1. Читаем конверты, откидываем заведомо неюзабельные. 2. Делаем DAG, используя отношение "a входит в b". Теперь нам нужно найти макс путь в этом графе. Для этого: 3. Топологически сортируем его (получаем дерево топ сортировки). 4. Делаем ДП по данному дереву D[v] - макс длина пути для этой вершины, изначально D[v] = 0 для всех. 5. Выводим max(D[v]). Кратко так.
        → Ответить
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
А зачем в Д два раза сортировать и дп запускать? И одного хватит.
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
По поводу задачи D:

1. создаем class/struct item с параметрами width, height, index (ширина, длина и порядок, в котором появляются открытки). 
   сортируем массив item-ов (включая открытку) в убывающем порядке:
   в java через 
   public int compareTo(item i){
   if(this.width > i.width) return -1;
   if(this.width < i.width) return 1;
   if (this.height > i.height) return -1;
   return 1;
   }
   Arrays.sort(items);
   в с++ через
   bool compareTo (item i, item j) { 
           if(i.width > j.width) return true;
           if(i.width < j.width) return false;
           if(i.height > j.height) return true;
           return false;
      }
      sort(items.begin(), items.end(), compareTo);
      
2. находим наибольшуу убывающую подпоследовательность (НУП).
   массив dp[2][n+1], dp[0] хранит длину НУП (вначале забит единицами)
        dp[1] хранит элемент, из которого мы пришли (вначале забит -1)
   для каждого i-го [1;n]
   для каждого j-го от 0 до i
   если (items[i].width < items[j].width && items[i].height < items[j].height && dp[0][j] + 1 > dp[0][i]){
   dp[0][i] = dp[0][j] + 1;
   dp[1][i] = j;
   }
3. Ответом на задачу будет dp[0][index], где index - индекс открытки после сортировки
   Используя НУП, легко выводить ответ на задачу:
int start = dp[1][index];
while(start != -1){
print(it[start].index);
start = dp[1][start];
}
  
  

→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Можно просто отсортить по площади и найти НВП (игнорируя "плохие конверты", в которые не влезает открытка). Понятно, что если один конверт влезает в другой, ответ в динамике будет посчитан для него раньше - у него площадь меньше.
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а вроде как у такой задачи есть решение за O(n logn). кто-нибудь скажет идею?
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    http://e-maxx.ru/algo/longest_increasing_subseq_log
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      только вот наверно для этого алгоритма требуется полное отношение порядка, а здесь частичное(не любые элементы можно сравнить).
      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, безусловно. В принципе этот алгоритм можно модифицировать и для частичного порядка где не все элементы можно сравнивать. Только там уже будут фигурировать не минимальные числа которыми могут оканьчиваться возрастающие подпоследовательности соотв. длины, а множества таких мин. элементов, каждая пара из которых не сравнима. Эти множества тоже будут идти по возрастанию, в некотором смысле. В итоге к сложности добавится какой-то множитель, что-то типа размера максимального независимого множества. Правда не понятно, когда это будет лучше чем простой квадрат ))
        → Ответить
        • 15 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          итак, мы вроде как вернулись к тому, что не умеем решать задачу за nlogn
          → Ответить
          • 15 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Я немного потерял нить дискуссии. Если вы про общую задачу, то ее за NlogN наверное никто решать не умеет. Если про изначальную, то там можно.
            → Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    так элементарно она решается за O(n logn).
    1. выкидываешь все конверты в которые не влезает открытка
    2. сортируешь по одному из критериев (ширине или высоте) O( n *logn )
    3. ищешь максимальную возрастающую последовательность (по второму критерию) в отсортированном массиве O( n log n)
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Только пункт 2 надо немного расширить. При сортировке по одному критерию, в случае его равенства, надо брать второй критерий в обратном порядке.
      → Ответить