Ah, sorry I did not notice that before, Sameer. Nice code!
Glad you worked out your problem, Vitus. It might have just been an
old file or something like that.
Good luck on the next round, everyone!
On Sep 8, 2:39 am, sameer mhatre <sam77...@gmail.com> wrote:
> Yes smloh you are right. Hash map does not return objects in order they
> inserted. Thats why I have used Array List inside hash map. I have made
> <Character, ArrayList> pair inside hash map. The Character key will hold all
> distinct characters from "welcome to google code jam" string. The
> corresponding value for the each Characters is a ArrayList (which is also a
> Collection) in which I am adding that Character locations one by one in the
> descending order (as I am processing test string from right to left then the
> second 'o' should get processed before first 'o'). So while processing each
> characters from test string, I m just retrieving Array List for the
> character using hash map and traversing it for further process. I have used
> Array List because it is definitely going to return positions in order I
> have inserted ie. desceding order.
>
> This is my code snippet:
>
> final int MOD = 10000;
> int N = Integer.parseInt(reader.readLine());
> String welcome = "welcome to code jam";
>
> HashMap<Character,ArrayList<Integer>> map = new
> HashMap<Character,ArrayList<Integer>>();
>
> for(int i = welcome.length() - 1; i >= 0; i--){
> char ch = welcome.charAt(i);
> if(map.containsKey(ch)){
> ArrayList<Integer> get = map.get(ch);
> get.add(i);
> }else{
> ArrayList<Integer> te = new ArrayList<Integer>();
> te.add(i);
> map.put(ch, te);
> }
> }
>
> long [] mul = new long[welcome.length()];
>
> for(int i = 1; i <= N; i++){
> String line = reader.readLine();
> Arrays.fill(mul, 0);
>
> for(int j = line.length() - 1; j >= 0; j--){
> char ch = line.charAt(j);
> if(map.containsKey(ch)){
> ArrayList<Integer> get = map.get(ch);
> for(Iterator iter = get.iterator(); iter.hasNext();){
> int col = (Integer)iter.next();
> if(col < welcome.length()-1){
> mul[col] = (mul[col] + mul[col+1]) % MOD;
> }else if(col == welcome.length()-1){
> mul[col]++;
> }
> }
> }
> }
> out.printf("Case #%d: %04d\n",i,mul[0]);
> }
>
> On Mon, Sep 7, 2009 at 9:37 PM, smloh <shanming....@gmail.com> wrote:
>
> > Love that optimization, Sameer. Great example of replacing what is
> > basically an inefficient linear-time search in the inner loop with the
> > magic of hash tables for a usually constant-time performance.
> > Although would need to make sure to be a little careful when using
> > this technique for other similar problems, as I don't think the hash
> > map guarantees you'll get the characters back in the same order
> > they're put in. If the target string had two adjacent repeated
> > characters (like if it said "welcome to google code jam"), then would
> > need to ensure the first 'o' is processed before the second one.
>
> > On Sep 6, 3:03 am, sameer mhatre <sam77...@gmail.com> 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 <shanming....@gmail.com> 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 google-code@googlegroups.com
To unsubscribe from this group, send email to
google-code+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/google-code?hl=en
-~----------~----~----~----~------~----~------~--~---
