Большое спасибо!
3 2010-10-01 14:18:56
Re: MinCostFlow (10 ответов, оставленных в Problems)
А как решать http://acm.tju.edu.cn/toj/showp3492.html
Я так пробовал: представляем все отрезки в виде пары вершин (вход, выход), между которыми ребро с проп. способностью 1 и стоимостью -ci. Между выходом отрезка i и входом отрезка j есть ребро если aj >= bi. Ставим ребра из истока в входы всех отрезков, и из выходов всех отрезков в сток. Расставляем потенциалы Форд-Беллманом, потом Дийкстрой ищем поток. Имею TL.
Такой подход вообще корректен? Задача вызывает ассоциацию с покрытием путями ориентированного ациклического графа.
4 2010-10-01 08:46:23
Re: Singapore 2007 (3 ответов, оставленных в Problems)
Вообще нехорошая задача этот SkyLine. Там как раз ограничение на ответ в 2*(10^6) и дает то, что такого теста не будет. Получается, что количество просмотров всех узлов дерева как раз и не превысит два лимона априорно. Вот если бы ограничения этого не было, то тест "с зубьями" корректен, и будет работать за квадрат 
5 2010-09-27 12:42:09
Re: MinCostFlow (10 ответов, оставленных в Problems)
Если кому еще интересно, вот прикольная задача: http://acmicpc-live-archive.uva.es/nuev … php?p=4263 Особенно замечательно то, что TL на ней аж 120 сек 
6 2010-09-25 08:06:11
Тема: Библиографические ссылки (1 ответов, оставленных в Feedback)
Статьи очень интересные. Но! Катастрофически не хватает библиографических ссылок. Почему? Во-первых любопытно, где именно Вы этот или иной материал смогли "нарыть". Во-вторых, бывает очень интересно посмотреть некоторые доказательства касаемо корректности или времени работы, чтобы воспринимать алгоритм не как фокус, а интуитивно понимать, что эта штука действительно работает.
7 2010-08-25 06:11:42
Re: SEERC 2008 (7 ответов, оставленных в Problems)
Интересно, а почему такое решение Sky Code корректно...
8 2010-04-01 09:17:16
Re: Union в DSU... (12 ответов, оставленных в Problems)
coder.ua, посмотри главу "Структуры данных для непересекающихся множеств" в книге Кормена. Там все подробно описано, включая анализ времени работы. А насчет результата, то это сильно зависит от входных данных. Насчет практической ценности... Ну хотя бы от сжатия пути польза интуитивно понятна, по-моему.
9 2010-03-31 12:39:20
Re: Матожидание. GCJ Round 1C: Collecting Cards (5 ответов, оставленных в Problems)
cmd, огроменное тебе спасибо! Все прочитал, разобрался. Да, все так и получается. Ты первый человек, который смог по существу мне ответить!
З.Ы. Собсно и в задаче с GCJ нужно точно так же разрешить петлю.
З.Ы.Ы. Еще раз спасибо!
10 2010-03-24 07:57:42
Re: Матожидание. GCJ Round 1C: Collecting Cards (5 ответов, оставленных в Problems)
Неужели никто не может ничего подсказать? Я уже запарился с этим разбираться... Может я не очень ясно выразился?
11 2010-03-19 10:27:07
Re: Матожидание. GCJ Round 1C: Collecting Cards (5 ответов, оставленных в Problems)
Ссылки пофиксил.
12 2010-03-19 09:16:42
Тема: Матожидание. GCJ Round 1C: Collecting Cards (5 ответов, оставленных в Problems)
Всем привет! Вот никак не могу разобраться с задачей: http://code.google.com/codejam/contest/ … p2&a=2
В разборе написана вот такая формуала: http://code.google.com/codejam/contest/ … p;c=188266 Просто указана и все. Вопрос такой: какая связь этой формулы с определением матожидания? Почему, вычисляя по ней, мы получаем правильный ответ?
Еще одна задача, на этот раз с NEERC 2006: http://acmicpc-live-archive.uva.es/nuev … php?p=3710 . Решения я смотрел, одно из них содержит очень похожу рекуррентную формулу.
Насколько я понимаю, это какойто очень распространенный прием. Кто-нибудь может его объяснить?