How to read an Analysis
The Problem Analyses on this website are designed to guide the reader throughout the process of solving the problem. We want to answer the question: "How can someone reproduce the thinking that leads to correct solutions?" For that purpose, each analysis is broken into the following sections:
- Problem Description: Written in my own words. This helps me to make sure that I fully understand what the problem is saying.
- Initial Observations: Immediate ideas that came to mind while reading the problem-statement. Reflects the "intuition".
- Idea Sections: Each "Idea" is a single cohesive train of thought. Includes problem-solving processes used, observations + proofs made and questions asked. At the end of each Idea Section, we describe the result (Wrong Answer, Accepted, Time-Limit-Exceeded, etc.). An Idea that we abandon will be recorded as a "No Solution" result.
- Review Section: A concise solution summary, reiterating the main ideas. Also includes Key Points and Observations, techniques used, learning points. We also try to categorize and generalize the problem, by looking at related problems.
What are the Problem Solving Techniques
There is no "exact-science" to problem-solving (despite the fact that I call this website a "Theory of Problem-Solving"). There are many heuristics and mental habits that we can consciously try in order to maximize our ability to solve problems. Most of the following ones come from "How to Solve Problems" (by George Polya) and "Problem Solving through Problems" (by Loren C. Larson):
- Draw a Picture: Sometimes seeing an idea with your eyes helps to think about a problem differently.
- Examine Examples: The sample test-cases and examples of your own can help you to understand how the problem works.
- Draw from Experience: Try to recall a relevant theorem, algorithm, or similar problem.
- Problem Transformation: Change the way you think about the problem. Rephrase the problem using different notation.
- Problem Simplification: Think of simple / special cases to solve first. Once you solve these, try the real problem.
- Problem Generalization: Is this problem a special case of a more general problem? Try the larger one instead.
- Work Backward: The input is A, the answer is B. What if the input was B and answer A? (This can take on other forms too)
- Write Out: When formulas are involved, write them down. Avoid errors later, and maybe even find a nice pattern.
- Ask for Help: It is sometimes okay to ask for help or to look at the solution if you're stuck.
- Generate and Test: If you have a hunch (intuition), try it, and prove that it works later.
- Exploit the Constraints: Sometimes the input is so constrained that a hard problem becomes easy. Pay attention.
About the author (dojiboy9)
Hi! My name is Deon, and I love to write code. I began writing code early on, attempting to make video games. In high school, I took part in the Canadian Computing Competition, which introduced me to the world of Programming Contests. I was never very good, but I loved doing it, so I've been practicing ever since.
I am now a student at the University of Waterloo, where I was a member of the 2012-2013 ACM International Collegiate Programming Contest (ACM ICPC) team that went to the 2013 World Finals in St. Petersburg. I have also been competing in online programming contests such as TopCoder, Codeforces, and CodeChef. My handle (or "user id") is: dojiboy9.
Why start a blog?
A mentor suggested that I start writing "analyses" of the problems that I solve. Eventually, I started to make it into a habit, because I've found that the best way to actually learn and improve is to not just solve a lot of problems, but to actually go back and think about how you solved the problem in the first place. In essence, go back and solve it again, but being more conscious about the questions you asked yourself and what assumptions or claims you made informally. By formalizing and writing it out, you may even find connections that you didn't realize were there.
Books, such as "How to Solve Problems" (by George Polya) and "Problem Solving through Problems" (by Loren C. Larson) really opened up to me this concept that there is really a study of problem-solving itself. Hence, I decided to start thinking about this "theory of problem-solving" (or "heuristic", as some people call it), and incorporating it into the analyses of problems I solve for programming contests.
Lastly, the book "Apprenticeship Patterns" (By Dave Hoover and Adewale Oshineye) gave me the idea to start a blog about it (to "Expose [my] Ignorance", in a sense). And so now, here I am!