TopCoder SRM 477 - Codeforces

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

+26

Лично мне нравиться инициатива Егора. Всегда понятно где задать вопрос по предстоящему контесту, обсудить ход и результаты.

→ Ответить

Edvard

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

Я тоже "за" такие сообщения. Во-первых можно не посмотреть почту и не узнать про раунд, во-вторых здесь можно обсудить задачи.

→ Ответить

slalex

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

Есть мысли как решать 1000 из 2-го дива? ...

→ Ответить

hydrastuff

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

условие не совсем понял(

→ Ответить

Egor	14 лет назад, # ^ \| 0 Не стоит обсуждать это до конца челлендж фазы → Ответить

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

Сделал тупейшую ошибку в Куне в 500-ке :( интересно пройдёт ли 1000-ка

→ Ответить

Egor	14 лет назад, # ^ \| 0 я 500ку слишком сложно сделал, конечно. Надо было заметить, что этот тупо паросочетание → Ответить

mr146

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

Я заметил. Но не заметил, что на двудольном, и сдал Эдмондса-Карпа. ><

→ Ответить

Egor	14 лет назад, # ^ \| 0 Ну вот я тоже Эдмондса написал А Эдмондс - Карп это поток таки, насколько я помню → Ответить

mr146

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

Пардоньте, просто Эдмондса. Путаюсь =)

→ Ответить

it4.kp

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

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

→ Ответить

AlexSkidanov

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

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

→ Ответить

freopen

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

Я где то читал про Венгерку на месте 500. Я подумал, что Эдмондс не так уж сильно сложнее венгерки.

→ Ответить

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

А мне вот не понятно как Div 1 Hard решать...

→ Ответить

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

Либо динамика по поддеревьям, либо жадность: каждый раз брать самый длинный путь и убирать.
Я писал динамику по двум параметрам: кол-во использованных shortcut'ов и ведёт ли один из них наверх.

→ Ответить

AlexSkidanov

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

А входить в поддерево всегда по ребру?
Я писал полагая что это всегда правильно, но у меня не проходят два теста из семплов. Вот думаю это косяк в коде или ошибка в предположении :о)

→ Ответить

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

Косяк в коде :)

→ Ответить

Egor	14 лет назад, # ^ \| +5 стоп-стоп-стоп, во втором семпле мы входим в поддерево не по ребру → Ответить

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

Ой, правильно, можно входить не по ребру, ошибся.
У меня это реализовано особенностью инициализации.

→ Ответить

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

Мы ищем неориентированный путь. Внутри поддерева можно считать что входим всегда по ребру.

→ Ответить

e-maxx

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

А жадность верна? Что-то я не заметил ни одного решения, кроме моего упавшего, работающего на жадности :)

→ Ответить

fetetriste

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

fastest submission by zhuojie вполне себе жадный: http://www.topcoder.com/stat?c=problem_solution&cr=22686851&rd=14157&pm=11003

→ Ответить

e-maxx

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

А, вон как надо было жадно решать. Ну конечно, находить и удалять диаметр было неверным :) Как оказалось, надо было вдоль найденного диаметра проставлять стоимости, равные старым со знаком "минус"; в результате появляется возможность для отмены уже взятых в ответ рёбер.

→ Ответить

Petr

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

Эта задача меня проперла!

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

Из этого кстати видно, что каждое ребро нужно использовать 1 или 2 раза - если 3, то заменим на 1 и ничего не изменится.

Ну а теперь уже простая динамика для того чтобы понять, 1 или 2: какая минимальная суммарная длина взятых ребер (с учетом кратности), если в поддереве с корнем в V ровно K нечетных вершин.

→ Ответить

Petr	14 лет назад, # ^ \| 0 Почитал едиториал - там сложнее гораздо объясняется ) → Ответить

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

А я и не заметил что мои два параметра - это остаток и результат деления на 2 твоего K, кстати по коду это заметно :)
k =k1+k2+(s1+s2)/2;
s = (s1+s2)%2;

