Состоится в среду, 21.01.2009 в 19:00 по Москве.
TopCoder SRM 433
Страница: 1
Сообщений 1 страница 23 из 23
Поделиться22009-01-21 17:46:39
Че-то пока никого не видно...
Поделиться32009-01-21 18:06:58
Хм. А на снарке написано, что в 19-00
Поделиться42009-01-21 18:21:27
Да, точно в 19-00 по Москве:
Ср янв 21, 4:00 PM MSK REGISTRATION
Ср янв 21, 7:00 PM MSK CODING
Ср янв 21, 8:15 PM MSK INTERMISSION
Ср янв 21, 8:20 PM MSK CHALLENGE
Ср янв 21, 8:35 PM MSK SYSTEM TEST
Поделиться52009-01-21 18:32:53
Хз откуда 21:30 взялось. =) Мож не в той строчке посмотрел? 
Удачи всем. =)
Поделиться62009-01-21 21:53:28
Бугога. Поздравьте мну, на следующем СРМе буду боянчеги решать. Ибо на этом ушел в минус, и вывалилсо во второй див. 
Поделиться72009-01-22 09:13:08
А меня можно поздравить с покраснением 
Поделиться82009-01-22 10:40:35
Поздравляю, это здорово!
Че-то я обложался на этом срме. Я откровенно перенервничал и не понял условие первой задачи, я почему-то второе предложения принял не как объяснение сдвига, а как объяснение равенства двух строк, при этом подумал вокак извратили... И главное с таким пониманием у меня проходили почти все тесты, кроме двух. Поэтому я был уверен в том что правильно понял. Надо было ее кинуть и ко второй перейти, она оказалась понятней... А так я тоже сменил цвет, и стал синим... Все ни как не удается желтым побыть больше 2х срмов подряд 
....
Поделиться92009-01-22 14:04:53
Поздравляю!
У меня тоже извечная проблема. Без английского пытаться задачи по тестам понять... - зло. На первую я написал какую - то огромную дурь, но сабмитить не стал она падала по ТЛЕ на моём тесте. Самое прикольное, что я даже сейчас не знаю как её решать. 
Поделиться102009-01-22 14:23:05
Чтобы первую решать, желательно что-нибудь по строкам знать - хэши, префикс-функцию или z-функцию. Хотя некоторые и без этого решали, там есть ещё решение за неплохую асимптотику, небольшое улучшение тривиального решения.
А насчёт английского - тут просто практика нужна. Мне здорово помогло решение проблемсетов на английском языке. Но понимать задачи по тестам - правда большое зло
Поделиться112009-01-22 15:30:24
Я не совсем точно выразился. Я знаю как решать - и про хеш, и про префикс-функцию, просто я никогда их не реализовывал - у меня в команде 2 кодера, которые это могут написать, и от меня это пока не требовалось.
Поделиться122009-01-22 17:41:37
Я как раз ее тривиально и решал ... ПОясните пожалуйста как ее по-умному решать?
Особенно интересует решение Петра Митречева ...
Поделиться132009-01-22 18:30:58
atimofeyev
1) Сгенерировать все перестановки -> 8! -> 40320 штук
2) Для каждой строки определить количество циклических сдвигов, равных строке. Очевидно, что за О(n*n) мы это сделать не успеваем, зато есть
много способов сделать это за О(n+n)
e-maxx
Рассматривал твоё решение.
Меня поражает, как ты испульзуешь массив переполнившихся Int64 =)
Ведь по сути получается рандомизатор какой-то. =)
Код:
vector<long long> pw (1000);
pw[0] = 1;
for (int i=1; i<1000; ++i)
pw[i] = pw[i-1] * base;Почему это работает?
Поделиться142009-01-22 20:26:52
Ktulhu
Это обычное применение хэша. Просто очень часто говорят, что хэши по модулю надо брать, однако на самом деле - почему бы нам не взять их по модулю 2^64, т.е. попросто забить на модули?
Во-первых, это очень быстро работает, т.к. делений не нужно. Во-вторых, на практике это даёт результат не худший, чем "правильные" хэши с взятием по простым модулям. Ни разу у меня не было, чтобы вот такой хэш у меня давал плохие коллизии и не проходил.
Поделиться152009-01-22 20:29:35
Единственный аргумент за взятие по простому модулю - чтобы потом можно было выполнять обратную к умножению операцию, - деление по модулю. Но на практике почти всегда можно этого деления избежать, как например в этой задаче - при сравнении h1 и h умножаем h на нужную степень вместо деления h1.
Поделиться162009-01-22 20:42:49
А у Пети да, интересное решение. Если отбросить генерацию всех перестановок, то останется:
Код:
private bool nice(string p, int K)
{
int delta = (p.Substring(1) + p).IndexOf(p) + 1;
return K * delta == p.Length;
}Т.е. если строка S встретилась в строке S+S где-нибудь в позиции I (0-индексация; начало не считаем), то она также встретилась и в 2*I, потом 3*I, и т.д. Всего получится S.length()/I вхождений (причём поделится нацело, иначе бы это противоречило тому, что с S.length()-ой позиции начинается новый экземпляр строки S).
Поделиться172009-01-23 12:16:31
Ktulhu написал(а):
2) Для каждой строки определить количество циклических сдвигов, равных строке. Очевидно, что за О(n*n) мы это сделать не успеваем, зато есть
много способов сделать это за О(n+n)
Можно линк на это множество методов?
ЗЫ: по поводу О(n*n). Если не знать метода за O(n+n), то можно заметить что если одна пермутация генерит волшебное число, то и все пермутации получаемые циклическим сдвигом, тоже будут волшебными, поэтому для тех ограничений которые даны в задачи этот тривиальный подход укладывается по времени...
Отредактировано atimofeyev (2009-01-23 12:19:12)
Поделиться182009-01-23 12:43:05
e-maxx написал(а):
Т.е. если строка S встретилась в строке S+S где-нибудь в позиции I (0-индексация; начало не считаем), то она также встретилась и в 2*I, потом 3*I, и т.д. Всего получится S.length()/I вхождений (причём поделится нацело, иначе бы это противоречило тому, что с S.length()-ой позиции начинается новый экземпляр строки S).
Спасибо, я тока щас допер до решения Петра. Супер. Все так просто, блин. Ну что знатоки алгоритмов, что скажете - это укладывается в какой-нидь из известных стандартных алгоритмов О(n+n), или это гений чистой красоты ?
Поделиться192009-01-23 12:51:25
atimofeyev
Можно линк на это множество методов?
Я уже упоминал здесь - хэши, z-функция, префикс-функция. Последние две вещи у многих даже в шаблончике уже есть, если хорошо понимать, то их писать в несколько строчек. У меня склонность вообще везде хэши использовать, где это только возможно
Спасибо, я тока щас допер до решения Петра. Супер. Все так просто, блин. Ну что знатоки алгоритмов, что скажете - это укладывается в какой-нидь из известных стандартных алгоритмов О(n+n), или это гений чистой красоты?
То, что ты описал в предыдущем посте - вроде и есть решение Петра
Безусловно, это не относится к стандартным алгоритмам на строки, но я думаю, Петру этот трюк был уже известен до контеста, всё-таки в режиме топкодера тратить время на придумывание более красивых решений накладно
Поделиться202009-01-23 12:57:22
Ну а то что Петя - гений, известно всем и так
Поделиться212009-01-23 14:59:44
Ни в коем случае не подвергал это никаким сомнениям !
Поделиться222009-01-24 11:12:22
e-maxx написал(а):
Я уже упоминал здесь - хэши, z-функция, префикс-функция. Последние две вещи у многих даже в шаблончике уже есть, если хорошо понимать, то их писать в несколько строчек. У меня склонность вообще везде хэши использовать, где это только возможно
Да, стыд и позор... Гляжу в кнгу - вижу фигу ... Все это читал когда-то да вот в полевых условиях не применял и забыл 
...
Меня только вот что удивляет: неужели тебе не страшно что хеши могут не сработать?
Поделиться232009-01-24 14:32:46
atimofeyev
Меня только вот что удивляет: неужели тебе не страшно что хеши могут не сработать?
Ну на таких коротких строчках - почему-то есть уверенность, что такого теста не будет. Хотя вон Петя для интовых хэшей во время челленджа находил коллизии
В общем, у меня ещё не было случая, чтобы int64-й хэш не проходил в задаче из-за коллизий, а с int'овым - кучу раз было. Вот такая магия
А префикс-функция - в принципе, довольно простая вещь, и при этом имеет немало применений. Сам не знаю, почему я её редко использую, она ведь по размеру кода даже короче хэшей получится
Страница: 1