TopCoder SRM 495 - Codeforces

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

Is rating decreaces if you registered but not participated?

→ Ответить

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

→ Ответить

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

← Rev. 2 →

Thank you

→ Ответить

makagonov

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

в переводе "Благодари" ))

→ Ответить

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

hexagon предательство ненависть

→ Ответить

k-va	13 лет назад, # \| 0 Неудачно совпало со временем поезда ... - Петрозаводск. → Ответить

yeputons

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

А я-то думаю: где Гена? :)

→ Ответить

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

Как решать 500? Я просто думал, что там надо выкидывать каждую вершину и потом считать минимальное число вершин, при выборе которых мы закрасим весь граф. Потом ответ ясно какой. Как считать это минимальное количество?

→ Ответить

PavelKunyavskiy

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

Будем в процессе дфса поддерживать 2 массива - посещенных в этом дфсе и глобально посещенных. В втором будем хранить 0 если эта вершина не посещена, 1 если посещена, 2 если посещена, но только в дфсе начатом с нее. Утверждается что искомое количество - число 2 во втором массиве после запуска дфса из всех вершин. (запускаемся только из тех, которые мы еще не умеем посещать).

Почему работает. Ответ - число компонент сильной связности, в которые ничего не входит. Несложно убедиться что то что посчитанно - именно это. кстати еще можно просто сконденсировать граф и честно посчитать эту величину.

→ Ответить

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

Хм.. интересно. Спасибо. Я почему то думал, что там какие то потоки) Не в ту сторону думал

→ Ответить

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

Спасибо) Буду знать)

→ Ответить

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

А я сконденсировал компоненты сильной связности и чет застрял на этом :)

→ Ответить

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

← Rev. 2 →

- неважный коммент -

→ Ответить

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

Я вот сейчас повнимательнее посмотрел твое описание решения. Мне кажется здесь есть неточности.
Наоборот, надо запускать из всех вершин, независимо посетили их или нет. Иначе такой тест, граф:
1-2
3-4
В итоге у тебя ответ - 4. Т.к. из вершин 2 и 4 ты не будешь запускаться и у тебя буду одни 2.
Еще тест:
1-2
2-3
4-2
5-3
Здесь ответ по твоему алгоритму - 3. Хотя на самом деле достаточно заглянуть в 2 коробки - 1 и 4 (или 5).

→ Ответить

MAK

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

По поводу первого контрпримера

<<"1 если посещена, 2 если посещена, но только в дфсе начатом с нее."

т.е. вершины 2 и 4 будут покрашены цветом 1,как пройденные при поиске из 1 и 3 соответственно и ответ 2.

По поводу второго. kuniavski отвечал на коммент и привел алгоритм поиска минимального числа вершин, при выборе которых мы закрасим весь граф (т.е. 3), а ответ на задачу получается на графе с исключенной вершиной 5 (или 4).

Алгоритм прост и красив. Жаль, что я потратил 80% контеста на размышления о потоках на измененном графе и неадекватной динамике.

→ Ответить

Egor

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

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

→ Ответить

Egor	13 лет назад, # ^ \| 0 не двусвязности, а сильной связности, конечно → Ответить

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

Что то я немного туплю, почему мы можем взять сс-компоненту и за 1 ее закрасить? мы же берем коробку и красим только ее соседей? или нет?

→ Ответить

AlexSkidanov

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

Очевидно, теперь мы знаем, что в соседях есть морковка, и можем открыть их не боясь нарваться на пустую.

→ Ответить

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

Блин :-( опять немного не хватило додумать) Спасибо)

→ Ответить

AlexSkidanov

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

Я вот щас поигрался на дорешке - можно решать и так, как ты описал.

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

Чтобы прошла не хватало при вычислении транзитивного замыкания не учитывать выкинутую вершину.

→ Ответить

Egor	13 лет назад, # ^ \| 0 Эм, я вот сначала транзитивно замкнул, а потом выкидывал - и прошло → Ответить

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

← Rev. 3 →

Поздравляю Jedi_Knight с бронзой! :)
И Petr'а с очередной победой! :)

→ Ответить

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

Спасибо :) 975 очень классная задача. Поздновато придумал короткое решение.

→ Ответить

Egor	13 лет назад, # ^ \| 0 А у меня в 975 короткое решение, но не хватило минут 6 чтобы все условия перехода в нем правильно расставить → Ответить

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

Я когда додумался до правильного короткого, как раз за 6 минут его и написал.

→ Ответить

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

Кажется только до меня дошло в 975-ой СРАЗУ поделить H на N.

→ Ответить

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

В одной комнате с Петей, он успел почеленжить раньше меня :( такой шанс упустил, эх...

→ Ответить

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

Получается Petr начелленджил на победу? :)

→ Ответить

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

Именно! Вот если бы у меня была своя комната где бы я собрал дань :(

→ Ответить

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

← Rev. 2 →

+148! =D

И снова здравствуй, Div. 1.
До скорой встречи, Div. 2. Не скучай сильно.

→ Ответить

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

А меня вот после первого СРМа с одной задачей кинули в див1. Надолго ли интересно

→ Ответить

JKeeJ1e30

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

Смотри, чтобы он успел соскучиться:)

→ Ответить

Vaness

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

