hats off to u all .for me , can somebody give a "comprehensive" list of all different currently known techniques of programming . also if possible plz explain me about, from where to prepare questions particular to each technique(branch and bound especially).
On Sep 6, 3:03 am, sameer mhatre <[email protected]> wrote: > 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.- 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 -~----------~----~----~----~------~----~------~--~---
