[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Using Lua in programming contests
- From: Coda Highland <chighland@...>
- Date: Thu, 5 Jan 2017 13:25:08 -0800
On Fri, Jan 6, 2017 at 12:22 AM, Martin <firstname.lastname@example.org> wrote:
> On 17-01-05 12:59 PM, Coda Highland wrote:
>> In Pascal and C you can get away with a linear array of key-value
>> pairs instead of using a hash table, because the underlying
>> performance is orders of magnitude higher than an interpreted
>> language. You could also use a binary tree instead of a hash table,
>> which is a much simpler implementation than a hash table while still
>> being faster than a linear array.
>> The whole point is that you don't have to use the most efficient
>> algorithm available to you when you're getting compiled to optimized
>> machine code; you can just brute force your way through it with
>> something good enough.
>> /s/ Adam
> Agree. In "real world" this is true. (Although brute-force solutions
> have horrible scalability.)
> But in programming contests mentioned scaling coefficients are used to
> equalize solutions in different languages. This is done because contest
> problems are not about minimal runtime but about most effective algorithm.
That was part of my point -- the scaling factor was specifically
BECAUSE you have the luxury of doing that, and therefore the challenge
has to be stricter in order to push the best-in-class solutions.
(Of course, in C++ you have hashtables in the standard library.)