Dwite 2010...#5

[A.J]

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]

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]

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 <2s at my school computer, and <1s at my home PC. Why is there such a difference in the execution time (cause you tell me it takes 7 - 8 s to run on the judge)?

[Dan]

We where kind of hoping to see students figgure out they could generate the table on there own computer and then embed it in there code, some what like a rainbow table for MD5 hashs.

The 1st place teams slotuion is also not the most effient submited as they try to burt force each hash rather then making a map or table, however it seems C++ is fast enought when using a for loop for that not to matter.

[A.J]

Yes, I came up with a hashing function the hash(x) function described in #5. But you didn't answer my question. Why does it take a lot longer to execute on the judge? I mean...2s and 7 - 8 s is a big difference.

[Dan]

A.J @ 25th March 2010, 8:28 am wrote:

Yes, I came up with a hashing function the hash(x) function described in #5.

What i mean is run the hash function for all possible values (on your school computer) then embed a hard coded map of them in your code, so it does not have to generate the map (on the judge) when it runs and just check it. It would be ugly but fast.

A.J wrote:

But you didn't answer my question. Why does it take a lot longer to execute on the judge? I mean...2s and 7 - 8 s is a big difference.

It's hard to say, the judge is running in a VM which does have some overhead. If i remember right the VM is assigned a signal CPU core (2.7ghz) and 1GB of ram. However i don't see this as a real negative point as part of the contest is making efficient code.

[A.J]

Well, I did output the mapped values as C++ code....but this took WAY too long to compile (as it was 457000 lines of code or so). So, I thought that might bog down the judge and thought against sending it.

[Tony]

A.J @ Thu Mar 25, 2010 6:57 pm wrote:

as it was 457000 lines of code or so

278776

[A.J]

Oh, you mean if you remove the ones that have more than one value mapped to it? But still, thats too many lines to compile...