TopCoder SRM 627 - Codeforces

Блог пользователя chrome

TopCoder SRM 627

Автор chrome, 10 лет назад, По-русски

Всем привет!

Завтра, в 19.00 MSK состоится Topcoder SRM 627.

Предлагаю после контеста обсудить здесь задачи.

GL & HF

UPD: Контест закончился.

UPD2: Участники 2 дивизиона, которые сдавали задачу В на питоне, можно попросить сделать контест нерейтинговым. Так как попытки по задаче В не будут сочтены для питона.

srm, tc, announcement, topcoder, single round match, top coder schedule

chrome
10 лет назад
29

Комментарии (28)

Показать архивные | Написать комментарий?

SlavaSSU

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

О нормал! Я и не знал(До этого по snarknews.info ориентировался, но сейчас там нету в расписании СРМов)

→ Ответить

Temirulan

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

← Rev. 2 →

Можно еще по clist.by ориентироваться.

→ Ответить

BanderLog

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

Первое место уже забито

→ Ответить

IDont_love_TanyaRomanova

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

-14

с конца

→ Ответить

Rubanenko

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

-10

Нужно определенно запилить себе prewritten поток.

→ Ответить

subscriber

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

+33

А как сеть построить? Я дошел только до того, что если есть только единички, то получается независимое множество.

→ Ответить

Rubanenko

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

← Rev. 2 →

-51

Вершинами будут все клетки поля. Из стока проведем в каждую башню понятно что. Сделаем копии пустых клеток, которые соответствуют состояниям "поток пришел слева", "..справа" и т. д. Из каждой башни в след клетку по направлению ее пушки проведем ребро. Из клеток с цифрами прведем ребра в сток с соотв. ценой.

→ Ответить

subscriber

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

+45

Как-то сомнительно) как будут запрещаться пересечения? если пускать клетки слева и сверху через одно ребро, то пути смогут заворачивать. Можно подробнее?

→ Ответить

Rubanenko

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

-9

Точно,ты прав, там понятно как банились пересечения, но я не учел появление поворотов.

→ Ответить

tourist

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

+116

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

>...1.4...36.

нарисуем отрезки:

XXXXX........ -- стоимостью 1
XXXXXXX...... -- стоимостью 3
XXXXXXXXXXXX. -- стоимостью 2

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

→ Ответить

qwerty787788

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

+37

А еще из-за того, что стоимости маленькие, можно не искать поток, а просто добавить каждый отрезок его стоимость раз и найти парасочетание.

→ Ответить

Petr

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

+29

Можно еще пойти в обратную сторону: если искать поток, то можно сделать граф с N**2 ребер вместо N**4.

→ Ответить

nekrald

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

Буду благодарен, если кто-нибудь расскажет решение для Div1 500.

→ Ответить

Rubanenko

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

Всего есть не более двух путей между любой парой вершин. Давайте пустим из каждой вершины дфс, и найдем все пути от нее до остальных, пересчитывая ответ. Потом сделаем то же самое, только ребра в обратном порядке смотреть будем, чтобы дфс пошел в другом направлении, при входе в цикл. Надеюсь, я не ошибаюсь :)

→ Ответить

Gassa

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

← Rev. 2 →

+29

Можно вместо двух поисков в глубину сделать один полный перебор (отличие — снимать метки при выходе из рекурсии). Он обойдёт в точности те же два пути до каждой вершины.

→ Ответить

Edvard

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

Между любой парой вершин в таком графе не более двух путей. Так что из каждой вершины запускаем перебор, а внутри поддерживаем суммы на префиксах меток вершин.

→ Ответить

HASP

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

← Rev. 3 →

-10

В div2 1000 жадник — это верное решение? Я закодил такую вещь: сделаем K итераций, на каждой итерации переберем все подотрезки массива и найдем такой максимум, что разность количества инверсий в текущем подмассиве и перевернутом — максимальная. В конце перевернем этот найденный подмассив и посчитаем новое число инверсий во всем массиве, если оно стало меньше, то оставляем, иначе — конец алгоритма.

upd: не зашло :(

→ Ответить

tunyash

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

А кто-нибудь умеет вбивать большие тесты в арену? Я увидел кублог по 500. Я измерил скорость, с которой я ввожу в это окошко числа. Мне понадобилось бы минут 20, чтобы вбить большой тест. Может, можно как-то удобно вводить массивы, чтобы тесты можно было таки генерировать?

→ Ответить

I_love_Tanya_Romanova

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

← Rev. 3 →

+18

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

Например, как-то так делаем:

for (int i=0;i<10;i++)
{ if (i)cout<<",";cout<<i;}
cout<<endl;

потом в окошке, где нужно вектор ввести — вводим наш аутпут и жмем на {}

Или я неправильно понял проблему?

(offtop) а кублог таймит?) Я случайно n^4 заслал, так он почти все тесты проходит) Сейчас попробую кублог)

→ Ответить

tunyash

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

Ого, спасибо, здорово.

Там, вроде, был явный кублог, мне казалось, что ему не суждено зайти на тест, размера 1000. А как делать осмысленный n^4?

→ Ответить

I_love_Tanya_Romanova

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

← Rev. 2 →

Перебираем все хорошие пути, их квадрат. Каждый путь строим в явном виде полностью, и за квадрат длины считаем инверсии. Получается n^4.

Сейчас дописал туда фенвика, чтобы считать число инверсий за nlogn, 173/175 в практисе проходит с временем <=0.3, дальше ТЛ) Стало интересно — пройдет ли, если переписать тот же бред немного более аккуратно.

upd. теперь 1.78 на тесте №169 и 174/175 в итоге)

→ Ответить

indy256

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

У меня реализация на Java за $\text{[math]}$ в практисе прошла за 1.9с только с добавлением отсечения по ответу.

→ Ответить

I_love_Tanya_Romanova

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

← Rev. 2 →

Отсечение по ответу рулит, учитывая то, что у них только 2 теста, более-менее похожих на худший возможный; и в том из них, который намного хуже другого — ответ 0)))

Upd. System> LeBron successfully challenged indy256's 500-point problem.

→ Ответить

olive

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

← Rev. 2 →

Sorry, moved to English thread

→ Ответить

olive

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

Can someone give me any ideas about Div2 1000?

Thanks

→ Ответить

faiyaz26

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

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

→ Ответить