Всем привет!
Сегодня авторами задач являемся мы с Романом Едемским (Shtrix). Большое спасибо за помощь в подготовке задач нашему тиммейту Твердохлебу Ярославу, Рахову Артему, Дмитрию Матову и Марии Беловой.
Надеюсь, контест вам понравится!
UPD: Разбор A B C E
UPD: Разбор D
UPD: Поздравляем победителя rng_58!
И чтобы ничего не мешало вам нормально решать =))
Убедительные просьбы:
1) добавить подсветку кода при взломах
2) сделать окно просмотра кода при взломе шире
3) исправить баг со скролом (прокручиваешь вниз эту синюю боковую полосу и вся страница выделяется словно была нажата комбинация Ctrl+A, опять прокручиваешь - исчезает, крутишь - появляется). Opera/9.80 (Windows NT 6.1; U; en) Presto/2.6.30 Version/10.61
Спасибо за внимание и за контест.
Когда такие ошибки были у меня, для меня они были сразу понятны.
Плохо, что нет скроллинкга в этом окошке.
Ну тут же всё ясно. Строка 1 заканчивается пробелом, а не должна.
Не хватает EOLN - конца строки. Ну тут тоже вроде всё ясно.
К тому же был бы этот тест показан, пробелы да переводы строк было бы сложноувидеть.
Будем хранить для каждой вершины суммарный вес ее и всех потомков. Делать это будем в хешмапе, чтобы поддержать разреженность. Общее количество записей в нем максимум 30*100000, что не страшно.
Тогда add делается тривиально бегом к корню.
Теперь смотрим что в расщеплении. рассмотрим какую то вершину, в которую расщепление пришло. Заметим что если одна ветка весит больше другой, то поход в меньшую ветку не интересен, мы его сразу учитываем. Тогда рассмотрим лишь поход в большую, при этом передав туда максимальный размер уже накопленных компонент связности.
Просто тут константа большая получается из за использования HashMap. Там вон внизу писали что TreeMap уже не работал.
Поэтому у меня на пределе прошло по времени, могло и завалиться.
UPD. Хотя у меня проблема со временем была из за слишком неаккуратного обращения с HashMap. Можно было сократить сильно количество обращений.
Во-первых, можно перемножить два числа. Умножаем максимальный размер массива (10000) на количество итераций двоичного поиска (в данном случае хватило бы и тридцати, но пусть даже 200). Получаем два миллиона. Два миллиона раз сложить, умножить и поделить получалось за две секунды ещё на компьютерах десятилетней давности, не то что сейчас.
Во-вторых, можно реализовать, сгенерировать максимальный тест и посмотреть, сколько на нём работает.
Жаль токо ТЛ по Д не 5 секунд а 3, меп надо аккуратно писать..
С порадовала))) но я не сдал..
На Jave с HashMap'ом на моей машине работает ~2.1 секунды, с TreeMap'ом ~3.8
Интересно узнать, у всех пройдёт по В по точности тест:100000 990 0 0 ... 1?бага с рейтом, 2 раза вычтен или прибавлен ))Seems like it's being fixed.
For Problem A, I wrote my code in Ruby and test it on Custom Test to see whether my code gets TLE.
Custom Test reports 970ms as running time for worst input case(997 998 999 1000 0 31415), but my code failed on System test by TLE, though the failed case was just same as my case.
Are there any difference between Custom Test and System test?
Couldn't I trust running time on Custom Test?
Только мне показалась, что по сложности между 3й и 4й большая разница получилась.В итоге после сдачи 3й я час ничего не писал.жаль, что меня так сильно разбажило на С, что я не успел дописать D.
вообще, мне кажется, очень удачный проблем-сет, без мешуры в условиях...
Вот задача C: s - это the first node of the pipe, f - это the second node of the pipe. Специально так, чтоб нерусских с толку сбивать? ;)
just see, how many leaf nodes are reachable from the node where "add" statement is given .
Then add that many items to all the leaf nodes reachable.
Simple :) . (then to produce ans take average..)