| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 165 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Всем привет!
Завтра, в 19.00 MSK состоится Topcoder SRM 627.
Предлагаю после контеста обсудить здесь задачи.
GL & HF
UPD: Контест закончился.
UPD2: Участники 2 дивизиона, которые сдавали задачу В на питоне, можно попросить сделать контест нерейтинговым. Так как попытки по задаче В не будут сочтены для питона.
О нормал! Я и не знал(До этого по snarknews.info ориентировался, но сейчас там нету в расписании СРМов)
Можно еще по clist.by ориентироваться.
Первое место уже забито
с конца
Нужно определенно запилить себе prewritten поток.
А как сеть построить? Я дошел только до того, что если есть только единички, то получается независимое множество.
Вершинами будут все клетки поля. Из стока проведем в каждую башню понятно что. Сделаем копии пустых клеток, которые соответствуют состояниям "поток пришел слева", "..справа" и т. д. Из каждой башни в след клетку по направлению ее пушки проведем ребро. Из клеток с цифрами прведем ребра в сток с соотв. ценой.
Как-то сомнительно) как будут запрещаться пересечения? если пускать клетки слева и сверху через одно ребро, то пути смогут заворачивать. Можно подробнее?
Точно,ты прав, там понятно как банились пересечения, но я не учел появление поворотов.
Для каждой башни в её направлении выделим последовательность максимумов. Для каждого максимума нарисуем отрезок между башней и этим максимумом, а стоимостью отрезка назовём разность величин этого максимума и предыдущего. Например, в таком случае:
нарисуем отрезки:
Теперь нужно найти максимальное по стоимости множество отрезков так, чтобы горизонтальные и вертикальные отрезки попарно не пересекались. Это почти то же самое, что наибольшее независимое множество в двудольном графе, только вместо паросочетания нужно искать поток.
А еще из-за того, что стоимости маленькие, можно не искать поток, а просто добавить каждый отрезок его стоимость раз и найти парасочетание.
Можно еще пойти в обратную сторону: если искать поток, то можно сделать граф с N**2 ребер вместо N**4.
Буду благодарен, если кто-нибудь расскажет решение для Div1 500.
Всего есть не более двух путей между любой парой вершин. Давайте пустим из каждой вершины дфс, и найдем все пути от нее до остальных, пересчитывая ответ. Потом сделаем то же самое, только ребра в обратном порядке смотреть будем, чтобы дфс пошел в другом направлении, при входе в цикл. Надеюсь, я не ошибаюсь :)
Можно вместо двух поисков в глубину сделать один полный перебор (отличие — снимать метки при выходе из рекурсии). Он обойдёт в точности те же два пути до каждой вершины.
Между любой парой вершин в таком графе не более двух путей. Так что из каждой вершины запускаем перебор, а внутри поддерживаем суммы на префиксах меток вершин.
В div2 1000 жадник — это верное решение? Я закодил такую вещь: сделаем K итераций, на каждой итерации переберем все подотрезки массива и найдем такой максимум, что разность количества инверсий в текущем подмассиве и перевернутом — максимальная. В конце перевернем этот найденный подмассив и посчитаем новое число инверсий во всем массиве, если оно стало меньше, то оставляем, иначе — конец алгоритма.
upd: не зашло :(
А кто-нибудь умеет вбивать большие тесты в арену? Я увидел кублог по 500. Я измерил скорость, с которой я ввожу в это окошко числа. Мне понадобилось бы минут 20, чтобы вбить большой тест. Может, можно как-то удобно вводить массивы, чтобы тесты можно было таки генерировать?
Пишем на своем родном языке генератор, который выводит нужный нам тест в какой-нибудь файлик (примерно так, как обычно генерируют массивы с константами прекалька), копируем оттуда.
Например, как-то так делаем:
потом в окошке, где нужно вектор ввести — вводим наш аутпут и жмем на {}
Или я неправильно понял проблему?
(offtop) а кублог таймит?) Я случайно n^4 заслал, так он почти все тесты проходит) Сейчас попробую кублог)
Ого, спасибо, здорово.
Там, вроде, был явный кублог, мне казалось, что ему не суждено зайти на тест, размера 1000. А как делать осмысленный n^4?
Перебираем все хорошие пути, их квадрат. Каждый путь строим в явном виде полностью, и за квадрат длины считаем инверсии. Получается n^4.
Сейчас дописал туда фенвика, чтобы считать число инверсий за nlogn, 173/175 в практисе проходит с временем <=0.3, дальше ТЛ) Стало интересно — пройдет ли, если переписать тот же бред немного более аккуратно.
upd. теперь 1.78 на тесте №169 и 174/175 в итоге)
У меня реализация на Java за
в практисе прошла за 1.9с только с добавлением отсечения по ответу.
Отсечение по ответу рулит, учитывая то, что у них только 2 теста, более-менее похожих на худший возможный; и в том из них, который намного хуже другого — ответ 0)))
Upd. System> LeBron successfully challenged indy256's 500-point problem.
Sorry, moved to English thread
Can someone give me any ideas about Div2 1000?
Thanks
At first what makes you think that this problem can be solved by DP? Because one can reverse the array with disjoint interval. Ok then what information do i need to solve the problem with DP ?
At first you need to know, that number of bubble sort swaps for an array is equal to the number of inversions in that array. Search on google if you don't know what is inversion of an array !
So with dp we need to minimize the inversions.
So the state will be (index, K) and in the dp body, you will select a range (subarray from the current index) , then for that range count the inversions of normal array and count the inversions after reversing the range. then make a transition to get the minimum.
BTW you can check my code for better understanding: http://pastie.org/9375371
I didn't participate, but can you give more information on UPD2? What happened with problem B and Python?
the return type,
char, is not supported by Python. this makes it impossible to solve the problem.