USACO 2012 Февральский контест

13 лет назад, # ^ |

Есть мнение, что контест ещё не закончился.

→ Ответить

Prestige

13 лет назад, # |

← Rev. 2 →

-25

Удачи всем)

→ Ответить

13 лет назад, # ^ |

14 часов еще.

→ Ответить

de_troit

13 лет назад, # |

-17

Как решать b и c в bronze div ?

→ Ответить

k-va

13 лет назад, # ^ |

+11

Не закончилось соревнование. В 15:59 МСК ещё можно стартовать и 3 часа решать.

→ Ответить

Prestige

13 лет назад, # |

← Rev. 2 →

-14

Спасибо

→ Ответить

13 лет назад, # ^ |

Про прямоугольники — если не ошибаюсь, дано 10 прямоугольников, найти площадь их объединения. Можно довольно просто это посчитать по формуле включений-исключений за O(N*2^N). Просто переберем все возможные подмножества прямоугольников, будем добавлять площадь пересечения прямоугольников в подмножестве к ответу с плюсом или минусом.
http://e-maxx.ru/algo/inclusion_exclusion_principle

→ Ответить

13 лет назад, # ^ |

← Rev. 5 →

Прямоугольники: создал массив объектов вида <x, y_down, y_up, flag>, где флаг говорит, начинается ли в этом объекте прямоугольник или заканчивается. Поместил в массив все границы прямоугольников, посортировал, и добавлял площадь пройденного куска. Сложность — (UPD) O(N^2*log(N)) — за счет подсчета суммарной высоты прямоугольников на текущий момент.

Третья: посчитаем длины s[i], пока они меньше 10^9. Теперь находим максимальный префикс s[k], меньший n, являющийся элементом последовательности, и вычитаем его длину из n. Теперь мы знаем, что дальше следуют 'm' и k+3 букв 'o'. Если n > k+4, то выкидываем k+4 символа и получаем, что n принадлежит постфиксу — т.е. тоже элементу последовательности. Решаем задачу для этого полученного n сначала =)

P.s. Кто-нибудь знает, как сделать зачеркнутый текст?

→ Ответить

13 лет назад, # ^ |

Можете показать исходник задачи про прямоугольники? O(N²) зашло бы и в silver, там N до 1000.

→ Ответить

13 лет назад, # ^ |

← Rev. 4 →

Вот. Но про квадрат я наврал, ввиду ограничений бронзового дивизиона там совсем не квадрат, прошу прощения, но, кажется, знаю как решить и за n^2*log(n) — нужно только изменить способ поиска суммарной высоты прямоугольников на текущем отрезке. Достаточно пробежать все открытые прямоугольники и положить их верхние/нижние границы в массив с пометкой открывающие/закрывающие, посортировать и пройти по нему, т.е. сделать по сути то же самое, что и по горизонтали.

P.s. А если поддерживать отсортированный набор с использованием set<>, то вроде бы можно и за n^2. Поправьте, если не прав.

→ Ответить

13 лет назад, # ^ |

Ну формально там квадрат — O(20000*N²) ~ O(N²) =)
Может я неправильно понял, но как с std::set может быть N² ? Сам set ведь работает за логарифм.

→ Ответить

13 лет назад, # ^ |

Когда проходим по отсортированному массиву левых/правых границ, добавляем верхнюю/нижнюю границы в set за O(log(n)). Если закрывающую — то удаляем за то же время. При этом эти границе содержатся в отсортированном виде, и мы можем перебирать их по порядку — за О(n). Эта процедура выполняется на для каждой встреченной точки, итого имеем O(n^2). Set нужен для поддержания отсортированности массива. В принципе можно просто содержать отсортированный массив, в который добавлять/удалять за O(n), асимптотика в итоге та же, так может быть проще.

→ Ответить

13 лет назад, # |

Первая silver проще сканлайна решается?

→ Ответить

13 лет назад, # |

Как решалась 1 задача голда?

→ Ответить

mmaxio

13 лет назад, # ^ |

Единственное, что придумалось — поток минимальной стоимости, но там квадрат минимум =( Интересно услышать и про вторую задачу в голде.

→ Ответить

13 лет назад, # ^ |

поток минимальной стоимости за квадрат? Это как?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

Zlobober

13 лет назад, # ^ |

Посоны, я один придумал сразу жадность? Она же вроде очевидна тут. Почему, кстати, "почти жадность"?

→ Ответить

13 лет назад, # ^ |

Ну, она может еще поменять что-то из предыдущего. А что за жадность?

→ Ответить

13 лет назад, # ^ |

А как здесь поток построить?

→ Ответить

13 лет назад, # ^ |

← Rev. 2 →

Две доли: 1)n вершин — это коровы. 2)n+k вершин — это коровы и скидки. Соединяем корову либо с ней самой с ценой P (если без скидки), либо со всеми скидками с ценой C. Нашли минимальное по цене масимальное паросочетание — это будет ответ.

→ Ответить

13 лет назад, # ^ |

Спасибо.

→ Ответить

Egor

13 лет назад, # ^ |

Вторая задача — ось симметрии либо является серединным перепендикуляром к отрезку, соединяющему первую точку с какой-то, либо является серединным перпендикуляром к отрезку, соединяющему вторую точку и какую-то и при этом проходит через первую точку, либо проходит через первую и вторую точку

→ Ответить

diogen

13 лет назад, # |

и 3-ая из голда?

→ Ответить

13 лет назад, # ^ |

Общие мысли: Подвесим дерево. За O(NK) посчитаем для каждой вершины ответ для поддерева при соответствующем K. Теперь посмотрим, какие вершины мы не посчитали в ответе. Те, путь к которым пролегает через родителей. Давайте еще за O(K) для каждой вершины поднимемся на K, на каждом шаге прибавляя к ответу уже посчитанное первой динамикой число для родителя (надо еще вычесть ответ для поддерева, из которого пришли).

→ Ответить

Egor

13 лет назад, # ^ |

Я так решал — будем динамически считать ответ для всех вершин, уменьшенный на число коров в самой этой вершины для всех K. Тогда answer[i][j] = сумма по всем детям answer[i — 1][v] + cow[v] — (кол-во детей — 1) * answer[i — 2][j]. Почему это так — когда мы считаем сумму для всех детей, мы лишний раз считаем возврат в начальную вершину (но без еще лишнего возврата в саму эту вершину, поэтому -1 при множителе)

→ Ответить