Has anyone made backup copies of the USACO training problems, just in case the site goes down?
For storing an adjacency list with edge weights, the (apparently) standard way is to store a vector of vector of pairs (vertex end, weight). I realized recently that it is possible to store the adjacency list as for an unweighted graph and store the edge weights separately (in a map or unordered map). noedne pointed out that storing the weight in the adjacency list is more organized. In theory by storing the edge weights separately we can reuse algorithms for unweighted graphs that take the unweighted adjacency list.
Which do you think is better?
If you are like me you probably have a favorite set of compiler flags, and you use Ctrl-R or press up a few times in the terminal to get the command used for compiling, and then you change the source file and binary name in the command to the right names. (Or you are not like me and hit the compile button in your IDE.) This works fine but always searching for the command and changing the file names is a little annoying.
The standard solution for doing the same compilation commands over and over is make, but usually makefiles are for projects with a few predetermined targets (generating one main binary), while competition programming is a unique environment where we need to create many binaries, one from each source file. I recently discovered that makefiles can pattern match (yes I am a make noob) so we can compile arbitrary files. In short:
% : %.cpp $$$(CXX) $$$(CXXFLAGS) -o $$$@ $$$<
(There should only be one dollar sign in each term. For some reason CF blogs render a single dollar sign in block code as 3.)
To use the makefile we simply provide the path to the program without the file extension.
make -a will generate binary
a from source
a.cpp, and use
-f ../Makefile if assuming the Makefile is in the root directory one level above. Unfortunately the target does not tab-complete in the shell. This is only marginally easier than compiling normally but it is an option.
Interesting to see the overlap in users and countries represented between sites. Since the last time I checked, a certain Gennady from Belarus is now in the top ranking.