JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
3.3. Generating Ideas for Your Solution | Reply
The recipe is based on my experience of solving MM problems, so it is naturally limited to the methods I use. If anybody wants to share his methods of generating initial idea of a solution, I'll be more than happy to incorporate them into this recipe - with appropriate attribution.

Edit. Moved the recipe to "3.3. Methods of Solving the Problem".

Problem

You've read and analyzed the problem statement and maybe even launched the visualizer. You understand the problem - now it's time to invent a ways to solve it.

How can one generate ideas for solutions if they don't get one right away?

Solution

The first basic way of generating ideas is to rely on existing human knowledge about this class of problems (or this exact problem, if you're lucky). Almost all Marathon problems rely on something from the writer's experience - a game they played, an article they read, a task they had to manage in their daily life. Thus, it's quite probable to search and find something related to the problem or at least similar to it.

The second way is to play with the problem yourself to study it in detail. Some problems contain non-evident patterns which can give a starting point for the solution.


Discussion

The good thing about Marathons is the amount of time you have: the typical two weeks gives you enough time to think about the problem, dig through Internet in search of similar problems and applicable approaches, try various ideas, reject inefficient ones and finally pick and polish the best one. Sometimes it's totally necessary to try several ideas to get a decent feel of the problem.

Let's have a closer look at the ideas generators and how they can be applied to existing Marathon problems.

1. Rely on existing knowledge of the problem

Like mentioned above, most Marathon problems have some real-life prototype, and sometimes it is already studied in enough detail to provide an idea for your solution. The prototype can be either a known serious problem or a game which was formalized and studied.

Examples of problems which allow using this approach are:

- Planarity is based on a game of same name, which is simpler (it handles only planar graphs) but is in turn based on quite serious researches. Actually, the task is to find the layout of the graph which produces its rectilinear crossing number (or gets as close to is as possible), and r.c.n. is subject to a lot of investigations.
- BookSelection is similar to lots of serious cutting and packing problems - strip or bin packing, container loading, knapsack etc. All of them are easily googleable, so one just has to pick the most similar one (they differ in subtle shades of problem statement) and study its solutions (which are non-trivial but still give a starting point of thought).
- TilesPuzzle is based on Eternity II puzzle, and at least one solution was based on explanation of one of Eternity II solvers.
- Klondike is based on a card game of same name, which is surprisingly well-studied. I got an idea of my solution from an article which describes ways of solving this game with some minor changes in the input data.
- Permute is actually linear ordering problem, subject to plenty of studies as well.

Generally one has to pick out the keywords of the problem and try to google for them in various wordings.

Another version of this approach is reading "Post your approach" for similar old problems or even studying the solutions themselves, though one has to be really desperate for this :-)
A perfect example of this approach are the crypto-marathons which ran in 2008: in OneTimePad Psyho used a very clever method of data compression to fit the necessary data into the size limit of submission, and in following matches it was successfully adopted by many competitors.


2. Play with the problem

Recent visualizers for game-based problems tend to provide "manual" mode - a mode in which it uses information given directly by the user, without his solution. From the user's point of view, this looks like he plays the game and receives a score which his solution would receive if it played in the same way. Older visualizers didn't have this feature, so one had to look for a non-TopCoder implementation of this game.

Regardless of the tool you use, the idea is to try solving the problem by hand and to observe the patterns which you follow when doing it. Automating these patterns can give you at least a draft of a solution. Examples of problems which allow using this approach are:

- ChessPuzzle. After a few games it becomes quite evident that it's better to clear one layer of tiles competly before starting next layer. Another observation (though a one not necessary for a good strategy) is that there are more ways to move to border and corner cells of the board, so they should be left closer to the end of the layer.
- TilesMatching. Playing it can hint that it's important to leave as many places to fit the next tile as possible, regardless of what type it comes in.
- ContinousSameGame. A basic strategy derived from playing the game by hand can be "remove the blocks of all colors except for one, and hope that the blocks of this color form a large group in the end".
RSS