Как решается 500 div 2? Очень печально, что не смог решить :(

→ Ответить

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

В нашей комнате было такое решение: сперва расставим все по-минимуму, потом все по максимуму. Что совпало-выводим, что не совпало-меняем на -1

→ Ответить

Vaness

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

В смысле по-минимуму? Как мы это сделаем?

→ Ответить

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

Смотрим буквы подряд. Ищем минимальное простое/не простое, больше только что использованного, используем его и т.д.

→ Ответить

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

Халява.
Генерим строку из n символов соответственно простым и непростым числам.
Находим первое возможное вхождение данной строки в результирующую. За линию. :)
Находим последнее возможное вхождение. Аналогично.
Пересекаем. Если не совпадают => -1.

→ Ответить

Vaness

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

О, это понятно уже. Действительно халява. Спасибо.

→ Ответить

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

А вот это не понял)

→ Ответить

Timus

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

← Rev. 2 →

Мб не самое эффективное, но динамика d[i][j] = количество возможных подмножеств длины i с последним числом j. Переход: d[i][j] = sum(d[i][k]), для k < j.

Ответ ввостановливаем идя с конца, если в d[i] кол-во не-нулей больше 1, то добавляем -1, иначе позицию где этот не-ноль встретился.

→ Ответить

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

← Rev. 2 →

А я даже сумму не считал. Просто d[i][j]=true, если j-ым числом в последовательности может быть i. А потом с конца восстанавливал жадно. Для каждого j брал наибольшее i. Если можно взять несколько i, то пишем -1.

→ Ответить

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

Правда наоочковался я перед Систем-тестом. Глупую ошибку допустил, не сделал memset булевского массива. Обычно массивы заполняются всяким шлаком, не раз горел на этом, но тут вроде повезло :)

→ Ответить

Kenny_HORROR

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

Эта та же задача, что 250 Div 1.

А решается она следующим образом. Для каждой позиции проверим какие числа на ней могут стоять. А именно:

сгенерим простые от 1 до N
переберем все числа j от 1 до N для i-ой позиции, и выполним проверку существует ли последовательность, в которой для чисел 1 до j-1 походит строка левее i-ой позиции и и для числе j+1, N подходит строка правее i-ой позиции
Проверку походит ли строка делаем жадным образом.

Так определяем что может стоять на i-ой позиции ответа. И однозначность его.

Сложность O(N^2 * длинну строки)

→ Ответить

PavelKunyavskiy

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

Можно за O(n^2). Достаточно перебрать не все числа, а только два больших чем последнее с нужной простотой.

→ Ответить

Rei	13 лет назад, # ^ \| 0 Можно за o(n). Сгенерить все простые, потом взять самую прижатую влево подходящую последовательность, самую прижатую вправо и сравнить. → Ответить

Edvard

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

Может кто-нить объяснить идею 500ки в див1? А то здесь как то реализацию обсудили, а идею обошли стороной

→ Ответить

Kenny_HORROR

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

← Rev. 2 →

+13

Ну я исходил из следующей идеи. Построим граф в котором вершинами будут коробки, а ребра будут соответствовать тому, что открытие этой коробки влечет знание, того что в другой коробке. После построения такого графа сожмем все сильно связные компоненты и получим ациклический граф в котором есть вершины в которые ничего не входит (пусть их q щтук). Т.е. мы точно определим коробку которая пустая не более чем за q открытий коробок, и не менее чем за q-1 в худшем случае. Теперь осталось определить когда мы можем получить q-1. Это значит, что после открытия всех остальных q-1 коробок у нас осталась ровно одна про которую ничего не известно. А тогда ответ q-1 если можно выбрать q-1 коробку из оставшихся, так чтобы ровно 1 была не использована (это можно сделать например проверкой есть ли такая коробка, из которой можно попасть только в вершины, которые покрыты, оставшимися).

Ну как-то так. Надеюсь более менее понятно.

→ Ответить

cmd

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

+11

Ответ: 1 - cnt / n, где cnt - количество ящиков, которые нужно открыть, чтобы получить всю информацию о всех ящиках (т.е. чтобы точно знать какой ящик пустой).

Ответ нужно максимизировать, а значит cnt минимизировать.

Как минимизировать cnt:

Если у нас будет информация о n-1 ящиках, то мы будем знать автоматически, что в оставшемся ящике. Тогда переберем ящик, который трогать не будем, а из оставшихся ящиков построим граф, где ребро между u и v есть, когда information[u][v] == 'Y' - нам нужно выбрать минимальное количество ящиков, что по ребрам в этом графе можно будет из выбранных ящиков дойти до остальных. А это делается как выше писали: конденсируется граф и считается количество вершин со степенью входа = 0.

→ Ответить

Edvard

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

Понял спасибо за оба ответа

→ Ответить

Egor	13 лет назад, # \| 0 Мои решения в репозитории, тешу себя надеждой, что они понятны без комментариев → Ответить

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

Объясните кто-нибудь как Div 2 1000 решается. :)

→ Ответить

Dmitry_Egorov

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

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

Решение.

Строим граф. Вершины - клетки, соединяем вершины ребром, если они лежат в каком-то незаблокированном треугольнике. Далее пускаем dfs по графу и ищем количество вершин в каждой компоненте связности. Если их a1, a2, ..., ak, то ответом будет число f(a1)*f(a2)*...*f(ak), где f(x)={x!/2 при x>=3, 1 иначе}.

Это был мой первый tc и div2 меня разочаровал - из 20 участников комнаты 9 не пришли, 9 решили только первую задачу, а последний 1 и 2, но вторую у него сломали в первую же минуту => челленджить было просто некого.

→ Ответить