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
-~----------~----~----~----~------~----~------~--~---
