Kerana ini adalah benang pelbagai bahasa, here goes: Walaupun seseorang boleh menggunakan satu baris, dan itulah yang saya lakukan, itu adalah salah secara rasmi. Kaedah rosak jika ada dua surat berturut-turut taip yang sama pada string target. Kalau orang menemukan "Welcome to Google Code Jam", itu akan rosak, namun solusi analisis dalam kontes akan tetap berdiri.
On Sep 11, 1:07 am, Hawston LLH <[email protected]> wrote: > 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 -~----------~----~----~----~------~----~------~--~---
