-----------------------------------

A.J

Wed Mar 24, 2010 8:07 pm


Dwite 2010...#5

-----------------------------------

This problem took about 5 minutes to code. My method was similar to everyone else's code: Iterate through every possible 4 letter string. This reasonable, as it is merely 26^4 = 456976 operations.

After submitting the solution to DWITE, I received a score of 0. However, when I ran it on my school computer, it ran for the official cases correctly < 2s. Yet, my code apparently timed out on the judge...

So, as a result, I got 0 on #5, as opposed to 120+. I have done DWITE too many times to have any hope of the rankings being changed after the end of the contest. 

I just want to make sure that this doesn't happen again (though, once again, this could somehow be my mistake....somehow).


-----------------------------------

Dan

Wed Mar 24, 2010 10:52 pm


RE:Dwite 2010...#5

-----------------------------------

As i told you when you PMed me during the contest there is nothing wrong with the judge, your code is just to slow and took longer then 2.5 seconds.

I just manually ran your code on the judge VM several times and timed how long it took and it was always between 7 and 8 seconds.

As a comparison the first place team's code, in the same language and complied using the same compiler, runs in under 1 second on the same VM.

On the surface when comparing the code it does look like there code is less efficient and has a higher complexity, so why is this the case?

The first issue with your code is it uses recursion to generate the table of hashs, this adds a lot of overhead compared to the for loop method.

Secondly you use strings and string operations rather then a character array which also adds to the overhead of the program.

This actually a great example of how time complexity is not the only factor that effects the speed of your code. Especially when using high level concepts and not fully considering whats going on under the hood.

It's a shame that rather then trying to make your solution faster when i suggested there was a faster solution you decided to only hard code some values and randomly guess at removing some possible hashs for your second submission.


-----------------------------------

A.J

Wed Mar 24, 2010 11:17 pm


RE:Dwite 2010...#5

-----------------------------------

Hmm...I see. Thanks Dan.

Yea, I thought there was a mathematical solution to this problem (I was looking at certain equations modulus some prime numbers, etc...). I didn't realize that the for loop method was any different, and I even considered it, but didn't bother switching as I had already started coding the recursion-permutation method. 

Though, my program ran