Monday, May 16, 2016

Topcoder problem analysis - A new hope

Intro

Off late, I've started practising topcoder problems to get better at problem solving. I'm in no state to compete in SRMs right now, but I'll try to practice as often as possible, till I feel up to it.
I'd never ever solved a 1000 pointer before, in any amount of time. But I managed to solve a couple, albeit taking a lot of time.
My intent was not to just get code to work, but write good idiomatic C++, with some amount of terseness.


Setup

The first thing I noticed is that the topcoder beta arena based on HTML really sucks. It doesn't let you browse problems by SRM and as far as I could tell, there is no way to see other peoples solutions. The good old Java applet still works, and I guess it will continue to work because it remains in production, so thank goodness for that.

The first thing to do is to configure a good editor plugin - I used to use FileEdit and TZTester before, but Greed seems like the best thing to use right now. It also downloads the problem descriptions and is highly configurable. So far I haven't been able to get it to generate automated test code, but that's probably because the problems I opened are from very early matches, where the test cases are not specified in a standard form which the plugin can parse.

The next thing is what template to use - as usual, a bunch of macros.
This is what I have right now:


Just a bunch of macros borrowed from many topcoder contestants. all() is probably the most useful, followed by FOR(), and P() is invaluable while debugging. Most of them just reduce verbosity and avoid typos. One has to be careful to use macro names that are not identifiers, otherwise you can get some horrendous errors.


Modus operandi

My goal is not to try to write code as fast as possible. It is to try to write the best (by my taste) C++ for each problem. This means that I will try my best to refine a solution once I get it to work, or try to write it in a refined STL centric manner from the get go.

In future posts I will try to dissect each problem, algorithmically and code wise, and try to show how best to leverage C++.

Ideally I would like to see myself writing code in the very first iteration, that looks like the last iteration I produce now, after much refinement.

In a contest situation, some of the code I write is not ideal, since in a contest, cleanliness of code is irrelevant, as is code duplication. If anything some contestants write code in a purposely obscure manner to thwart others from grokking the code.

For practice purposes, I'd rather write elegant code. Some terseness and one-lining is nice though as code golf.
I do not adhere strictly to my variable naming convention, since it leads to come verbosity. I also break some whitespace rules to make the code look compact.
A supplementary library of code is getting accumulated as I do these problems, since some things are patterns that repeat.
I will discuss those bits of code in future posts.


No comments:

Post a Comment