premature optimization is the root of all evil

[coolgod]

I think this is one of my biggest flaws during major contest, i tend to optimize alot as i write the code. It especially screws me up during DWITE. My teacher says it has screwed numerous other stars in our schools before.
Any any advise or suggestions to help me deal with it? An example was today for DWITE #4 i used a star and made a silly mistake somewhere, got 3/5 and wasted 1.5 hrs. Could have bfsed 5/5 it in like 20 mins.

[A.J]

Would you mind elaborating 'optimize a lot as I write code'? As in, you try to make it memory efficient?

Usually with contests, you want to be aware of the time constraints and the input specs of the problems. For example, on DWITE I never suggest implementing a breadth first search, as a depth first search could as easily solve the problem with the given constraints, and requires (well, most of the time) less code than a breadth first search.

In general though, I would suggest thinking in terms of:

1) The complexity required to solve the problem (by this I mean what is the slowest program that could pass given the constraints).

2) Problem genre. This comes from experience, basically trying to recognize what 'genre' the intended solution falls under

3) Determining an Algorithm. Arguably the most challenging part. Come up with an algorithm (or implement a known one) to solve your problem

4) Implement your Algorithm. This is the part you want to try saving some precious time on, though not at the expense of complexity

But I guess its always a learning curve. DWITE does help a lot with small things like this (so now in the future you'll know to implement a DFS/BFS for pathfinding problems as opposed to an A*, if appropriate).

[coolgod]

Implement your Algorithm. This is the part you want to try saving some precious time on, though not at the expense of complexity <-
The astar today wasn't the best example. I kindda wanted to push myself and see if I could code an a star on the spot.
I mean just in general, optimizing the little details in the code.

[Tony]

coolgod @ Thu Dec 22, 2011 12:31 am wrote:

optimizing the little details in the code.

It might help to realize that a good compiler is better at optimizing than you are. The little details don't matter*, next to high-level algorithm complexity.

* the exception being embedded software where cpu cycles, memory, and space are still at a premium.

[trishume]

This is my favourite programming motto. I use it constantly whenever I am coding anything.

Profiling is the only way to really know what is slow and in contests there is not even time for that.

I still have much to learn though. As a ruby user I automatically dismiss brute force solutions (like many people used for q5.)
I was writing a fancy tree matching boolean algebra simplifier for q5 when another person on my team (ttm) said "That's only about 20,000 possible combinations. C++ could easily brute force that." So he sat down and quickly coded a working brute-force algorithm.