2.) Not a huge deal, but the logic I had for reading from and out to files was unnecessary. I like the idea of just using stdin and stdout - it cuts the program down to what's necessary to solve the problem.

How can I improve my ability to identify subproblems, and realize properties of the problem that allow for it to be build from these smaller subproblems? I guess the solution is to just do more of these types of problems?

Doing many of these types of problems is helpful, but I also think that there are some strategies that can help you make progress more quickly. (There are easy analogies with tsumego here.) I'm not an expert on developing these type of algorithms (hence barely scraping by the qualification round), but I do have a few strategies I apply.

• Try to consider the simplest case. Can you find a situation where the problem becomes trivial? In other words, don't start with the "big problem." Start with the simplest possible problem.
• Expand a bit upon the simple case. Can you reduce a slightly more complex case to the trivial case with a little manipulation? As you increase the complexity of the case, can you find a pattern that emerges? Familiarity with various mathematical progressions can be helpful here, but I suspect that this is one of the areas where practice is very helpful.
• Can you identify a similar problem with a known solution? What kind of algorithms are employed in those problems? (The pancake problem is essentially flipping bits. Does that help solve the problem? While I didn't have time to work on the fashion problem, I did recognize that it involved an n-bishops and an n-rooks problem - that gave me some avenues of research to pursue rather than trying to invent the algorithm from scratch.)

I don't think this really says anything you didn't already know (at least in theory), but it's important to recognize that there are real skills to apply here. In particular, breaking a big problem up into smaller problems is one of the most important techniques in computer science. Experienced developers do it automatically, but it's surprisingly difficult to teach to people new to the field. But I believe that it is a skill that can be mastered independently of your ability to develop complex mathematical algorithms.

I didn't mean to imply you were new to the field! I teach Intro to Programming at a community college, and I was thinking of how difficult it is to get some of the students to break a big problem up into smaller chunks.

I guess the solution is to just do more of these types of problems?

If it gives you any motivation, there's a fun site called AtCoder that hosts weekly competitions similar to Topcoder, Codeforces, Google Code Jam, etc. However, the thing I like about this site from the others is that they have a ranking system just like Go (I'm 9k there atm, and tourist who could be considered the best in this field is 10d), and the quality of the problems are excellent with interesting problem statements and thorough editorials provided after the contest. It's also cool to see Petr do it live. The only downside is having to wake up at 5am on Saturdays . Check it out!

One way is to work backwards. For example, with Towers of Hanoi, the solution requires you to move the bottom block to a different peg - how do you do that? Well, the rest of the blocks have to be stacked on the third peg, or you can't move the bottom block to the right place. And then you note that this is a smaller version of the same problem.

I didn't catch on to the fact that there's a systematic way to make progress and move forward.

Moving forward is particularly difficult for me in these types of problems.

It's easy to setup some sort of enumeration of states so that I can do a breadth first search or depth first search, for example. But then there's the fear of encountering cycles.

An easy example is the classic Towers of Hanoi (https://en.wikipedia.org/wiki/Tower_of_Hanoi) problem. Obviously, I can look at the solution to see what they did, but without doing that, my thought process goes like this:

1.) Think of a couple of examples (using numbers to represent the size of the disk - smaller number is a smaller disk).

1
2
3 _ _

Valid moves? I can move "1" to either of the empty slots. Doesn't matter which, since it's symmetrical.

2
3 1 _

Valid moves?
a.) I could move "1" to the empty spot (silly, though, since it's symmetrical).
b.) I could move "2" to the empty spot.
c.) I could move "1" back to on top of number 2.

Obviously "c" isn't making progress toward a solution, and it's stupid. If I were playing the game myself, I can easily tell that moving "1" back to "2" is not making progress toward finding a solution.

But how do I express this so that the algorithm knows this?

So in short, my mind tries to think of a way to iterate through all possible "next states". But I get into trouble when I realize that I might end up going back to a "previous state". Then I get a little flustered about how to proceed.

Looking at the solution, it's a systematic procedure. There's an observation that the problem can be broken up into smaller subproblems that, when combined, form a complete solution.

It's sometimes tricky for me to make this observation.

As you can see from my convoluted thought process above, I don't make any observation about breaking the problem into subproblems.

Whew. Not fast enough, I guess. I worked on problems 1 and 2. Conceptually, they didn't seem very difficult. I ran into a couple of hiccups with getting the correct input for problem 2, and didn't get something submitted in time.

I guess I need to work on my speed.

I got problem 1 correct.