Your solution is same as mine. Only difference is that I am traversing test string backward and using hash map to improve running time.
You can improve the running time of your code by avoiding inner loop which traverse 0 to 18. We can keep each distinct characters of target string "welcome to code jam" in the hash map as a key and value for the key will be the array holding respective positions in the target string. So while traversing outer loop for test string you just need to check whether the character is available in the hash map. If it is not then no need to traverse inner loop. But if the character exist then just need to traverse it's respective positions (retrieve array values corresponding to that key) only. You can check my solution user "sam6230i". My solution is in JAVA. On Fri, Sep 4, 2009 at 1:44 PM, smloh <[email protected]> wrote: > > I'm going to try to provide an intuitive explanation of the logic I > used for Problem C, in the hope it may help some fellow programmers. > > First the code, in old-fashioned C: > #include <stdio.h> > #include <stdlib.h> > #include <string.h> > int main(int argc,char *argv[]) > { > char *wstr="welcome to code jam"; > FILE * pFile, *pOut; > char buffer [600]; > int mults[19]; > int numCases; > pFile = fopen ("c-large.in" , "r"); > pOut= fopen("c-large.out","w"); > if (pFile == NULL) perror ("Error opening file"); > else > { > fscanf(pFile, "%d\n", &numCases); > for (int num=0;num<numCases;num++) > { > fgets(buffer, 600, pFile); > for (int i=0;i<19;i++) mults[i]=0; > fprintf(pOut,"Case #%d: ",num+1); > int len=strlen(buffer); > for (int i=0;i<len;i++){ > for (int j=0;j<19;j++){ > if (j==0) { > if (buffer[i]==wstr[j]) mults[j]++; > }else if (mults[j-1]>0){ > if (buffer[i]==wstr[j]) > mults[j]=(mults[j]+mults[j-1])%10000; > } > } > } > if (mults[18]<1000) fprintf(pOut,"0"); > if (mults[18]<100) fprintf(pOut,"0"); > if (mults[18]<10) fprintf(pOut,"0"); > fprintf(pOut,"%d\n",mults[18]); > } > fclose (pFile); > } > return 0; > } > > > Explanation: > Let's call the string we are testing the "test string", and "welcome > to code jam" the "target string". > > For each test case, the outer loop of this algorithm iterates over the > test string, which is stored in buffer[]. The inner loop iterates > over the target string, which is stored in wstr[]. > > As we go over the test string, we keep track of a number mults[j] for > each character in the target string. > This is defined as: > > mults[j] = the number of ways to build the target string up to the jth > character, using the characters in the test string we have evaluated > so far > * to correlate to the code, "jth character" counts from 0 > > Intuitively, we can describe mults[j] as the number of ways to "get > to" the jth character in "welcome to code jam" that we have found so > far. > > When j==0, each time we encounter a character match ("buffer[i]==wstr > [j]"), we increment mults[0] by 1, since we have 1 more potential > first character for our target string. > > When j>0, each time we encounter a match, we increment mults[j] by > mults[j-1]. > > This is because there are mults[j-1] ways so far to form the target > string up (j-1)th character. Each of these ways, when combined with > the character in we are currently evaluating, gives us a new way to > form the target string up to the jth character. > > We also mod(%) the calculations by 10000, since only the values less > than 10000 at each step affect the last 4 digits of our final result. > > When we are done iterating over the entire test string, mults[18] > will, by definition, be the number of ways to build the entire target > string, using the characters in the entire test string. > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