→ Ответить

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

Я блин провтыкал, что в 500 надо чоединять числа из разных строк. В результате у меня были числа 19 и 5, а не 195 в последнем примере... Обидно шо капец. Особенно если сейчас в практис руме пройдет.

→ Ответить

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

Блин. Прошла.

→ Ответить

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

Так сэмпл же не проходил?

→ Ответить

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

Так да. Я и не сдавал, а сидел искал баг. Так и не нашел. Уже после челленджа меня Igel_SK просветил по поводу последнего примера.

→ Ответить

Egor	14 лет назад, # ^ \| +5 Читать комменты к семплам - это папство, да → Ответить

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

Я не спорю, это моя вина. Но согласитесь, обидно не сдавать задачу из-за такой мелочи.

→ Ответить

freopen

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

Вот из комментов как раз не сильно становится понятно. Раньше сказали соединить и тут сказали. Как соединить - никто не сказал. Хотя конечно да - самое буквальное понимание - верное

→ Ответить

mastersobg

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

Тоже долго втыкал про 3-й тест. Почти под конец догадался. Зашла:)

→ Ответить

freopen

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

А вот у меня не зашла. Глюк в Куне :(

→ Ответить

Ripatti

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

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

→ Ответить

mr146

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

Хм, я из-за этого много времени убил. Потом таки прочитал, что надо сконкатенировать строки.

→ Ответить

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

Забавно :)

→ Ответить

AlexSkidanov

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

После матча всегда Score обновляется раньше чем сортировка
Но при этом можно отсортировать список по Score, и лапками посчитать свое место :о)

→ Ответить

DELETED02

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

Подскажите плз как решать 3-ию во 2-ом див.

→ Ответить

KADR

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

Если ни одно письмо не пришло по назначению, то така перестановка называется беспорядком пордка n. Затем, если ровно одно письмо пришло по назначению, то зафиксируем его и останется беспорядок порядка n-1. Если f(n) - количество беспорядков порядка n, то ответ это f(n-k)+f(n-k+1)+...+f(n). Теперь покажем как посчитать f(n).

Пускай p(S) равно количеству перестановок, у которых элементы множества S стоят на своих местах, а все остальные элементы стоят как угодно. По принципу включения-исключения имеем:

f(n)=n!-p({1})-p({2})-...-p({n})+p({1,2})+...+p({n-1,n})-...+(-1)ⁿp({1,2,...,n})=n!-n*(n-1)+n*(n-1)*(n-2)!/2-n*(n-1)*(n-2)*(n-3)!/3!+...+(-1)ⁿ=n!-n!/1+n!/2-n!/3+...+(-1)ⁿn!/n!. Отсюда видно, что посчитать количество беспорядков порядка n можно за O(n), если предварительно предпосчитать факториалы и обратные факториалы. Отсюда следует решение за O(n²).

Можно решить еще быстрее, если вынести за скобки n! и предпосчитать для k от 1 до n суммы вида 1-1/1+1/2-...+(-1)^k1/k!. В таком случае сложность решения получится O(n+k).

→ Ответить

it4.kp

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

еще можно так: f(n) = (n - 1) * (f(n - 1) + f(n - 2))

→ Ответить

http://www.topcoder.com/stat?c=problem_solution&rm=305324&rd=14157&pm=10766&cr=22685398

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

Включение-исключение:
C[K][0]*A[0] - C[K][1]*A[1] + C[K][2]*A[2] +C[K][3]*A[3] + ... - где A[i] - сколько вариантов таких что i фиксированных министров среди этих K получили получили свои письма, т.е. A[i] = (N-i)!
Попробуем упростить C[K][i]*A[i] = mul(i, K) * mul(K-i, N-i) где mul(a,b ) это b!/a! = (a+1)*...*b, легко выделить в отдельную функцию.

→ Ответить

frost_nova

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

Кто сможет найти баг в этом решени на 500-ку?

Забавно, что оно прошло самплы и довольно много сист. тестов, но не все :)

→ Ответить