your method is same as what explained in code jam solution page, the solution there use previous row to calculate current row, hence, in nutshell, one can just keep 1D array of row.
2009/9/10 mogo <[email protected]> > My solution is under nickname "mogo" in the qualification round if you > want to have a look. The only thing that I save is a single dimension > array of length 19. > > The solution to this problem is based dynamic programming and here's a > short explanation of the way it works: > > The first thing that you have to notice is that if you know the number > of occurences of each substring 0..k from the key ("welcome to > codejam") in a string s1 then there's a simple (recurrent) formula to > compute the number of occurences for each substring 1..k in s1+c where > c is a single caracter. So you add once char and compute the new > values for it. > > Here's an example for you to understand: > > The substrings 0..k from the string "welcome to codejam" that I was > talking about are: > k=0 "w" > k=1 "we" > k=2 "wel" > k=3 "welc" > .... > k=16 "welcome to codeja" > k=17 "welcome to codejam" > > The recurrent formula is: > if(c == key[0]) //where key is the key string "welcome to codejam" > nr[0]++; > if(c == key[j]) > nr[j]+=nr[j-1]; > > To explain the formula here's an example of how it works: > > let s1 = "test w test el" > let c = 'l' //small L > we know that: > nr[0] = 1 // the number of 'w' letters in s1 (on position 5) > nr[1] = 2 // the number of "we" substrings in s1 (postitions 5, 8 and > 5, 12) > nr[2] = 2 // the number of "wel" substrings in s1 (5, 8, 13 and 5, 12, > 13) > nr[3] = ... = nr[17] = 0 > > Now if we add another 'l' to s1 then we'll get that > nr[0] = 1 // same number of w > nr[1] = 2 // same number of we > nr[2] = 4 // because key[2] = 'l' = c we know that for each substring > "we" that we were able to generate from s1 we will also be able to > generate a "wel" substring using letter c now. > > After you understand the idea, implementation becomes very > straghtforward. > > > > On Sep 9, 12:34 am, Misha Marchenko <[email protected]> wrote: > > Кажется у меня появилась идея как это можно сделать, нужно будет > попробывать > > > > 9 сентября 2009 г. 10:33 пользователь romanr <[email protected]> > написал: > > > > > > > > > По идее разбиваем строку на голову и хвост. > > > Так вот обрати внимание: часто приходятся решать задачу для той-же > самой > > > головы и хвоста. > > > Вот этот результат и закешируй. > > > Можешь как кеш использовать двумерный массив с индексами в которых > > > разбивается на голову и хвост текст и искомая строка, > > > или хешируйся по конкатенации хвостов текста и искомой строки. > > > > > Misha Marchenko wrote: > > > > > Решал на жаве в лоб, без кеширования. Что к данной задаче будет > > > кешированием? > > > > > 8 сентября 2009 г. 21:49 пользователь romanr <[email protected]> > написал: > > > > >> Решай "в лоб" с кешированием - это называется "динамическое > > >> программирование". > > > > >> Misha Marchenko wrote: > > > > >> Смотрел. Мне интереснее какой алгоритм был использован, какого его > > >> название? В том году я узнал, например, про венгерский алгоритм- Hide > quoted text - > > > > - Show quoted text - > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
