Тема: Google Code Jam Problems
Вот и подошел к концу Qualification Round.
Задача "Alien Language"оказалась простой.
Интересно какие методы существуют для решения задачи "Welcome to Code Jam"? 
Re: Google Code Jam Problems
Зачем было удалять сообщение из старого топика? Получилось, что мой ответ в нем повис не в тему, и его тоже пришлось удалить.
Welcome to Code Jam - стандартная задача на двумерное ДП.
Джеймс Гослинг с нами!
Re: Google Code Jam Problems
Sorry! Заметил после удаления.:(
Так в чем же суть двумерного ДП?
Ведь довольно сложно перебрать все вхождения фразы.
Re: Google Code Jam Problems
Естественно, перебор здесь не катит. 
ДП: подзадача характеризуется 2-мя параметрами.
F(i, j)
i - позиция текущего символа в первой строке (пусть будет s1)
j - позиция текущего символа во второй строке (пусть будет s2)
первая строка - это входные данные, вторая - "welcome to code jam".
Переходы между состояниями
если s1(i) = s2(j), то F(i, j) = F(i + 1, j + 1) + F(i + 1, j);
иначе F(i, j) = F(i + 1, j);
Если j == s2.length(), то F(i, j) = 1;
Если i == s1.length(), то F(i, j) = 0;
Вроде как-то так, может чуток соврал. Ну еще каждый раз ответ брать по модулю 10000, а потом не забыть вывести ведущие нули, если они есть.
Джеймс Гослинг с нами!
Re: Google Code Jam Problems
Большое спасибо!:)